Sent to Carl only by mistake, I'm still getting the hang of this newfangled email thing... Carl said

Armin said

...

No, precisely my point: this argument is bogus. The proof that it's wrong is that CPython gets very similar timing results! Your pure Python version outperforms the C str(long) in a very similar way on PyPy and on CPython! The "bug" is originally in CPython, for having a str() that is too slow, and I just copied it into PyPy. The pure Python version you posted is faster. Its speed is roughly the same on CPython and on PyPy because most of the time is spent doing divmod on large "long" objects (which is this post's original point).

divmod in principle can be done in O(multiplication log* n), which for large numbers can be O(n log n). I don't know whether py*'s implemention does this. How do you determine where the bottlenecks are?

...

I believe that you're right on one point and wrong on another. You're right in that this gives a faster algo for str(). You're wrong in that it's still quadratic. If 'a' has 2N digits and 'b' has N digits, then divmod(a,b) is quadratic --- takes time proportional to N*N. It can be shown by measuring the time spent by your algo to do the repr of larger and larger numbers.

For what it's worth, the time for str(long) / time for recursive algorithm does decrease steadily for increasing input lengths. But it's not n^2 / n log n. Perhaps we need to implement a faster divmod? Can I assume that bit_length() is O(1)? I checked Knuth last night, he doesn't have anything to say in the main text, but he says in exercises: (II.4.4) 14. [M27] (A. Schonhage.) The text's method of converting multiple-precision integers requires an execution time of order n^2 to convert an n-place integer, when n is large. Show that it is possible to convert n-digit decimal integers into binary notation in O(M(n)logn) steps, where M(n) is an upper bound on the number of steps needed to multiply n-bit binary numbers that satisfies the “smoothness condition” M(2n) >= 2M(n). 15. [M47] Can the upper bound on the time to convert large integers, given in exercise 14, be substantially lowered? which fits my intuition. I'm fairly sure that my (and bokr's) algorithm is O(M(n)logn). It also suggests I'm wrong about a linear time algorithm (though the question doesn't state either way, but given it's M47 hardness, I'm probably not going to be able to whip this up tonight :) Lloyd Allison observed that changing any bit can affect any digits, which makes beating n log n less likely. One of the main reasons I use python is because it lets me concentrate on the higher level algorithms (like haskell), but it is pragmatic about the way we tend to write programs (unlike haskell :). I doubt I could have written that algorithm in C before breakfast (as I did for the python version). But to the main point: is it fair for people to compare code which doesn't get the benefit of pypy? Yes it is. Because the majority of code out there today is going to have C calls. Sure, pypy will lose on those, but that provides incentive to fix the problem - for example, implementing a better long to string. People are going to write silly benchmarks and they are going to solve problems in silly ways. We should be honest about this in the benchmarks. Don't worry, pypy will do just fine. On Fri, May 31, 2013 at 12:01:27PM +0200, Carl Friedrich Bolz wrote:

Hi Armin,

I have only glanced at the code, but isn't the right argument of the divmod always a power of two? So it can be replaced by a shift and a mask, giving the right complexity.

No, it's a power of 10, 10^2^i in fact. njh

Cheers,

Carl Friedrich

----- End forwarded message -----