Playing with A* Updated

A* algorithm

Just updated the Playing with A* algorithm app so that now one can toggle on and off the use of the heuristic and the use of a cross product tiebreaker. This leads to new variants of the algorithm, mainly the well known Dijkstra algorithm.

This A * application was written in Java, so you’ll need to check your java permissions to run it. You can download the .jnlp file and run it from your computer.

The A* Algorithm (A star) is a pathfinding and graph traversal algorithm. It is widely used in computer science, games, robotics and network science. A thorough overview of the algorithm can be found in Introduction to A* which presents several comparisons and illustrations on the mechanics of the A star algorithm.

Java Hangs Converting 2.2250738585072012e-308

class runhang {
public static void main(String[] args) {
  double d = Double.parseDouble("2.2250738585072012e-308");
  System.out.println("Value: " + d);

via Java Hangs When Converting 2.2250738585072012e-308 – Exploring Binary.

Don’t try this on production machines… :)

Square Root of Big Numbers in Java

Computing the square root of big numbers is a problem for computers. The way computations happen, computers don’t really like the huge numbers some scientists like to put out. Even if For several applications you can easily go from int to long or from float to double, there are times when even those aren’t enough.

Java has a few classes that deal with large numbers. They are BigInteger and BigDecimal. Between the two you’ll probably get almost everything you need for big number computation.

Although the way to do operations with the BigInteger and BigDecimal can be counter-intuitive in mathematical terms, it is correct in an object oriented way. The only thing that I found lacking until now is a method to calculate square roots in BigDecimals… That is annoying.

I searched around the internet and found an elegant (and fast) implementation for BigDecimals of the square root by Michael Gilleland. I’m copying is code here at the end of this post for the sake of preservation (I hate sites going away and these things being lost).

Java code for large number computing of square roots

The code bellow for computing the square root of large numbers works very well. You just need to remember to set the scale (the number of digits you want in the fractional part) to 100 or more. Yes, that’s the kind of precision one sometimes needs and that’s why I can’t convert to doubles, do sqrt, and go back to BigDecimal. 

The class BigSquareRoot for computing large numbers square roots in Java. Next step: Compute the number PI as a large number computation with the same precision.

// Compute square root of large numbers using Heron's method
import java.math.*;
public class BigSquareRoot {
    private static BigDecimal ZERO                   = new BigDecimal("0");
    private static BigDecimal ONE                    = new BigDecimal("1");
    private static BigDecimal TWO                    = new BigDecimal("2");
    public static final int   DEFAULT_MAX_ITERATIONS = 50;
    public static final int   DEFAULT_SCALE          = 10;
    private BigDecimal        error;
    private int               iterations;
    private boolean           traceFlag;
    private int               scale                  = DEFAULT_SCALE;
    private int               maxIterations          = DEFAULT_MAX_ITERATIONS;
    // ---------------------------------------
    // The error is the original number minus
    // (sqrt * sqrt). If the original number
    // was a perfect square, the error is 0.
    // ---------------------------------------
    public BigDecimal getError() {
        return error;
    // -------------------------------------------------------------
    // Number of iterations performed when square root was computed
    // -------------------------------------------------------------
    public int getIterations() {
        return iterations;
    // -----------
    // Trace flag
    // -----------
    public boolean getTraceFlag() {
        return traceFlag;
    public void setTraceFlag(boolean flag) {
        traceFlag = flag;
    // ------
    // Scale
    // ------
    public int getScale() {
        return scale;
    public void setScale(int scale) {
        this.scale = scale;
    // -------------------
    // Maximum iterations
    // -------------------
    public int getMaxIterations() {
        return maxIterations;
    public void setMaxIterations(int maxIterations) {
        this.maxIterations = maxIterations;
    // --------------------------
    // Get initial approximation
    // --------------------------
    private static BigDecimal getInitialApproximation(BigDecimal n) {
        BigInteger integerPart = n.toBigInteger();
        int length = integerPart.toString().length();
        if ((length % 2) == 0) {
        length /= 2;
        BigDecimal guess = ONE.movePointRight(length);
        return guess;
    // ----------------
    // Get square root
    // ----------------
    public BigDecimal get(BigInteger n) {
        return get(new BigDecimal(n));
    public BigDecimal get(BigDecimal n) {
        // Make sure n is a positive number
        if (n.compareTo(ZERO) <= 0) {
            throw new IllegalArgumentException();
        BigDecimal initialGuess = getInitialApproximation(n);
        trace("Initial guess " + initialGuess.toString());
        BigDecimal lastGuess = ZERO;
        BigDecimal guess = new BigDecimal(initialGuess.toString());
        // Iterate
        iterations = 0;
        boolean more = true;
        while (more) {
            lastGuess = guess;
            guess = n.divide(guess, scale, BigDecimal.ROUND_HALF_UP);
            guess = guess.add(lastGuess);
            guess = guess.divide(TWO, scale, BigDecimal.ROUND_HALF_UP);
            trace("Next guess " + guess.toString());
            error = n.subtract(guess.multiply(guess));
            if (++iterations >= maxIterations) {
                more = false;
            } else if (lastGuess.equals(guess)) {
                more = error.abs().compareTo(ONE) >= 0;
        return guess;
    // ------
    // Trace
    // ------
    private void trace(String s) {
        if (traceFlag) {
    // ----------------------
    // Get random BigInteger
    // ----------------------
    public static BigInteger getRandomBigInteger(int nDigits) {
        StringBuffer sb = new StringBuffer();
        java.util.Random r = new java.util.Random();
        for (int i = 0; i < nDigits; i++) {
        return new BigInteger(sb.toString());
    // -----
    // Test
    // -----
    public static void main(String[] args) {
        BigInteger n;
        BigDecimal sqrt;
        BigSquareRoot app = new BigSquareRoot();
        // Generate a random big integer with a hundred digits
        n = BigSquareRoot.getRandomBigInteger(100);
        // Build an array of test numbers
        String testNums[] = { "9", "30", "720", "1024", n.toString() };
        for (int i = 0; i < testNums.length; i++) {
            n = new BigInteger(testNums[i]);
            if (i > 0) {
            System.out.println("Computing the square root of");
            int length = n.toString().length();
            if (length > 20) {
                app.setScale(length / 2);
            sqrt = app.get(n);
            System.out.println("Iterations " + app.getIterations());
            System.out.println("Sqrt " + sqrt.toString());
            System.out.println("Error " + app.getError().toString());

bigsquareroot class in java how to find big square root of a big number in java using biginteger java biginteger square root sqrt big sqrt long java

Performance no Java

Todos desejamos performance nas nossas aplicações. No Java e apesar de alguns dizerem que é mais rápido que C++ isto nem sempre é verdade, mas vou falar disso noutra altura. Hoje o que queria colocar aqui é uma ajuda para quem tem que trabalhar com Java. Em vez de correr a JVM client o melhor para performance é mesmo correr a JVM server. Para isso terá que utilizar o terminal e correr os programas da seguinte forma

java -server -jar programa.jar

Ora para não ter que andar sempre a adicionar -server no terminal, o melhor é colocar o -server como default. Para isso basta editar o ficheiro jvm.cfg (que é um ficheiro de texto simples) e onde está:

-client KNOWN -server KNOWN

é só trocar a ordem para:

-server KNOWN -client KNOWN

Assim tudo o que for java vai correr na JVM server e só se chamarmos explicitamente a versão client é que será corrida aí.

Ganhos de performance? Sim bastante notáveis. Estive a experimentar calcular uma série de Fibonacci e posso dizer que o tempo de execução foi em média:

-client: 540ms -server: 397ms

o que dá para o mesmo programa um ganho de 143ms ou cerca de 26%, nada mau. O downside? Tradicionalmente o JVM -server demora um pouco mais a arrancar e come mais memória, mas se depois se tornar mais rápido… para quê queixarmo-nos…

no Mac OS X Tiger o jvm.cfg está em /System/Library/Frameworks/JavaVM.framework/Versions/1.5.0/Home/lib/jvm.cfg

Bem, por curiosidade o mesmo cálculo em C sem optimizações demorou 810ms e com optimizações -O3 cerca de 260ms. Mas como disse estas discussões são para outra altura.

Jogando Lemmings!

A Universidade de Oxford produziu um emulador de x86 em Java e tem online um Demo desta máquina virtual a correr DOS (FreeDOS), mas a grande vantagem é que se alguém quiser matar saudades de jogar alguns jogos clássicos, esta máquina inclui no disco C:

Space Invaders


Prince of Persia

Super Mario


King Kong

Ok, já chega de saudades… vamos lá voltar para a realidade…

Modelo Bak-Sneppen

Andámos todos de volta do modelo do Merton, que nem tive tempo para outras coisas, mas agora que a entrega no passado, pus-me a brincar com o modelo Bak-Sneppen, falado na aula de Matemática. Queria ver o boneco a funcionar… e depois de o implementar, não é que funciona?


Para quem quiser experimentar, criei o projecto no NetBeans e podem fazer download do projecto para o correr no vosso computador.