Archive for December 2008

## Half a half: Part 2

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!

## An evening of violence.

This event happened about a week ago.

Its windy, dark, cold and wet outside. There is no rain, but a previous rain has left the pavement in a slippery way. I’ve gone for a run round the usual route round the Parc du Champs de Mars, which is just next to the Eiffel Tower. The half an hour run in these harsh conditions is quite rewarding, especially when you wake in the morning after.

The run finishes with a quick sprint up the steps of Musee de L’homme, and round the corner past the musee de l’homme cafe. That evening, it wasn’t possible to finish the run. 15 meters in front of me is a 6 foot 4 man, intimidating a woman at least a full head height shorter than him. He goes for a headbutt, missing by some distance quite deliberately. He leaves his head forward as he places clenched fists by his side, talking precise steps towards her. The gap between them is closing, despite the fact that shes cowering and peering behind her for a space to step. Shes clearly been in this position before; to twist your body round to look is to take your eyes off what you are avoiding is a bad move to make.

This incident is about to unfold in full sight of the 7 or so people around. Surprisingly no-one has made steps to intercede. Everyone has limits; mine are set at the instant he pulls his hand back for a strike. That is the moment for action. Before then, the mater may resolve itself with words, the preferred solution.

Something that I haven’t noticed is that upon completing the sprint, I’ve paused to observe the situation in a jog on the spot motion. Not a huge knees in the air jog, but one which resembles the boxers side to side stepping, just before he lunges forward at the punch bag. Coupled with an all black outfit (it just so happened to be all black that evening) and low comfortable shoulders, my presence is looking quite aggressive. Underneath this appearance, I’m just observing, waiting for the trigger, but hoping that its not pulled. I’m relaxed and calm, and with each step my breath is getting slower and slower, back to normal standing rate.

So what does every coward do before doing something stupid? He looks round. Having spotted me, he suddenly realises that he’s been watched all this time, and that he might have trouble pulling off a smack. He turns his attention towards me and takes a step in my direction.

From an Islamic perspective, Muslims are supposed to enjoin the good and forbid the evil. This can take many forms, and in this instance it involves defending someone who is unable to defend themselves. This includes all children, the elderly and women by default. Mostly, this situation is win-win. Allow me to break my analysis down for you:

• If he’s intimidated out of hitting her and calms down, she wins and he wins too; he won’t be going to jail

The complicated part is in explaining what might happen if he tries to attack me instead. Firstly, as a muslim, I believe that only God decides the timing of my death. If I’m to live until I’m 80 years old, its guaranteed. If I’m to die on a ferry which sinks in the sea, then I can’t avoid it. So in this instance, I’m not worried about death. If God decides I’m to die that day, its going to happen whether I’m hit by a bus, if I fall down a manhole, or if this man attacks me. This may sound a bit morbid, but its quite a relief knowing that all I have to do is take care of my health, God will decide the rest. Of course, my greater concern is always for those around me, family and friends who would be upset or set back in the event of my death. And of course, I don’t want it to happen any time soon My work schedule is too busy

If he attacks, and we have a little scuffle, he’s going to loose interest in further dealings very quickly. This is the nature of isolated public violence. People get embarrassed, feel ashamed, or realise that its just not worth it. I don’t want to hurt anyone, but sometimes you have to do what is right. Sometimes that means you get hurt, thats just how life is. Having grown up on a council estate, I’ve seen this happen many times before. 99% of incidents like this rely totally on posturing, so now is not the time to shrink in character or resolve. Most men appreciate that if their opposition is completely committed, its not worth it.

So what happened, I hear you asking?

He took a second step towards me, waving his arm vaguely at me as if to say “Whos this punk? “. I’m still jogging on the spot. I can hear the pat pat of water being lightly splashed under my feet; I had managed to stand in a shallow puddle. Just then, she shouts something to him, and he swings around with his attention back on her again. By now, some of those 7 or so people nearby have drawn closer to the situation and appear to know both the women and the man. Their group moulds back together as the man is calming down, him on one side of them, and the women on the other. They form together and the begin to head on a path beyond me, probably to go to the Eiffel Tower. I’m still not moving from my position. To do so is like saying your no longer paying attention. Taking your eyes off that kind of situation is the last thing you want to do. They walk past, the man only a few meters away from me now, but predictably he says and does nothing as they leave. I can smell alcohol on his breath. The pat pat sound turns into a squish squish sound as I walk back to the flat, reflecting on what just happened.

## Half a number, half it again and add it to the first half.

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 &lt; 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 ```