Hi Nathan, On Thu, May 30, 2013 at 6:41 PM, Nathan Hurst <njh@njhurst.com> wrote:
It doesn't have to be quadratic, it's easy to come up with a splitting algorithm:
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.
beating the builtin C implementation by a factor of 7.5 seems a reasonable outcome for pypy.
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).
I think I could come up with a linear time two pass algorithm working on intdigits if this were important to pypy.
That would be interesting for both PyPy and CPython. A bientôt, Armin.