Parolski.com

Ten days ago we had a look at Java’s ability to deal with numbers which had alot of decimal places. Liam pointed out that having to loop through a variety of operations is longer than performing a more efficient operation once.

With Liams magical formula, we get the following Java, with no loop:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

import java.math.BigDecimal;
 
public class The_proper_half {
 
    public static Integer times_to_loop;
 
    /**
     * @param args the number of times you want to run the loop
     */
    public static void main(String[] args) {
        calculate(Integer.valueOf(args[0]));
 
    }
 
    public static void calculate(int times_to_loop) {
        //The Number we want to half
        BigDecimal number_to_half = new BigDecimal("10");
        //The result of doing the half
        BigDecimal the_half = new BigDecimal("0");
        //The number we want to divide by
        BigDecimal divider = new BigDecimal("2");
 
        the_half = (number_to_half.divide(divider.pow(times_to_loop)));
 
        System.out.println("The last number has " +
                ((Integer) number_to_half.subtract(the_half).toString().length()
                - 2) + " decimal places: ");
 
        System.out.println(number_to_half.subtract(the_half));
    }
}

As you can see, we only perform the opertation once (line 23), but admitadly, to get the correct number at the end, we still do the subtraction at the end!

Regarding optimisation, there are huge benefits. It turns out that the old way if hugely costly for thousands of iterations. These are the results for 10000 iterations, the old way:

anton@anton-laptop classes $ time java Half_of_a_half 10000 > /dev/null

real    5m22.714s
user    5m21.320s
sys    0m1.052s

The results for the new way are much better:

anton@anton-laptop classes $ time java The_proper_half 10000 > /dev/null

real    0m1.019s
user    0m1.248s
sys    0m0.052s

So it went from over five minutes, down to just a second. That was just by changing from a loop a single statement. Thats pretty cool stuff!

I have to admit here, the difficult bit is probably not the code. Its the abillity to see how a problem may be translated from one way of expressing it to another. Its that bit of genius thats really done the work here. Credit to Liam for the genius!

This is a common riddle, so if you’ve heard it, don’t shout out the answer (people might think your strange for shouting at the internet….)

Take a number. Then, half that number. Then half that half and add it to the first half. Before that gives people a headache, lets do a little example:

Lets use 10 . Then half of ten gives us 5. Then, half five (2.5) and add it to the first half, 5. This gives us 7.5

Continue to half the last half, adding it to the sum of the previous halves. Phew, I hope thats explained properly.i.e. half two point five, and add it the the 7.5 we already have, which give us 8.25

Okay, so the question is this. If we keeping adding on the halves, will we ever reach 10 again? Well, I like Java, so lets get all geeky and model the problem. For this, the double and float data types won’t give us enough decimal places. For this, we’ll need: math.BigDecimal . The Big Decimal. Sounds ominous!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

import java.math.BigDecimal;
public class Half_of_a_half {
 
    public static Integer times_to_loop;
 
    /**
     * @param args the number of times you want to run the loop
     */
    public static void main(String[] args) {
        calculate(Integer.valueOf(args[0]));
    }
 
    public static void calculate(int times_to_loop) {
        //The Number we want to half
        BigDecimal number_to_half = new BigDecimal("10");
        //The result of doing the half
        BigDecimal the_half = new BigDecimal("0");
        //The number we want to divide by
        BigDecimal divider = new BigDecimal("2");
 
        for (int i = 0; i < times_to_loop; i++) {
 
            number_to_half = number_to_half.divide(divider);
            the_half = the_half.add(number_to_half);
 
            System.out.println(the_half);
        }
        System.out.println("The last number has " +
                ((Integer) the_half.toString().length() - 2) + " decimal places");
    }
}

This code takes a single parameter on the command line: the number of times to half by

e.g.

anton@anton-laptop classes $ java Half_of_a_half 10
5
7.5
8.75
9.375
9.6875
9.84375
9.921875
9.9609375
9.98046875
9.990234375
The last number has 9 decimal places

So as we can see, the decimal places just get long and longer. The additions are never big enough to get us close enough to the original number. Problem solved!

The fun bit is realising the significance of the calculation, or rather, the speed with which it was done. Performing 1000 divisions and additions takes less that 0.2 of a second! Maybe thats not so fast by todays computing ability, but by human standards thats pretty extreme.

anton@anton-laptop classes $ time java Half_of_a_half 1000 > /dev/null


real    0m1.387s
user    0m1.916s
sys    0m0.036s