[issue3451] Asymptotically faster divmod and str(long)

[Pernici Mario]

Pernici Mario <pernici at users.sourceforge.net> added the comment:

In this second patch to the above patch it is added the recursive
division algorithm by Burnikel and Ziegler (BZ) 
from longobject2.diff, unmodified,
to see the effect of the subquadratic algorithm; there is still a lot of
work to be done on it, as Mark pointed out.

Here is a benchmark on hp pavilion Q8200  2.33GHz
a = 7**n; compute str(a) N times
n        N        unpatched  patch1   patch2
100      100000   0.25       0.25     0.25
200      100000   0.63       0.64     0.63
300      100000   1.19       1.22     1.23
400      100000   1.87       1.74     1.75
500      10000    0.27       0.24     0.24
1000     10000    0.98       0.59     0.60
2000     1000     0.36       0.16     0.17
5000     1000     2.17       0.65     0.66
10000    100      0.86       0.20     0.19
20000    100      3.42       0.70     0.55
50000    10       2.13       0.37     0.24
100000   1        0.85       0.13     0.08
500000   1        21         2.9      0.94
1000000  1        85         11       2.8
2000000  1        339        44       8.4

str(n) in the first patch uses a quadratic algorithm, but asymptotically
it is almost 8 times faster than the unpatched version;
in the second patch the subquadratic algorithm starts showing 
after 10000 digits.

----------
Added file: http://bugs.python.org/file13497/longformat_BZ.diff

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