computer accuracy

lfm · 2009-11-06, 07:15

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;
}

Batalov · 2009-11-06, 07:42

Predict it with float, too.

retina · 2009-11-06, 09:13

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

Brian-E · 2009-11-06, 13:11

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:

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.

petrw1 · 2009-11-06, 14:36

I agree with the last part:

d is definded but not used

WMHalsdorf · 2009-11-06, 14:42

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

storm5510 · 2009-11-06, 20:13

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

ewmayer · 2009-11-06, 20:38

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

gcc -O0 gives 49

gcc -O3 gives 41

Interesting...

flouran · 2009-11-06, 21:53

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

TimSorbet · 2009-11-06, 23:07

Quote:

Originally Posted by flouran

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

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?

Batalov · 2009-11-07, 00:32

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 every computer scientist... etc.
Written more than 15 years ago. Great reading.

2009-11-06, 07:15	#1
lfm Jul 2006 Calgary 5²×17 Posts	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; }

2009-11-06, 20:38	#8
ewmayer ∂²ω=0 Sep 2002 República de California 2DEB₁₆ Posts	I guessed 3, but in the real world I see something rather different: gcc -O0 gives 49 gcc -O3 gives 41 Interesting... Last fiddled with by ewmayer on 2009-11-06 at 20:38

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Accuracy and Precision	davieddy	Math	0	2011-03-14 22:54
CPU Credit Accuracy	g0vegan	PrimeNet	1	2008-11-04 20:26
Verify Accuracy of Test	Numbers	PrimeNet	8	2005-07-31 08:16
Calculating sieving % accuracy	amcfarlane	Math	3	2005-01-02 19:34
Accuracy of our work [k*2^n-1, k<300]	Kosmaj	15k Search	87	2004-11-13 09:35

2009-11-06, 07:42	#2
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2·11·457 Posts	Predict it with float, too.

2009-11-06, 09:13	#3
retina Undefined "The unspeakable one" Jun 2006 My evil lair 3·17·131 Posts	I would guess: 2[sup]53[/sup]+1

2009-11-06, 13:11	#4
Brian-E "Brian" Jul 2007 The Netherlands 2·11·149 Posts	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: 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.

2009-11-06, 14:36	#5
petrw1 1976 Toyota Corona years forever! "Wayne" Nov 2006 Saskatchewan, Canada 1010010011011₂ Posts	I agree with the last part: d is definded but not used

2009-11-06, 14:42	#6
WMHalsdorf Feb 2005 Bristol, CT 3³×19 Posts	It's a question of precision. a=3 since b = 1/3 can't be represented precisely in floating point.

2009-11-06, 20:13	#7
storm5510 Random Account Aug 2009 Not U. + S.A. 3²·281 Posts	I doesn't do anything but loop repeatedly. C is always equal to 1.

2009-11-06, 21:53	#9
flouran Dec 2008 7²·17 Posts	I'm a beginner programmer, but isn't this an infinite loop?

2009-11-07, 00:32	#11
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2746₁₆ Posts	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 every computer scientist... etc. Written more than 15 years ago. Great reading.