[issue3451] Asymptotically faster divmod and str(long)

[Mark Dickinson]

Mark Dickinson <dickinsm at gmail.com> added the comment:

The longobject2.diff patch probably doesn't apply cleanly any more.  
Anyone interested in updating it?

I think this patch looks like a promising beginning, but there's still 
quite a lot of work to do.  The main concerns at the moment are:

(1) the huge numbers of Py_DECREFs and Py_XDECREFs.  Some refactoring 
might help here ("goto" isn't all bad: it's fairly common to use lots of 
"goto error" statements in Python's source code).

(2) I suspect that many of the operations could be turned into in-place 
operations on digit vectors, thus saving lots of object allocations and 
deallocations.  This should also help out with (1).

I'm not yet 100% sold on getting subquadratic division into Python---it 
remains to be seen how much complexity it adds.  If it makes it easy to 
implement subquadratic integer <-> string conversions that would be a big 
plus.

----------

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue3451>
_______________________________________