Bug in % (Float)?

ruby-talk
1

Modulo should be a fairly simple operation, however I'm finding some very
odd results and am wondering what is going on... For instance:

irb(main):001:0> 1 % 0.1
=> 0.1

Shouldn't 1 % 0.1 be 0.0 and not 0.1? Also, look at the following example:

irb(main):002:0> a = 1
=> 1
irb(main):003:0> b = 0.1
=> 0.1
irb(main):004:0> a += (a % b) if ((a % b) > 0)
=> 1.1
irb(main):005:0> a += (a % b) if ((a % b) > 0)
=> 1.2
irb(main):006:0> a += (a % b) if ((a % b) > 0)
=> 1.3
irb(main):007:0> a += (a % b) if ((a % b) > 0)
=> 1.4
irb(main):008:0> a += (a % b) if ((a % b) > 0)
=> 1.5
irb(main):009:0> a += (a % b) if ((a % b) > 0)
=> 1.59999999999999

Something is seriously messed up here... Of course, if you do the following:

irb(main):024:0> a = 1
=> 1
irb(main):025:0> b = 0.1
=> 0.1
irb(main):026:0> a += ((a * 100) % (b * 100)) if (((a * 100) % (b * 100)) >
0)
=> nil
irb(main):027:0> a
=> 1

Everything works as expected (at least as *I* expect it to work). So, can
anybody tell me what's going on here? Are things really broken, or am I just
expecting the wrong results?

Thanks,
Charlie

2

Hi Charlie,

I really don't like floats. That's because some things only machines
understand.

For further reading check
* http://en.wikipedia.org/wiki/Modulo_operation
* http://en.wikipedia.org/wiki/Floor_function (especially: The operator
(int) in C)

Regards
Florian

3

As Florian says, the problem is inherent with floating point values. The Python docs have a good section which explains how 0.1 cannot be represented as a binary fraction:

http://docs.python.org/tut/node16.html

Ruby just uses your systems C functions (fmod in this case) to do these calculations and they show the same behavior:

[alexg@powerbook]/Users/alexg/Desktop(209): cat test.c
#include <math.h>
#include <stdio.h>

int main(){
   printf("fmod of 1 / 0.1 is %lf\n",fmod(1,0.1));
   return 0;
}
[alexg@powerbook]/Users/alexg/Desktop(210): gcc -lm test.c -o modtest
[alexg@powerbook]/Users/alexg/Desktop(211): ./modtest
fmod of 1 / 0.1 is 0.100000

Alex Gutteridge

Bioinformatics Center
Kyoto University

···

On 30 Aug 2007, at 09:02, Charlie Lehardy wrote:

So, can anybody tell me what's going on here? Are things really broken, or am I just
expecting the wrong results?

Thanks,
Charlie

4

I think you've found a bug. Defining a modulo operator for floats is a little tricky. Consider

n, d = 1.0, 0.1
q, r = 1.0.divmod(0.1) # => [9.0, 0.1]
n == q * d + r # => true

So the answer you're getting satisfies the basic invariant imposed by division. But it should also satisfy the additional constraint that r.abs be minimal, and it fails there.

Regards, Morton

···

On Aug 29, 2007, at 8:02 PM, Charlie Lehardy wrote:

Modulo should be a fairly simple operation, however I'm finding some very
odd results and am wondering what is going on... For instance:

irb(main):001:0> 1 % 0.1
=> 0.1

5

# irb(main):001:0> 1 % 0.1
# => 0.1

···

From: Charlie Lehardy [mailto:charlie.lehardy@gmail.com] :
#
# Shouldn't 1 % 0.1 be 0.0 and not 0.1?

never trust floats in division :slight_smile:
ruby tries to be friendly at the expense of more surprises...

irb(main):343:0> system "qri numeric.divmod | head -7"
--------------------------------------------------------- Numeric#divmod
     num.divmod( aNumeric ) -> anArray
------------------------------------------------------------------------
     Returns an array containing the quotient and modulus obtained by
     dividing num by aNumeric. If q, r = x.divmod(y), then

         q = floor(float(x)/float(y))
=> true

irb(main):345:0> 1.divmod 0.1
=> [9, 0.1]
irb(main):347:0> 9*0.1+0.1
=> 1.0

:frowning:

you can use Rational instead (or BigDecimal, see below),

irb(main):358:0> x=Rational(1,1)
=> Rational(1, 1)
irb(main):360:0> y=Rational(1,10)
=> Rational(1, 10)
irb(main):361:0> r = x % y
=> Rational(0, 1)
irb(main):362:0> puts r
0
=> nil

# Also, look at the
# following example:
# irb(main):009:0> a += (a % b) if ((a % b) > 0)
# => 1.59999999999999

again, do not put all your trust in floats or in machines for that matter :slight_smile:

irb(main):344:0> 1.5.divmod 0.1
=> [14, 0.0999999999999999]

this time, let us use BigDecimal.

irb(main):369:0> require 'bigdecimal'
=> true
irb(main):375:0* x=BigDecimal.new "1.5"
=> #<BigDecimal:b7adfacc,'0.15E1',8(8)>
irb(main):376:0> y=BigDecimal.new "0.1"
=> #<BigDecimal:b7adb904,'0.1E0',4(8)>
irb(main):377:0> r = x%y
=> #<BigDecimal:b7ad7dcc,'0.0',4(16)>
irb(main):378:0> puts r
0.0
=> nil
irb(main):379:0> q,r = x.divmod(y)
=> [#<BigDecimal:b7accaa8,'0.15E2',4(12)>, #<BigDecimal:b7accb0c,'0.0',4(16)>]
irb(main):380:0> puts q, r
0.15E2
0.0
=> nil

BigDecimal is powerful, Rational is less heavy.
Your choice though.

kind regards -botp

6

Floats are not very well suited for modulo operations. Btw, here's
why you probably see 0.1:

irb(main):001:0> (1 % 0.1) - 0.1
=> -5.55111512312578e-17

You should probably read up a bit on numeric issues with floating
point arithmetic. See also other postings for explanations.

Kind regards

robert

···

2007/8/30, Charlie Lehardy <charlie.lehardy@gmail.com>:

Modulo should be a fairly simple operation, however I'm finding some very
odd results and am wondering what is going on... For instance:

irb(main):001:0> 1 % 0.1
=> 0.1

7

From: Charlie Lehardy [mailto:charlie.lehardy@gmail.com] :
# irb(main):001:0> 1 % 0.1
# => 0.1
#
# Shouldn't 1 % 0.1 be 0.0 and not 0.1?

never trust floats in division :slight_smile:
ruby tries to be friendly at the expense of more surprises...

irb(main):343:0> system "qri numeric.divmod | head -7"
--------------------------------------------------------- Numeric#divmod
     num.divmod( aNumeric ) -> anArray
------------------------------------------------------------------------
     Returns an array containing the quotient and modulus obtained by
     dividing num by aNumeric. If q, r = x.divmod(y), then

         q = floor(float(x)/float(y)

irb(main):345:0> 1.divmod 0.1
=> [9, 0.1]

If Numeric#divmod adhered to the above, the result would be [10.0, 0.0], so the result is just plain wrong, not a matter of float inaccuracy. Proof:

x, y = 1.0, 0.1
(x/y).floor.to_f # => 10.0

irb(main):347:0> 9*0.1+0.1
=> 1.0

Regards, Morton

···

On Aug 29, 2007, at 10:14 PM, Peña, Botp wrote:

8

Yes, but if you use modf, you DO get the correct result. And ruby only
uses fmod if it's available and uses modf instead. However,
considering that modf is returning the incorrect results (and fmod
returns the correct ones), maybe it shouldn't be used?

For example, to build upon your C code:

scott9:mms$ cat test.c
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char * argv) {
  double div, mod, x, y, z;
  x = 1.0;
  y = 0.1;

  if (argc > 1) x = atof(argv[1]);
  if (argc > 2) y = atof(argv[2]);

  modf(x/y, &z);
  mod = x - z * y;

  printf("fmod of %lf / %lf is %lf\n", x, y, fmod(x, y));
  printf("modf of %lf / %lf is %lf\n", x, y, mod);
  return 0;
}
scott9:mms$ gcc -lm test.c -o modtest
scott9:mms$ ./modtest
fmod of 1.000000 / 0.100000 is 0.100000
modf of 1.000000 / 0.100000 is -0.000000
scott9:mms$ ./modtest 5 0.5
fmod of 5.000000 / 0.500000 is 0.000000
modf of 5.000000 / 0.500000 is 0.000000
scott9:mms$ ./modtest 1 0.5
fmod of 1.000000 / 0.500000 is 0.000000
modf of 1.000000 / 0.500000 is 0.000000

I also thought I'd throw in that example of 0.5 as the divisor too (it
works properly in Ruby too).

Anyway, what's the reasoning for preferring to use fmod over modf? If
it's simply a performance reason, isn't giving correct results
preferable to having a bit of speed increase?

Lastly, if floats are so problematic, why even use them in these sorts
of operations? Why not have flo_mod convert to a decimal first
(multiply by some factor of 10) and then divide the by that factor
again? Or again, maybe flodivmod should just use modf since it appears
to work properly?

Thanks Again,
Charlie

···

On 8/29/07, Alex Gutteridge <alexg@kuicr.kyoto-u.ac.jp> wrote:

As Florian says, the problem is inherent with floating point values.
The Python docs have a good section which explains how 0.1 cannot be
represented as a binary fraction:

http://docs.python.org/tut/node16.html

Ruby just uses your systems C functions (fmod in this case) to do
these calculations and they show the same behavior:

[alexg@powerbook]/Users/alexg/Desktop(209): cat test.c
#include <math.h>
#include <stdio.h>

int main(){
   printf("fmod of 1 / 0.1 is %lf\n",fmod(1,0.1));
   return 0;
}
[alexg@powerbook]/Users/alexg/Desktop(210): gcc -lm test.c -o modtest
[alexg@powerbook]/Users/alexg/Desktop(211): ./modtest
fmod of 1 / 0.1 is 0.100000

9

Mathematically, division goes as follows:

  given a dividend n, a divisor d, the quotient q and remainder r are
defined as follows:

    n = q * d + r
    0 <= r < d

The only number required to be integer to make the solution to the
equations unique is q.

In floating point arithmetic, the first equation is approximately
true, usually in as close a way as possible in a certain sense. The
second equation is strictly adhered to, you can check:

  irb(main):001:0> 1.0 % 0.1 < 0.1
  => true

As for the equation given by ri, it's not intended to be evaluated by
Ruby (note how you needed to change where you put the floor function.)
Since 0.1 is represented by a float float(0.1) that is slightly larger
than 0.1, and 1.0 i represented exactly by float(1.0), float(1.0) /
float(0.1) will be slightly smaller than 10 in exact arithmetic,
rounding down gives 9.

Peter

···

On 30/08/2007, Morton Goldberg <m_goldberg@ameritech.net> wrote:

On Aug 29, 2007, at 10:14 PM, Peña, Botp wrote:

> From: Charlie Lehardy [mailto:charlie.lehardy@gmail.com] :
> # irb(main):001:0> 1 % 0.1
> # => 0.1
> #
> # Shouldn't 1 % 0.1 be 0.0 and not 0.1?
>
> never trust floats in division :slight_smile:
> ruby tries to be friendly at the expense of more surprises...
>
> irb(main):343:0> system "qri numeric.divmod | head -7"
> ---------------------------------------------------------
> Numeric#divmod
> num.divmod( aNumeric ) -> anArray
> ----------------------------------------------------------------------
> --
> Returns an array containing the quotient and modulus obtained by
> dividing num by aNumeric. If q, r = x.divmod(y), then
>
> q = floor(float(x)/float(y)
>
> irb(main):345:0> 1.divmod 0.1
> => [9, 0.1]

If Numeric#divmod adhered to the above, the result would be [10.0,
0.0], so the result is just plain wrong, not a matter of float
inaccuracy. Proof:

x, y = 1.0, 0.1
(x/y).floor.to_f # => 10.0

> irb(main):347:0> 9*0.1+0.1
> => 1.0

10

# On Aug 29, 2007, at 10:14 PM, Peña, Botp wrote:
# >Returns an array containing the quotient and modulus
# >obtained by dividing num by aNumeric. If q, r = x.divmod(y),
# >then
# > q = floor(float(x)/float(y)
# >
# > irb(main):345:0> 1.divmod 0.1
# > => [9, 0.1]
# > irb(main):347:0> 9*0.1+0.1
# > => 1.0

···

From: Morton Goldberg [mailto:m_goldberg@ameritech.net]
#
# If Numeric#divmod adhered to the above, the result would be [10.0,
# 0.0], so the result is just plain wrong, not a matter of float
# inaccuracy. Proof:
#
# x, y = 1.0, 0.1
# (x/y).floor.to_f # => 10.0

indeed, that is the effect you are testing. what i'm saying is that,

A. result of q from q,r=x.divmod(y)
   may _not (always) guarantee that q == (x/y).floor

B. there are too many results of that kind above, so inferred this
   is not plain ruby algo error.
   see,

irb(main):069:0> (0.5/0.1).floor
=> 5
irb(main):070:0> 0.5.divmod(0.1)
=> [4, 0.1]
irb(main):071:0> (0.6/0.1).floor
=> 5
irb(main):072:0> 0.6.divmod(0.1)
=> [5, 0.1]
irb(main):073:0> (0.7/0.1).floor
=> 6
irb(main):074:0> 0.7.divmod(0.1)
=> [6, 0.0999999999999999]
irb(main):075:0> (1.2/0.1).floor
=> 11
irb(main):076:0> 1.2.divmod(0.1)
=> [11, 0.0999999999999999]
irb(main):077:0> (1.3/0.1).floor
=> 13
irb(main):078:0> 1.3.divmod(0.1)
=> [12, 0.1]

i checked divmod second value is same as modulo result (fr which i based my previous statement to not trust float division; of course, i may be wrong). so i reckon, ruby gets modulo first, then generate q by q=(num-r)/div. Thus ruby can only guarantee num = q*div + r. (maybe modulo is wrong, and the documentation can be wrong too). i think.

i'm sorry. i tend to generalize. i don't read ruby source. correct me if i'm wrong, pls.

kind regards -botp

11

You are correct I think. In numeric.c, flo_divmod (Float#divmod) and flo_mod (Float#%) both call flodivmod which calls fmod to generate the modulo and then calculates q as you say.

Alex Gutteridge

Bioinformatics Center
Kyoto University

···

On 30 Aug 2007, at 16:46, Peña, Botp wrote:

i checked divmod second value is same as modulo result (fr which i based my previous statement to not trust float division; of course, i may be wrong). so i reckon, ruby gets modulo first, then generate q by q=(num-r)/div. Thus ruby can only guarantee num = q*div + r. (maybe modulo is wrong, and the documentation can be wrong too). i think.

i'm sorry. i tend to generalize. i don't read ruby source. correct me if i'm wrong, pls.

kind regards -botp

12

From: Charlie Lehardy [mailto:charlie.lehardy@gmail.com] :
# irb(main):001:0> 1 % 0.1
# => 0.1
#
# Shouldn't 1 % 0.1 be 0.0 and not 0.1?

never trust floats in division :slight_smile:
ruby tries to be friendly at the expense of more surprises...

irb(main):343:0> system "qri numeric.divmod | head -7"
---------------------------------------------------------
Numeric#divmod
     num.divmod( aNumeric ) -> anArray
----------------------------------------------------------------------
--
     Returns an array containing the quotient and modulus obtained by
     dividing num by aNumeric. If q, r = x.divmod(y), then

         q = floor(float(x)/float(y)

irb(main):345:0> 1.divmod 0.1
=> [9, 0.1]

If Numeric#divmod adhered to the above, the result would be [10.0,
0.0], so the result is just plain wrong, not a matter of float
inaccuracy. Proof:

x, y = 1.0, 0.1
(x/y).floor.to_f # => 10.0

irb(main):347:0> 9*0.1+0.1
=> 1.0

I going to be stubborn about this.

Mathematically, division goes as follows:

  given a dividend n, a divisor d, the quotient q and remainder r are
defined as follows:

    n = q * d + r
    0 <= r < d

The only number required to be integer to make the solution to the
equations unique is q.

No, that only holds for _integer_ division. For fields (e.g., real numbers), division is defined as the inverse of multiplication. For computer floats, which are neither integers nor form a field, defining a modulo operator is tricky (as I said in previous post). But it can be done better than Ruby is doing it.

A reasonable definition for a float modulo would be:

def m_mod_n(m, n)
    m - n * m.quo(n)
end

With this definition

m_mod_n(1.0, 0.1) # => 0.0

In floating point arithmetic, the first equation is approximately
true, usually in as close a way as possible in a certain sense. The
second equation is strictly adhered to, you can check:

  irb(main):001:0> 1.0 % 0.1 < 0.1
  => true

As for the equation given by ri, it's not intended to be evaluated by
Ruby (note how you needed to change where you put the floor function.)
Since 0.1 is represented by a float float(0.1) that is slightly larger
than 0.1, and 1.0 i represented exactly by float(1.0), float(1.0) /
float(0.1) will be slightly smaller than 10 in exact arithmetic,
rounding down gives 9.

As your example demonstrates, that's a bad algorithm and should not be used.

Regards, Morton

···

On Aug 30, 2007, at 3:39 AM, Calamitas wrote:

On 30/08/2007, Morton Goldberg <m_goldberg@ameritech.net> wrote:

On Aug 29, 2007, at 10:14 PM, Peña, Botp wrote:

13

>>
>>> From: Charlie Lehardy [mailto:charlie.lehardy@gmail.com] :
>>> # irb(main):001:0> 1 % 0.1
>>> # => 0.1
>>> #
>>> # Shouldn't 1 % 0.1 be 0.0 and not 0.1?
>>>
>>> never trust floats in division :slight_smile:
>>> ruby tries to be friendly at the expense of more surprises...
>>>
>>> irb(main):343:0> system "qri numeric.divmod | head -7"
>>> ---------------------------------------------------------
>>> Numeric#divmod
>>> num.divmod( aNumeric ) -> anArray
>>> --------------------------------------------------------------------
>>> --
>>> --
>>> Returns an array containing the quotient and modulus
>>> obtained by
>>> dividing num by aNumeric. If q, r = x.divmod(y), then
>>>
>>> q = floor(float(x)/float(y)
>>>
>>> irb(main):345:0> 1.divmod 0.1
>>> => [9, 0.1]
>>
>> If Numeric#divmod adhered to the above, the result would be [10.0,
>> 0.0], so the result is just plain wrong, not a matter of float
>> inaccuracy. Proof:
>>
>> x, y = 1.0, 0.1
>> (x/y).floor.to_f # => 10.0
>>
>>> irb(main):347:0> 9*0.1+0.1
>>> => 1.0

I going to be stubborn about this.

> Mathematically, division goes as follows:
>
> given a dividend n, a divisor d, the quotient q and remainder r are
> defined as follows:
>
> n = q * d + r
> 0 <= r < d
>
> The only number required to be integer to make the solution to the
> equations unique is q.

No, that only holds for _integer_ division. For fields (e.g., real
numbers), division is defined as the inverse of multiplication. For
computer floats, which are neither integers nor form a field,
defining a modulo operator is tricky (as I said in previous post).
But it can be done better than Ruby is doing it.

That definition works (i.e. it defines q and r uniquely) for real
numbers too, provided that q is required to be integer. But that was
not my point, my point was that the condition that r.abs should be
minimal is not the usual one.

A reasonable definition for a float modulo would be:

def m_mod_n(m, n)
    m - n * m.quo(n)
end

With this definition

m_mod_n(1.0, 0.1) # => 0.0

This returns 0.0 for m_mod_n(1.0, 0.3) too. Is that the intention?

> In floating point arithmetic, the first equation is approximately
> true, usually in as close a way as possible in a certain sense. The
> second equation is strictly adhered to, you can check:
>
> irb(main):001:0> 1.0 % 0.1 < 0.1
> => true
>
> As for the equation given by ri, it's not intended to be evaluated by
> Ruby (note how you needed to change where you put the floor function.)
> Since 0.1 is represented by a float float(0.1) that is slightly larger
> than 0.1, and 1.0 i represented exactly by float(1.0), float(1.0) /
> float(0.1) will be slightly smaller than 10 in exact arithmetic,
> rounding down gives 9.

As your example demonstrates, that's a bad algorithm and should not
be used.

The ideal for floating point arithmetic is that the operations are
performed in real arithmetic (floating point numbers are a subset of
real numbers, so that's an exact operation), and the result is then
taken to be the floating point number closest to the real result.
That's what the expression given by ri expresses, and I don't think
you can really ask for anything better. In Ruby 0.1 really is
0.10000000000000000555 as that is the floating point number closest to
0.1, and it doesn't fit 10 whole times in 1.0. This has nothing to do
with the algorithm used.

Peter

···

On 30/08/2007, Morton Goldberg <m_goldberg@ameritech.net> wrote:

On Aug 30, 2007, at 3:39 AM, Calamitas wrote:
> On 30/08/2007, Morton Goldberg <m_goldberg@ameritech.net> wrote:
>> On Aug 29, 2007, at 10:14 PM, Peña, Botp wrote:

14

A reasonable definition for a float modulo would be:

def m_mod_n(m, n)
    m - n * m.quo(n)
end

With this definition

m_mod_n(1.0, 0.1) # => 0.0

This returns 0.0 for m_mod_n(1.0, 0.3) too. Is that the intention?

My bad. Confused #quo with #div. Should have written

def m_mod_n(m, n)
    m - n * m.div(n)
end

m_mod_n(1.0, 0.1) # => 0.0
m_mod_n(1.0, 0.2) # => 0.0
m_mod_n(1.0, 0.3) # => 0.1
m_mod_n(1.0, 0.4) # => 0.2
m_mod_n(1.0, 0.5) # => 0.0
m_mod_n(1.0, 0.6) # => 0.4
m_mod_n(1.0, 0.7) # => 0.3
m_mod_n(1.0, 0.8) # => 0.2
m_mod_n(1.0, 0.9) # => 0.1

and tested before posting.

<snip>

I don't think you can really ask for anything better.

The above def suggests I can. I'm not saying it's a plug-in replacement for %, but it shows that a better answer can be obtained for the case in question.

In Ruby 0.1
really is 0.10000000000000000555 as that is the floating point
number closest to 0.1 ...

That's true ...

... and it doesn't fit 10 whole times in 1.0. This has nothing to do
with the algorithm used.

... but Ruby appears to think otherwise

    sprintf("%.25f", 1.0/0.1) # => "10.0000000000000000000000000"

causing me to conclude something is amiss in the % operator algorithm.

Regards, Morton

···

On Aug 30, 2007, at 5:56 PM, Calamitas wrote:

15

From what I can gather from the source code for the numeric, it is
using C's fmod (from math.h) to do the actual calculation and THAT
function is "broken" (see
http://www.ruby-doc.org/doxygen/1.8.4/numeric_8c-source.html for the
source code. Relevant portions are at lines 646 through 705).

However (as I've noted before), modf DOES work and if we were to set
the define for HAVE_FMOD to 0 instead of 1 at compile time, that code
would be used and (from what I can tell) % would work properly.

The more I look at this problem, the more confused I get though.
Sadly, this is my first real experience with floats where I've noticed
that they are not so precise. So I'm still trying to catch up a bit.

Charlie

···

On 8/31/07, Morton Goldberg <m_goldberg@ameritech.net> wrote:

That's true ...

> ... and it doesn't fit 10 whole times in 1.0. This has nothing to do
> with the algorithm used.

... but Ruby appears to think otherwise

    sprintf("%.25f", 1.0/0.1) # => "10.0000000000000000000000000"

causing me to conclude something is amiss in the % operator algorithm.

16

> I don't think you can really ask for anything better.

The above def suggests I can. I'm not saying it's a plug-in
replacement for %, but it shows that a better answer can be obtained
for the case in question.

But what is better? I think we disagree on that.

> In Ruby 0.1
> really is 0.10000000000000000555 as that is the floating point
> number closest to 0.1 ...

That's true ...

> ... and it doesn't fit 10 whole times in 1.0. This has nothing to do
> with the algorithm used.

... but Ruby appears to think otherwise

    sprintf("%.25f", 1.0/0.1) # => "10.0000000000000000000000000"

causing me to conclude something is amiss in the % operator algorithm.

But that is a different question...

It seems to me that you are looking for a way to make % and / obey a
mathematical equation that is true for reals but that simply isn't for
floats. You can change the definitions of % and / slightly to obey the
rule you want it to obey (although I'm not entirely sure that your
"fix" works in general,) but you can't change it to satisfy all
mathematical equations that are true for reals, and any change
probably makes other calculations more imprecise.

I can understand your feeling though. You expect 1.0 % 0.1 to be 0.0
and you get 0.1, which is a big difference, a lot bigger than the one
between 0.1 and 0.10000000000000000555. This is a consequence of the
fact that % is a discontinuous function. Any discontinuous function is
dangerous in floating point arithmetic, but only when used near its
discontinuities. The only general solution to this is either not to
use discontinuous functions near their discontinuities, or take into
account the large imprecision. This is really a well-understood
problem. It's not the algorithm used that is the problem, it's the
question asked that is the problem.

Regards,
Peter

···

On 31/08/2007, Morton Goldberg <m_goldberg@ameritech.net> wrote:

On Aug 30, 2007, at 5:56 PM, Calamitas wrote:

17

I don't think you can really ask for anything better.

The above def suggests I can. I'm not saying it's a plug-in
replacement for %, but it shows that a better answer can be obtained
for the case in question.

But what is better? I think we disagree on that.

When there are two methods for performing a computation, the better one is the one that produces the more accurate result. When floats are involved that means the method which produces the result closer to what one would get with the real numbers they are meant to imitate.

In Ruby 0.1
really is 0.10000000000000000555 as that is the floating point
number closest to 0.1 ...

That's true ...

... and it doesn't fit 10 whole times in 1.0. This has nothing to do
with the algorithm used.

... but Ruby appears to think otherwise

    sprintf("%.25f", 1.0/0.1) # => "10.0000000000000000000000000"

causing me to conclude something is amiss in the % operator algorithm.

But that is a different question.

It's the question I'm focused on, and the question I believe the OP was bringing up.

It seems to me that you are looking for a way to make % and / obey a
mathematical equation that is true for reals but that simply isn't for
floats. You can change the definitions of % and / slightly to obey the
rule you want it to obey (although I'm not entirely sure that your
"fix" works in general,) but you can't change it to satisfy all
mathematical equations that are true for reals, and any change
probably makes other calculations more imprecise.

I'm only talking about % here. I don't think / is an issue. I think issue revolves around the discontinuity of % and the inability of a binary floating-point number system to represent numbers such as 1/10 exactly.

I can understand your feeling though. You expect 1.0 % 0.1 to be 0.0
and you get 0.1, which is a big difference, a lot bigger than the one
between 0.1 and 0.10000000000000000555. This is a consequence of the
fact that % is a discontinuous function.

The discontinuity of % is certainly at the root of the problem, but ...

Any discontinuous function is
dangerous in floating point arithmetic, but only when used near its
discontinuities. The only general solution to this is either not to
use discontinuous functions near their discontinuities, or take into
account the large imprecision. This is really a well-understood
problem. It's not the algorithm used that is the problem, it's the
question asked that is the problem.

...this is where we differ. I believe the % algorithm should take the points of discontinuity into account and tread very carefully in their neighborhoods.

Regards, Morton

···

On Aug 31, 2007, at 8:57 PM, Calamitas wrote:

On 31/08/2007, Morton Goldberg <m_goldberg@ameritech.net> wrote:

On Aug 30, 2007, at 5:56 PM, Calamitas wrote:

18

>>> I don't think you can really ask for anything better.
>>
>> The above def suggests I can. I'm not saying it's a plug-in
>> replacement for %, but it shows that a better answer can be obtained
>> for the case in question.
>
> But what is better? I think we disagree on that.

When there are two methods for performing a computation, the better
one is the one that produces the more accurate result. When floats
are involved that means the method which produces the result closer
to what one would get with the real numbers they are meant to imitate.

OK, I agree with you. But you can only reasonably do that in every
step of the calculation. First, you need to represent 0.1 as a
floating point number and it ends up slightly larger. Then, you do the
% operation, but because the number turned out slightly larger
previously, it no longer fits 10 times and 1.0 % 0.1 returns something
slightly smaller than 0.1. The only way according to your rule above
that it can return 0.0 as you want it to is if the history of the
calculation is taken into account, but that is practically infeasible
for a general purpose language. You get errors along each step of the
calculation, and 1.0 % 0.1 is really two steps: approximate 0.1 by the
closest floating point number (done at parse time), and that is
0.10000000000000000555, and then you do 1.0 % 0.10000000000000000555
which is 1.0 - 9 * 0.10000000000000000555 = 0.09999999999999995004
because 1.0 - 10 * 0.10000000000000000555 (in real arithmetic) is
-5.55e-17 and negative. What Ruby does is as close to real number
arithmetic as you can get *in every step of the calculation*. The
whole calculation is the programmer's responsibility.

>>> In Ruby 0.1
>>> really is 0.10000000000000000555 as that is the floating point
>>> number closest to 0.1 ...
>>
>> That's true ...
>>
>>> ... and it doesn't fit 10 whole times in 1.0. This has nothing to do
>>> with the algorithm used.
>>
>> ... but Ruby appears to think otherwise
>>
>> sprintf("%.25f", 1.0/0.1) # => "10.0000000000000000000000000"
>>
>> causing me to conclude something is amiss in the % operator
>> algorithm.
>
> But that is a different question.

It's the question I'm focused on, and the question I believe the OP
was bringing up.

> It seems to me that you are looking for a way to make % and / obey a
> mathematical equation that is true for reals but that simply isn't for
> floats. You can change the definitions of % and / slightly to obey the
> rule you want it to obey (although I'm not entirely sure that your
> "fix" works in general,) but you can't change it to satisfy all
> mathematical equations that are true for reals, and any change
> probably makes other calculations more imprecise.

I'm only talking about % here. I don't think / is an issue. I think
issue revolves around the discontinuity of % and the inability of a
binary floating-point number system to represent numbers such as 1/10
exactly.

With all due respect, but when I explained why 1.0 % 0.1 turns out
different from 0.0, you had to admit I was correct but your counter
argument was that 1.0 / 0.1 is *exactly* 10.0 in Ruby.

> I can understand your feeling though. You expect 1.0 % 0.1 to be 0.0
> and you get 0.1, which is a big difference, a lot bigger than the one
> between 0.1 and 0.10000000000000000555. This is a consequence of the
> fact that % is a discontinuous function.

The discontinuity of % is certainly at the root of the problem, but ...

> Any discontinuous function is
> dangerous in floating point arithmetic, but only when used near its
> discontinuities. The only general solution to this is either not to
> use discontinuous functions near their discontinuities, or take into
> account the large imprecision. This is really a well-understood
> problem. It's not the algorithm used that is the problem, it's the
> question asked that is the problem.

...this is where we differ. I believe the % algorithm should take the
points of discontinuity into account and tread very carefully in
their neighborhoods.

OK, but it does. Ruby is right in saying that 1.0 % 0.1 is 0.1, with
the first 0.1 being slightly larger than the real 0.1, and the second
one being slightly smaller. And the fact that you can find an
algorithm that gives 0.0 as you expect doesn't make that the correct
result. I can give you an algorithm that calculates 1.0 but ends up
with 0.0 instead, and using only + and -, but that doesn't make 1.0
and 0.0 equal.

The question you ask Ruby is what 1.0 % 0.1 is. That's near a
discontinuity in %. You know that there is an error in representing
0.1, and it can go either side of the discontinuity. As it turns out,
it goes on the wrong side of the discontinuity as far as you are
concerned, but from the point of view of Ruby, that side has the
closest floating point number.

Can you accept that Ruby does % as an atomic operation as well as
possible? Your algorithm uses 4 atomic operations (Float#div is
apparently not an atomic operation, even though I found this in the
change log: "div" should return x.divmod(x)[0]) and the errors happen
to cancel each other out for the cases you've tested. That's good, and
if that's the behavior you want in your algorithms, then you should
use it, but for the sake of doing every atomic calculation as well as
possible, it's bad.

Peter

···

On 01/09/07, Morton Goldberg <m_goldberg@ameritech.net> wrote:

On Aug 31, 2007, at 8:57 PM, Calamitas wrote:
> On 31/08/2007, Morton Goldberg <m_goldberg@ameritech.net> wrote:
>> On Aug 30, 2007, at 5:56 PM, Calamitas wrote:

19

OK, I agree with you. But you can only reasonably do that in every
step of the calculation. First, you need to represent 0.1 as a
floating point number and it ends up slightly larger. Then, you do the
% operation, but because the number turned out slightly larger
previously, it no longer fits 10 times and 1.0 % 0.1 returns something
slightly smaller than 0.1. The only way according to your rule above
that it can return 0.0 as you want it to is if the history of the
calculation is taken into account, but that is practically infeasible
for a general purpose language. You get errors along each step of the
calculation, and 1.0 % 0.1 is really two steps: approximate 0.1 by the
closest floating point number (done at parse time), and that is
0.10000000000000000555, and then you do 1.0 % 0.10000000000000000555
which is 1.0 - 9 * 0.10000000000000000555 = 0.09999999999999995004
because 1.0 - 10 * 0.10000000000000000555 (in real arithmetic) is
-5.55e-17 and negative. What Ruby does is as close to real number
arithmetic as you can get *in every step of the calculation*.

You may be right, but I am not convinced. That is, I believe there might be a way to order the calculation so that in general the errors cancel rather than reinforce.

The question you ask Ruby is what 1.0 % 0.1 is. That's near a
discontinuity in %. You know that there is an error in representing
0.1, and it can go either side of the discontinuity. As it turns out,
it goes on the wrong side of the discontinuity as far as you are
concerned, but from the point of view of Ruby, that side has the
closest floating point number.

The question is: can Ruby's POV be changed to agree with mine? :slight_smile: I understand that you are arguing that it can't.

Can you accept that Ruby does % as an atomic operation as well as
possible?

Not yet. I have submitted the problem to Wolfram Research tech support. There is nobody I have access to who knows more about numerics than they do. I am waiting on their answer.

Regards, Morton

···

On Sep 1, 2007, at 7:50 AM, Calamitas wrote:

20

You may be right, but I am not convinced. That is, I believe there
might be a way to order the calculation so that in general the errors
cancel rather than reinforce.

Sure. That's what every numerical algorithm designer tries to do. But
it is far from easy to do in general, and I am not at all sure if it
is really possible to have the errors cancel in every case. But even
if it is possible, figuring out what the best order is will likely be
very expensive to do programmatically and thus not suited for a
general purpose language.

BTW, I just found an example where your m_mod_n function still gives
the "wrong" result.

  1.0 / 3125.0 == 0.00032 # => true
  m_mod_n(1.0, 0.00032) # => 0.000319999999999876

In this case, 1.0 / 0.00032 is not exactly 3125.0, i.e., / does not
counter the approximation of 0.00032 anymore.

> The question you ask Ruby is what 1.0 % 0.1 is. That's near a
> discontinuity in %. You know that there is an error in representing
> 0.1, and it can go either side of the discontinuity. As it turns out,
> it goes on the wrong side of the discontinuity as far as you are
> concerned, but from the point of view of Ruby, that side has the
> closest floating point number.

The question is: can Ruby's POV be changed to agree with mine? :slight_smile: I
understand that you are arguing that it can't.

You can change Ruby's POV, sure. It depends on what you want. The best
result for every atomic operation, or the best result overall. The
latter sounds ideal, but I don't believe it can be done in general.
(If you can do that, I'm pretty sure you'll be famous.) The former is
something that can be done and that I believe modern processors'
floating point units do or try to do. It does req

···

On 01/09/07, Morton Goldberg <m_goldberg@ameritech.net> wrote:

On Sep 1, 2007, at 7:50 AM, Calamitas wrote:

> Can you accept that Ruby does % as an atomic operation as well as
> possible?

Not yet. I have submitted the problem to Wolfram Research tech
support. There is nobody I have access to who knows more about
numerics than they do. I am waiting on their answer.

Regards, Morton