Fernando J. Pereda’s blag

April 27, 2009

Small C trivia

Filed under: blag — Tags: , , , — Fernando J. Pereda @ 8:50 am

This is somehow surprising the first time you see it and it is interesting to remind it to people from time to time. The question is easy, does this program always return 0? That is, are those summations the same?

If there’s a case when it doesn’t, provide a sample input and explain why it happens.

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
	float f[argc - 1];
	for (int i = 1; i < argc; i++)
		f[i - 1] = atof(argv[i]);
	float r1 = 0;
	for (int i = 0; i < argc - 1; i++)
		r1 += f[i];
	float r2 = 0;
	for (int i = argc - 2; i >= 0; i--)
		r2 += f[i];
	return r1 != r2;
}

As usual, I’ll post the solution in a couple of days or when someone gets it right (which is always the case :))

— fpereda

Update: correct typo spotted by Snaury.

Advertisements

4 Comments »

  1. The line with f[i] = atof(argv[i]) must be a typo. Not only f[0] is garbage, you get possible stack corruption, too.

    Comment by Snaury — April 27, 2009 @ 9:55 am

  2. As for the right answer, if the line there reads f[i-1] = atof(argv[i]), then no, they can be different. The problem is how numbers are stored as floating point, and when a very large number (i.e. that has no bits left for fractional part) is summed with a very small number, then result doesn’t change. So if the first argument is a very large number, and all the rest are comparatively small, but summed give you some comparatively large number (in relation to the first number), then from left to right result won’t change, and will stay equal to the first number. But from right to left you could get a big number, and two big numbers summed would be different from the first number.

    …sorry for my poor explanation. ;)

    Comment by Snaury — April 27, 2009 @ 10:00 am

    • I think you are just half-right. The problem here is that floating point (as specified by IEEE754, that is) addition isn’t associative. But you don’t need to involve big and small numbers, the following sequence will give you different results if summed left to right and right to left: 0.1 0.2 0.3 0.4 0.5

      Also, for the record, neither does the distributive property hold.

      — fpereda

      Comment by Fernando J. Pereda — April 27, 2009 @ 10:28 am


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: