1

Possible Duplicate:
Why “for( i = 0.1 ; i != 1.0 ; i += 0.1)” doesn’t break at i = 1.0?

I have a numeric (real) interval [x, y]. I must iterate through it using something like:

nr = 0;
for (i = x; i <= y; i += step) //step is a small double value
    nr++;

For [-1, 1] with 0.001 step, it is clear nr should be 2001 (-1.000 ... 0.999 1.000), however it computes nr = 2000 (I investigated and it fails the last comparison: 0.999 + 0.001 > 1.000)

How can I compute the exact nr value?

Community
  • 1
  • 1
kaspersky
  • 3,959
  • 4
  • 33
  • 50
  • 3
    `float`/`double` are inherently inexact; if you need "exact," use an integer type – Kevin Dec 06 '12 at 20:08
  • Do you truly want only to count the number of steps, or will there be more in the body of your loop? What will be in it? – Eric Postpischil Dec 06 '12 at 20:17
  • nr represents the height of an image, which is mapped on an real plane. I calculate some pixel values in the for(s). I understand it would be impossible to calculate nr exactly, so I'll stick to "height = (int) ((y - x) / step). – kaspersky Dec 06 '12 at 20:22
  • 1
    @BoPersson: This question does not ask why the summation is incorrect, as your proposed duplicate does. This question, if read literally, asks how to calculate floor((y-x)/step) exactly. – Eric Postpischil Dec 07 '12 at 02:17

4 Answers4

3

You need to do this using integers, or be happy with imprecision, because floats and doubles are inherently imprecise*. Your code is working exactly according to the C language spec. Floats and doubles are not safe to use in situations requiring exact precision.

Other than that you need more information in your question regarding what your requirements are. If nr is a temperature then to calculate the exact value you need to use physics that either do not exist or cannot exist (I'm not a physicist so I couldn't tell you). If step is actually an irrational value then you have to round up or down - your call and which is correct depends on your business logic requirements. If it's rational and no rounding is needed then you need to multiply out by the lowest common denominator and use ints (or a fraction class in C or such).

*Per comment floats/doubles are precise when the fractions have denominator that is a power of 2, if you can force step and y to conform to this your problem will sort of clear, but of course if step does not divide evenly into y you will need to do the exact same business logic-handling as above.

djechlin
  • 59,258
  • 35
  • 162
  • 290
  • How would you solve the problem? – kaspersky Dec 06 '12 at 20:10
  • I don't know because I don't know what your application requirements are. Also, what have you tried? – djechlin Dec 06 '12 at 20:10
  • This neither answers the question nor explains why the code does not behave as desired. – Eric Postpischil Dec 06 '12 at 20:12
  • @EricPostpischil - fair, added the information regarded imprecision that was posted in the comment and the respective solutions for all possible situations the OP could be dealing with but has not specified. – djechlin Dec 06 '12 at 20:16
  • "Imprecision" as a generalization for floating point is invalid. Floating point is imprecise under certain conditions and not under others. See my answer. – Olof Forshell Dec 06 '12 at 20:35
0

The problem that you are experiencing is that floating point numbers (float or double) are not stored exactly so the representation in memory is more ofter than not exact.

So you have two choices - live with precise numbers or use integers for the number of times around the loop and then compute the value.

This can be done as follows:

int numberOfIntervals = 2000;
double lowestValue = -1.0;
for (loop = 0; loop <= numberOfIntervals; ++loop)
{
    double v = (0.001 * loop ) + lowestValue;
}
Ed Heal
  • 59,252
  • 17
  • 87
  • 127
  • In many instances where a similar question is asked in Stack Overflow, there is an obvious translation of the loop to integers. In this case, however, x and y are arbitrary floating-point values, and it is not immediately obvious how to implement the desired computation. There is actually an interesting problem here, and it deserves more than a curt answer. – Eric Postpischil Dec 06 '12 at 20:13
0
int nsteps = (int)((y-x)/step);
for(int i=0; nsteps; ++i){
   double v = x + (i*step);  // use v in your calculations
}
Rodney Schuler
  • 2,158
  • 4
  • 23
  • 34
  • 1
    We should consider for what values of `x`, `y`, and `step`, this might produce an incorrect value for `nsteps`. – Eric Postpischil Dec 06 '12 at 20:15
  • That's actually the (best effort) solution I'm using right now. However, it will compute nr = 2000. Also, wouldn't it be faster to avoid i * step multiplication at each iteration? – kaspersky Dec 06 '12 at 20:15
  • @gg.kaspersky: `i*step` is not expensive on typical processors, unless you are working on some underpowered embedded processor. – Eric Postpischil Dec 06 '12 at 20:18
  • The beauty of C is that you control the tradeoff between precision (loop with an int & multiply) or speed (loop with double & no multiply) – Rodney Schuler Dec 06 '12 at 20:19
-1

It's just not true that binary floating point is imprecise. What is true is that for numbers whose contents conform to a sum of different (positive and/or negative) powers of two the value will be exact. Obviously decimal numbers conform to a sum of powers of ten so they won't be exact. Base four, eight and sixteen conform because they are multiples of two.

I posted this answer quite some time ago and it will give you a hint as to just how exact a floating point number can be. You can also see how fractions may be assembled by summing negative powers of two.

As to how to solve the problem you have the tools you need. If the algorithm doesn't fit you can make it fit.

Community
  • 1
  • 1
Olof Forshell
  • 3,169
  • 22
  • 28
  • Actually, decimal numbers are also conform to a sum of powers of two: 11 = 8 + 2 + 1, and we are able to encode their exact value using binary, as well as whichever base. The difference is not int binary/decimal base representation, but in integer/real numbers. – kaspersky Dec 06 '12 at 20:41
  • So if decimal numbers also conform to powers of two why doesn't your program work? – Olof Forshell Dec 06 '12 at 21:15
  • I misunderstood what you said (my English is poor). I thought you meant integer decimal numbers, but you meant fractional numbers. – kaspersky Dec 06 '12 at 22:49
  • Your original question contained issues with decimal numbers containing both integers and fractions. That was what my answer was about. – Olof Forshell Dec 07 '12 at 14:44