[issue46558] Quadratic time internal base conversions

Tim Peters added the comment: > todecstr treats it as an "input" conversion instead, ... Worth pointing this out since it doesn't seem widely known: "input" base conversions are _generally_ faster than "output" ones. Working in the destination base (or a power of it) is generally simpler.

[issue46558] Quadratic time internal base conversions

Tim Peters 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: 475seconds (about 8 minutes) numeral: 22.3

[issue46558] Quadratic time internal base conversions

Carl Friedrich Bolz-Tereick added the comment: Somebody pointed me to V8's implementation of str(bigint) today: https://github.com/v8/v8/blob/main/src/bigint/tostring.cc They say that they can compute str(factorial(1_000_000)) (which is 5.5 million decimal digits) in 1.5s:

[issue46558] Quadratic time internal base conversions

Tim Peters added the comment: Addendum: the "native" time (for built in str(a)) in the msg above turned out to be over 3 hours and 50 minutes. -- ___ Python tracker ___

[issue46558] Quadratic time internal base conversions

Tim Peters added the comment: The test case here is a = (1 << 1) - 1, a solid string of 100 million 1 bits. The goal is to convert to a decimal string. Methods: native: str(a) numeral: the Python numeral() function from bpo-3451's div.py after adapting to use the Python

[issue46558] Quadratic time internal base conversions

Tim Peters added the comment: Changed the code so that inner() only references one of the O(log log n) powers of 2 we actually precomputed (it could get lost before if `lo` was non-zero but within `n` had at least one leading zero bit - now we _pass_ the conceptual width instead of

[issue46558] Quadratic time internal base conversions

Tim Peters added the comment: Dennis, partly, although that was more aimed at speeding division, while the approach here doesn't use division at all. However, thinking about it, the implementation I attached doesn't actually for many cases (it doesn't build as much of the power tree in

[issue46558] Quadratic time internal base conversions

Dennis Sweeney added the comment: Is this similar to https://bugs.python.org/issue3451 ? -- nosy: +Dennis Sweeney ___ Python tracker ___

[issue46558] Quadratic time internal base conversions

New submission from Tim Peters : Our internal base conversion algorithms between power-of-2 and non-power-of-2 bases are quadratic time, and that's been annoying forever ;-) This applies to int<->str and int<->decimal.Decimal conversions. Sometimes the conversion is implicit, like when