Pernici Mario <pern...@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 <rep...@bugs.python.org> <http://bugs.python.org/issue3451> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com