[Python-Dev] Floor division

Tim Peters tim.peters at gmail.com
Fri Jan 26 04:28:03 CET 2007


[Armin Rigo]
>> Thanks for the clarification.  Yes, it makes sense that __mod__,
>> __divmod__ and __floordiv__ on float and decimal would eventually follow
>> the same path as for complex (where they make even less sense and
>> already raise a DeprecationWarning).

[Nick Maclaren]
> Yes.  Though them not doing so would also make sense.  The difference
> is that they make no mathematical sense for complex, but the problems
> with float are caused by floating-point (and do not occur for the
> mathematical reals).
>
> There is an argument for saying that divmod should return a long
> quotient and a float remainder,

It could, but who would have a (sane) use for a possibly 2000-bit quotient?

> which is what C99 has specified for remquo (except that it requires
> only the last 3 bits of the quotient for reasons that completely baffle
> me).

C99 has no integral type capable of representing the full quotient,
but the last few bits may suffice for performing argument reduction in
the implementation of a periodic function.  Surely you did that for
trig functions in the bad old days?  For example, express input x as
N*(pi/2) + r, where |r| <= pi/4.  Then N can be expressed as 4*n1 +
n2, with n2 in [0, 1, 2, 3], and:

    cos(x) =
    cos((4*n1+n2)*(pi/2) + r) =
    cos(n1*(2*pi) + n2*pi/2 + r) =  [can ignore integral multiples of 2*pi]
    cos(n2*pi/2 + r)

Then the combination of n2 and the sign of r tell you which quadrant
you're in, and various cos-specific rules can deliver the result from
that and cos(r) or sin(r).

The point is that only the last 2 bits of the quotient are needed to
determine n2, and all other bits in N are irrelevant to the result.

> Linux misimplemented that the last time I looked.
>
> Personally, I think that it is bonkers, as it is fiendishly expensive
> compared to its usefulness - especially with Decimal!

Ah, but the IBM spec weasels out:  it raises an exception if you try
to compute "remainder" or "remainder-near" of inputs when the
exponents differ by "too much".

This is a bit peculiar to me, because there are ways to compute
"remainder" using a number of operations proportional to the log of
the exponent difference.  It could be that people who spend their life
doing floating point forget how to work with integers ;-)

For example, what about 9e99999 % 3.14?

    9e99999 = q*3.14 + r

if and only if (multiplying both sides by 100)

    9e100001 = 314*q + 100*r

So what's mod(9 * 10**100001, 314)?  Binary-method modular
exponentiation goes fast:

>>> pow(10, 100001, 314)
148
>>> _ * 9 % 314
76

So

9e100001 = 314*q + 76

exactly for some integer q, so (dividing both sides by 100)

9e99999 = 3.14*q + 0.76

exactly for the same integer q.  Done.  It doesn't require 100000
long-division steps, it only requires about two dozen modular
multiplications wrt the relatively tiny modulus 314.

OTOH, I don't know how to get the last bit of `q` with comparable
efficiency, and that's required to implement the related
"remainder-near" in "halfway cases".

> But it isn't obviously WRONG.

For floats, fmod(x, y) is exactly congruent to x modulo y -- I don't
think it's possible to get more right than exactly right ;-)


More information about the Python-Dev mailing list