ansaurus

Question

Answer 1

A:

Start with 1.0, and keep doubling it until the test succeeds:

double x;
for (x = 1.0; x + 1 != x; x *= 2) { }
printf("%g + 1 = %g\n", x, x + 1);

Marcelo Cantos 2010-05-03 08:49:04

trying it out doesn't mean i understand why :) i'd kind of prefer to reason it out first. i guess this post is more generally about how rounding is incorporated into floating point math, as evidenced by the sample question i propose.

hatorade 2010-05-03 08:51:07

Answer 2

+5 A:

You just need an expression for the value of the LS bit in the mantissa in terms of the exponent. When this is > 1 then you have met your condition. For a single precision float the LS bit has a value of 2^-24*2^exp, so the condition would me met when exp is > 24, i.e. 25. The smallest (normalized) number where this condition would be satisfied would therefore be 1.0 * 2^25 = 33554432.0f.

I haven't checked this, so my maths may be off somewhere (e.g. by a factor of 2) and it's also possible that the FP unit does rounding beyond the 24th bit, so there may be a further factor of 2 needed to account for this, but you get the general idea...

Paul R 2010-05-03 09:05:28

oh man, i literally figured it out RIGHT as you posted this! Nice!

hatorade 2010-05-03 09:06:40

+1. Note that you can round toward +infinity, in which case the answer is +infinity.

AProgrammer 2010-05-03 09:18:00

Actually, x=2^24 is the first float to meet the condition (anything greater than 2^24 - 1 requires 25 bits, and hence more than a float can hold exactly).

Rick Regan 2010-05-03 12:57:08

@Rick: ah yes, that's a much simpler way of looking at it.

Paul R 2010-05-03 13:28:44

there are likely a couple of sticky bits beyond the mantissa that you dont see, used for rounding so depending on how the number makes it into the register (through an int to float or through float + float(1.0), etc) can have subtle differences, so it could be 24 or 25 or 26 bits but somewhere in that range you push that one off the end of the mantissa into the ether.

dwelch 2010-05-03 14:07:51

@dwelch: yes, I thought there might be at least one bit beyond the mantissa for rounding - this has prompted me to write some test code now to see what is actually going on for the various CPUs I have here.

Paul R 2010-05-03 15:49:32

@dwelch: I'm pretty sure it will happen in the 25 bit range; if not for 2^24 (it works for 2^24 in my test), soon thereafter. 25-bit integers have to be rounded to even numbers (16777216, 16777218, 16777220, 16777222, ...), so those are the candidates for x. You would have to be more than unlucky for all 2^23 of those -- each added to 1 -- to round away from x!

Rick Regan 2010-05-03 16:07:52

I would assume some fpus vary in this regard, I have not looked at the spec in a long time to see if it has details on this. From a theoretical perspective you need at least one more bit there to do the rounding. To answer the specific question also depends on the X and rounding 1 plus the right number will round into the mantiss and other rounding modes wont. Perhaps we have beaten this horse to death and the poster understands the exponent mantissa thing wellenough.

dwelch 2010-05-03 20:08:26

@dwelch: Good point about rounding mode. I think the only one that will cause a problem though is "round towards positive infinity" (assuming we're talking about positive integers). It should always round AWAY from x (round to nearest will round to x half the time, and round towards negative infinity and round towards 0 will round to x all the time -- my experiments on an Intel Core Duo confirm this).

Rick Regan 2010-05-04 00:56:29

Sure, round up or round to zero if the number is negative, round down wont be a problem. I was trying to think if x going into this add plus one had been the result of some other operation what might that extra rounding bit look like, I think I agree you probably have to allow for one bit beyond the mantissa and the bit after that is the one that wont affect X.

dwelch 2010-05-04 17:43:00

Answer 3

A:

I suggest that while trying to understand f-p numbers and f-p arithmetic you work in decimal with 5 digits in the significand and 2 in the exponent. (Or, if 5 and 2 don't suit you, 6 and 3 or any other small numbers you like.) The issues of:

the limited set of numbers which can be represented;
non-commutativity, non-associativity and non-distributivity;
the problems which can arise when treating f-p numbers as real numbers;

are all much easier to figure out in decimal and the lessons you learn are entirely general. Once you've got this figured out, enhancing your knowledge with IEEE f-p arithmetic will be relatively straightforward. You'll also be able to figure out other f-p arithmetic systems with relative ease.

High Performance Mark 2010-05-03 09:16:51

ansaurus

tags:

views:

answers:

C - floating point rounding

related questions