Division of two longs can produce results that are needlessly inaccurate:>>> from __future__ import division>>> 10**40/10**3910.000000000000002The correct result is, of course, 10.0, which is exactly representable as a float.The attached snippet of Python code shows that things don't have to be this way.

How fast is your algorithm compared to the current algorithm and wherestarts the break even zone? Most users use only small integers so itmight be a good idea to use a simpler algorithm for longs with Py_SIZE()== 1. This is important for py3k.

It would be easy and safe to just use a/b = float(a)/float(b) if both a and b are less than 2**53 (assuming IEEE doubles).  Then there wouldn't be any loss of speed for small integers.For large integers the algorithm I posted should run in time linear in the number of digits of max(a, b), at least in the worst case (though with appropriate optimizations it could be made much faster for 'random' inputs).  The current algorithm has essentially O(1) runtime.  To get proper timings I'd have to code this up properly.  I'll do this, unless there's a consensus that it would be a waste of time :)

Mark Dickinson wrote:> To get proper timings I'd have to code this up properly.  I'll do this, unless there's > a consensus that it would be a waste of time :)Why don't you ask Tim? He is the right person for the discussion. I'monly an interested amateur mathematician.Christian

Tim:  is this worth fixing?

A related problem is that float(n) isn't always correctly rounded for an integer n.  A contrived example:>>> n = 2**68 + 2**16 - 1>>> float(n)2.9514790517935283e+20Here the difference between float(n) and the true value of n is around 0.99998 ulps;  a correctly rounded float() would have error at most 0.5 ulps.I don't regard this as terribly serious: from looking at the code, I *think* it's always true that the error is strictly less than 1 ulp, which is just enough to guarantee that float(n) == n whenever n is exactly representable as a float.In contrast, the division of two integers can produce results that are up to 3.5 ulps out from the true value.  This is, in my opinion, a worryingly large error for a simple calculation.

To my mind, the inaccurate result is a bug that should be fixed.Note: (3.0a3)>>> 10e40/10e3910.0The rationale for the division change is that (as far as reasonablypossible) arithmetic operations with same values should give same resultregardless of types.I have not looked at either algorithm, but if long/long started byfinding divmod(), but added fractional value when remainer is non-zeroinstead of tossing it, exact quotients would easily be exact (unless toolarge).

Here's a patch that fixes the rounding of integer division.  It includes a fast path for the case where both integers are small (less than about 3.5e12).

An example of a case that's almost 3.5 ulps out (Python 2.6):Python 2.6.2 (r262:71600, Jul  8 2009, 09:56:31) [GCC 4.0.1 (Apple Inc. build 5490)] on darwinType "help", "copyright", "credits" or "license" for more information.>>> from __future__ import division>>> m = 295147931372582273023>>> n = 295147932265116303360>>> m/n0.99999999697597697The correctly rounded result would be the float given by 0.9999999969759773.

Stealing this from Tim, with the intention of acting on it in the next couple of weeks.

Here's an updated patch, against py3k.  On my machine, a/b is a touch faster with this patch when abs(a), abs(b) are smaller than 1e15 or so;  it's (inevitably) slower than the existing implementation for larger a and b.  For 'random' a and b, average running time is proportional to the size of b, and is independent of the size of a;  worst-case running time (which occurs when a has many trailing zero bits) grows as max(size(a), size(b)).Changing versions to 2.7 and 3.2, but I'm mostly aiming for 3.2.  It may not be worth backporting to 2.7, given the extra effort required to deal correctly with ints as well as with longs.

Fixed inr77062 (trunk),r77063 (py3k).