CODEWITHSUNDEEP
java
manic
manic

Reputation: 83

Java same calculation with different way gives different result

I have an exercise telling me to calculate the sum of 1/i (i ranging from 1 to 1000000000) with different approaches. So I have tried several approaches but there are 2 in particular that give me different results

The 1st method is to use 2 loops and increment using one variable.

public class Main {
    public static void main(String[] args){
        double a = 0d;
        for (long i = 1; i <= 500000000; i++) {
            a = a + (1.0/i);
        }
        for (long i = 500000001; i <= 1000000000; i++) {
            a = a + (1.0/i);
        }
        System.out.println("result: "+ a);
   }
}


result: 21.30048150234855

The 2nd method is use 2 loops using different variable and add them in a 3rd variable.

public class Main {
    public static void main(String[] args){
        double a = 0d;
        double b = 0d;
        for (long i = 1; i <= 500000000; i++) {
            a = a + (1.0/i);
        }
        for (long i = 500000001; i <= 1000000000; i++) {
            b = b + (1.0/i);
        }
        double c = a+b;
        System.out.println("result: "+ c);
   }
}

result: 21.300481502348767

I don't understand why they return different results... I am doing this because I will use multiple threads to calculate this, so if I use 10 threads, the gap with the real results will be higher.

Upvotes: 0

Views: 502

Answers (2)

rzwitserloot
rzwitserloot

Reputation: 102795

Consider how computers work. They have bits. Bits are like light switches.

Let's say you are in a pristine room with nothing in it whatsoever, and all you have is 2 lightswitches. Your mission is to send me a message. You get to mess with the light switches but nothing else, and then you have to leave. Sometime later I will show up.

How much data can you send me?

The answer is: There are 4 different things: down, down, down, up, up, down, and up, up. That's it. So, if your mission is to tell me about, say, what number to pick on a roulette wheel, that's no good - a wheel has 37 to 38 different options but you can only tell me to pick from one of 4.

The same applies to doubles. They are powered by 64 bits. Just like 2 bits give you 4 options (because 2^2 is 4), 64 bits give you 2^64 = 18446744073709551616 different options. That's... a lot of different options you can convey with 64 bits, but it is still finite.

This applies to doubles: Doubles can be used to represent any number. From 123094359823958435.2432134 to 0.000000000000001. Except, that can't really be true. We know that there are only at most 18446744073709551616 numbers which are actually representable by a double, for the same reason 1+1=2 - it is mathematically impossible for 64 bits to be capable of differentiating any more numbers than 18446744073709551616.

Let's call those 18446744073709551616 the 'blessed' numbers.

I will give you a quick hint, 0.1 is not blessed. This sounds insane, but note that in decimal numbers, the notion of 'divide 1 by 3' is not blessed; you cannot represent that even if I give you 100 digits to toy with. You'd write 0.3333 and a lot more 3s and you still haven't quite gotten there.

Computers are binary, so you get similar issues; there are numbers that work in decimal (0.1), which, in binary, require rounding, just like trying to represent 1/3 in decimal does.

And yet this:

double d = 0.1;

compiles just fine! What's going on? 0.1 is not a blessed number!

Ah, that's the rules of how double math works kicking in. The rule is very very very simple: If the result of any calculation isn't blessed, then round it to the nearest blessed number. The nearest blessed number is actually 0.1000000000000000055511151231257827021181583404541015625.

Because that is incredibly annoying to look at, System.out.println and friends have built-in some rounding behaviour to take care of these most egregious cases.

But that's just rounding the number some when you print it. The rounding is still happening. A very tiny shift for every math operation you are executing, and you're executing rather a lot of them.

Furthermore, the blessed numbers are unfairly distributed: There are as many blessed numbers between 0 and 1 as there are between 1 and infinity. As you move away from the 0, you get fewer and fewer blessed numbers, which means when a result isn't a blessed number and thus needs to be rounded to be closer to one, the rounding errors become more and more dire. In fact, above 2^53 or so, the gap between blessed numbers is higher than 1.0.

That's why your code produces different results; your second one has fewer rounding errors in it because you are closer to the 0. But, they both have rounding issues.

Can you get rid of those rounding issues?

Maybe. BigDecimal can do it, but it is quite tricky to use and quite slow. BigDecimal still can't deal with something as simple as 'divide 1 by 3', but it will just refuse to do that (throws an exception instead) unless you instruct it on how, precisely, it is allowed to round.

Upvotes: 4

Joop Eggen
Joop Eggen

Reputation: 109532

A floating point number is a finite sum of powers of 2. Which will introduce an approximation error.

Two consecutive (near distinguishable) doubles can easily have a large difference, say > 1.0 if the numbers have a high exponent. So for addition it matters how large the number is.

I might be wrong here! AFAIK starting with a two sum variables from 0 is the most precise as then in general the old sum is smaller, and the sum's new value can be more precise.

The algorithm is unstable and the divisions might become undistinguishable from 0.

(Please use 500_000_000L and such for clearness.)

Upvotes: 0

Related Questions