OpenEuphoria

Re: Rob's going to hate me... (Remainder bug)

• Posted by kbochert at copper.net Nov 08, 2003
• 620 views

On 7 Nov 2003 at 18:07, Robert Craig wrote:

> 
> 
> kbochert at copper.net wrote:
> > It seems to me that given that fmod(a,b) is defined as returning a value
> > which is less than b, failure to do so is not just inaccurate but a real
> > bug.
> 
> I'm sure it *does* return a value less than b.
> But when you print a result such as 0.01 - 99 * epsilon
> to 10 significant digits, like Euphoria does by default,
> you see: 0.01
> 
Yes it does. A value is calculated that looks like .00999... which rounds to .01
But note that even with a precise decimal (extending to infinity) the result is
nearly as bad as it can be. (Given that it must be less than .01).
Whats at fault is the algorithm, which can magnify small errors into disasters.


Consider instead:
  rslt = X - floor( X/Y) * Y
Slight inaccuracies in the subtraction or multiplication leave you with small
inaccuracies in the result.
A slight inaccuracy in the division can cause the floor function to return a
value that
is (exactly) one too small, which multiplied by Y  gives a value that is Y too
small,
and subtracted from X gives a result that is exactly Y  too large, a huge error
just
like we see now.
For floor(X/Y) to produce this kind of step error requires that X/Y be very
close
to an integral value. So either X is a multiple of Y, in which case the result
can be
Y when it should be 0, or they are near values whose difference is close to the
accuracy
limits of a double (Like 111111111111 /111111111112, or some such)

So:
 rslt = X - floor (X/Y) * Y
 if (rslt == Y)
    rslt = 0

The step error can still happen, but it is confined to more uncommon cases.

> >>From a Google search:
> >  http://www.boic.com/b1mnum.pdf.  (dated Nov 3 2003 !!)
> > 
> > QUOTE:
> > Appendix 
> > Microsoft Modulo Bugs 
> > Over the years of testing of the Number Class, we've discovered nasty bugs
> > in
> > Microsoft's fmod() 
> > function, which you can easily confirm for yourself. For example, using the
> > Windows
> > 95 Calculator 
> > accessory (evidently built on the same fmod function) try this simple
> > calculation:
> > 5.5 mod 1.1 
> > Instead of giving the correct result, which should be 0, 
>  > it shows the result as 1.1.
>  > ...
> 
> This person obviously is not aware of the pitfalls of
> binary, limited-precision floating-point.
> 
> > We were unable to find any reference to this 
> > disturbing bug in the 
> > Microsoft Knowledge Base. 
> 
> Because it's not really a bug in the library.
> It's a limitation of the floating-point hardware.
> 
Exacerbated by a fragile algorithm.

> > ... For some versions, the bug did NOT appear in the calculator 
> > program, but 
> > using fmod() ALWAYS produces this bug. 
> 
> No doubt because the calculator program uses
> *decimal* floating-point, where numbers like 0.1, 0.01 etc.
> *can* be represented with perfect accuracy (but then
> lots of other numbers can't, so this is not a
> perfect solution either.)
>
Would be good for checking the results of the binary math.
 
KtB