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 <ar...@tunes.org> wrote: >Hi Nathan, > >On Thu, May 30, 2013 at 6:41 PM, Nathan Hurst <n...@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
_______________________________________________ pypy-dev mailing list pypy-dev@python.org http://mail.python.org/mailman/listinfo/pypy-dev
