computer accuracy
 

Predict the output of this simple C program before you run it:


#include <stdio.h>

int main(void) {
double a, b, c, d;

a = 0.0;
do {
a = a + 1.0;
b = 1.0 / a;
c = b * a;
} while (c == 1.0);

printf("%g\n", a);

return 0;
}

:tu: Predict it with float, too. :rolleyes:

I would guess: [spoiler]2[sup]53[/sup]+1[/spoiler]

Your puzzle makes me reflect that I worked for 8 years in a programming environment without ever once using floating point arithmetic in anything I wrote.

Still, no harm in guessing, baseless though my guess is:

[spoiler]Depending on the compiler, the program will either output 1.0 or not terminate. (A good compiler might combine the commands in the loop setting b and c to simply assign c=1.0.)
Plus the compiler should warn about testing the equality c==1.0 with floating point numbers, not to mention the failure to use the variable d.
[/spoiler]

I agree with the last part:

[SPOILER]d is definded but not used[/SPOILER]

It's a question of precision.
[SPOILER]a=3 since b = 1/3 can't be represented precisely in floating point.[/SPOILER]

I doesn't do anything but loop repeatedly. C is always equal to 1.

I guessed 3, but in the real world I see something rather different:

gcc -O0 gives 49

gcc -O3 gives 41

Interesting...

I'm a beginner programmer, but isn't this an infinite loop?

[quote=flouran;195086]I'm a beginner programmer, but isn't this an infinite loop?[/quote]
Only if you have no rounding errors at all. That's where the challenge comes in: exactly when would the given language (C) using the given method for storing fractional parts (the one specified by double) make a rounding error big enough to cause the condition (c == 1.0) to fail?

It doesn't really have to do with the language (except for the bit that the compiler could optimize the whole thing out). It's the IEEE standard for , and it actually tries really hard to do the right thing, and that's why the loop goes as far as it does, which is fairly amazing.

Here's a document that indeed [URL="http://dlc.sun.com/pdf/800-7895/800-7895.pdf"]every computer scientist...[/URL] etc.
Written more than 15 years ago. Great reading.