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.

Cheers,

Carl Friedrich

Armin Rigo <arigo@tunes.org> wrote:

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.

pypy-dev mailing list

pypy-dev@python.org

http://mail.python.org/mailman/listinfo/pypy-dev