[issue46558] Quadratic time internal base conversions

[Tim Peters]

Tim Peters <tim at python.org> added the comment:

The factorial of a million is much smaller than the case I was looking at. Here are rough timings on my box, for computing the decimal string from the bigint (and, yes, they all return the same string):

native:   475    seconds (about 8 minutes)
numeral:   22.3  seconds
todecstr:   4.10 seconds
gmp:        0.74 seconds

"They recursively split the bigint into halves using % 10^n at each recursion step". That's the standard trick for "output" conversions. Beyond that, there are different ways to try to use "fat" multiplications instead of division. The recursive splitting all on its own can help, but dramatic speedups need dramatically faster multiplication.

todecstr treats it as an "input" conversion instead, using the `decimal` module to work mostly _in_ base 10. That, by itself, reduces the role of division (to none at all in the Python code), and `decimal` has a more advanced multiplication algorithm than CPython's bigints have.

----------

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue46558>
_______________________________________