I tested it on version 3.12.3 and it worked just fine

I tried on a few versions of 3.12 too (on Mac) and couldn't reproduce a hang.

Did you do anything to the decimal module, forcing the use of the Python implementation?

I can reproduce a hang if I prevent the C implementation from getting used, starting with 10**9031 (with 9030 it still only takes a split second).

import sys

sys.modules['_decimal'] = None
sys.set_int_max_str_digits(0)

str(10**9031)

starting with 10**9031

That's 30001 bits, where the switch happens:

To be clear here, I strongly doubt that computing 10**10000 hangs for the OP either. @antonio-rojas, try this:

>>> import sys; sys.set_int_max_str_digits(0); x = 10**10000

I bet it will return near instantly. What can take considerable time is converting the result to a decimal string, which the code you showed implicitly does. Since you didn't bind the result to a name, an interactive shell will try to display the result, which requires converting it to a string first. So, after the above, str(x) may well appear to hang (but is actually just taking a long time to complete).

That "shouldn't" take such a long time either, but before anyone can really address this you'll need to be clear about where the "hang" is occurring (in the computation of the power, or in converting the result to a string - or possibly even that the shell you're using is actually the thing that's hanging when trying to display a string so long - can't guess which from here, because none of this takes noticeable time for me).

EDIT: on second reading, ya, it's clear enough already that the hang is in conversion to string - the power was already computed, and there's not yet a long string for a shell to display.

It's clear from OP's stacktrace that a) it's getting hung during the str conversion, b) they have frames in _pydecimal so they aren't using the C implementation

Turned out to be a packaging issue (missing mpdecimal library), sorry for the noise.

Thanks for following up! But don't be sorry - there's still a mystery here. Even if you don't have mpdecimal, core Python still ships with a pure Python implementation of that code. Did you try @pochmann3's variant?:

import sys

sys.modules['_decimal'] = None
sys.set_int_max_str_digits(0)

str(10**9031)

That forces Python to ignore the mpdecimal module. That appears to hang on my box too. I slammed in a print statement before the line in your traceback, and it displayed:

raising 10 to 1000000000000000000

That sure looks like a mistake to me, so I'm reopening this report. In fact, I think the same line in _power_exact was recently the subject of a different report (and if someone remembers which, we should probably link that report to this one, and close this again).

#118027

There is other problem with using _pydecimal to stringify integers. When it converts a 2n-bit integer to Decimal, it recursively calculates it as D(a) + D(b)*D(2**n), where a and b are only n-bit integers. But multiplication of two large Decimals is implemented in _pydecimal via calculating str(op1.int * op2.int). If both arguments are n-bit, the result of the multiplication is 2n-bit, and we are at square one, trying to stringify a 2n-bit integers. This code falls in infinite recursion.

cc @mdickinson, @tim-one

yes, now that str(huge_integer) is implemented in pure Python in _pylong.py and uses the decimal module, the C implementation in _decimal is not completely optional any more.

this was discussed here: https://discuss.python.org/t/int-str-conversions-broken-in-latest-python-bugfix-releases/18889/174

@gpshead wrote:

_pydecimal never actually gets used by anything in CPython so it no longer working in various situations with a limit enabled was considered a non-problem as there is no scenario in which the C _decimal module is not present. _pydecimal only exists as a reference / prototyping implementation within CPython at this point.

Within CPython could we make it an error for _decimal to not exist rather than blindly falling back to _pydecimal at this point. Or at least require _decimal in order for the _pylong code path to be taken?

Or at least require _decimal in order for the _pylong code path to be taken?

yes, at a minimum this seems like a good idea to me.

Whether _pydecimal should be removed maybe needs some wider discussion?

Another possiblity to address the immediate problem. This is untested, but I know the code well. In _pylong.py, just change

                result = D2**w

to

                result = D(1 << w)

Then the decimal __pow__() won't be called at all. It may even be faster that way under the C decimal implementation too, although not enough so to matter in this context. w in the above is always "small".

@serhiy-storchaka wrote:

"""
There is other problem with using _pydecimal to stringify integers. When it converts a 2n-bit integer to Decimal, it recursively calculates it as D(a) + D(b)*D(2**n), where a and b are only n-bit integers. But multiplication of two large Decimals is implemented in _pydecimal via calculating str(op1.int * op2.int). If both arguments are n-bit, the result of the multiplication is 2n-bit, and we are at square one, trying to stringify a 2n-bit integers. This code falls in infinite recursion.
"""

That's really cute 😉. If someone cares enough about _pydecimal.py to address this (as noted already, CPython doesn't use it for anything), probably most straightforward for it to implement its own, internal, simple int->str function, and use that instead of calling str(int). It would defer to str(int) for "small" ints, of course.

It requires little code. For "big" ints it will be quadratic-time, but it already was, and users who really care about speed weren't using _pydecimal anyway. I know PyPy uses it, but PyPy should also do a good job on speeding a simple Python-level str->int function.

With PyPy in mind, it would probably be best to convert the trailing N decimal digits remaining per iteration, via divmod(n, 10**N), where 10**N is a precomputed constant, the largest value that fits in a "1 digit" internal PyPy int.

Or it could use much larger powers of 10 in a fancier recursive scheme, relying on CPython's newer sub-quadratic division (which I suspect PyPy already implements internally) for speed. That's substantially trickier to code, though. At a high level, you pick a power P of 10 close to the square root of the int, use divmod(n, P) to break n into high and low pieces with about the same number of decimal digits, recursively convert each piece to a decimal string, then concatenate those strings (careful to pad the "low" string with leading zeros as needed).

But fancy schemes generally don't pay off unless the int is "very" big.

Yes, I am not an expert in fancier schemes, but this idea is pretty straightforward. I thought about it before, but it did not work while division was quadratic.

Here is a simple implementation:

def int_to_decimal_string(n):
    DECLIM = 39
    def inner(n, w):
        if w <= DECLIM:
            return str(n)
        w2 = w >> 1
        d = 10**w2
        hi, lo = divmod(n, d)
        return inner(hi, w - w2) + inner(lo, w2).zfill(w2)
    w = int(n.bit_length() * 0.3010299956639812)
    return inner(n, w)

It is even faster than the current implementation for 10**10000 (740 usec vs 1.59 msec) and 10**100000 (20.5 msec vs 39.1 msec), but slower for 10**1000000 (721 msec vs 567 msec). They are equal for 10**530000 (266 msec).

The code above used the same threshold as the current code (translated to decimals). If increase DECLIM to 1000, this improves results (694 msec for 10**1000000), and this value looks like the optimum. Increasing BITLIM in the current code also slightly improves results.

Ya! That's in the right direction. It has bugs, though. Primarily, what's "high" at one level may be "low" to its caller. Zero-padding is always needed.

But then the number of digits needs to be known exactly in advance, so that a useless '0' isn't tacked on to the front of the very leftmost piece, and there is no dirt-cheap way to compute that.

More subtly, repeated catenation introduces an O(d log d) cost, where d is the number of digits. One way to eliminate that is shown below. Another is to extend a result bytearray in-place instead.

Testing hint: set DECLIM to 1 and compare the result to str(i) for all i in, say, range(1000000).

For fine-tuning (not done here), the same powers of 10 are reused often, so it can pay some to use a pow10 wrapper that caches the results for reuse. Which powers get reused depends on the input, though, so it's best to use a fresh cache on each call (lest the cache grow without bound - on a single call it won't hold more than O(log(n)) entries).

import math
LOG10OF2 = math.log10(2)
DECLIM = 39

def int_to_decimal_string(n):
    assert n >= 0  # precondition for this specific code
    if n < 1000000: # arbitrary - really want to get rid of n==0
        return str(n)
    pieces = []
    def inner(n, w):
        if w <= DECLIM:
            pieces.append(str(n).zfill(w))
            return
        w2 = w >> 1
        hi, lo = divmod(n, 10**w2)
        inner(hi, w - w2)
        inner(lo, w2)
    # The number of decimal digits is the smallest w such that
    # n < 10**w. There is no O(1) way to compute this.
    w = int(n.bit_length() * LOG10OF2) + 1 # upper bound
    assert n <= 10**w
    while n < 10**(w-1): # usually goes around no more than once
        w -= 1
    inner(n, w)
    assert pieces and pieces[0][0] != '0'
    result = "".join(pieces)
    assert len(result) == w
    return result

We could, e.g., instead settle for the cheap upper-bound guess at the number of digits needed, and then, at the end, strip off any leading zeroes in pieces[0] (which can happen if the guess was too large).

We could, e.g., instead settle for the cheap upper-bound guess ...

Or not worry about "upper bound" at all - just get "close". Floating-point vagaries make it too annoying to try to out-think "upper bound" precisely.

import math
LOG10OF2 = math.log10(2)
DECLIM = 39

def int_to_decimal_string(n):
    assert n >= 0  # precondition for this specific code
    if n < 1000000: # arbitrary - really want to get rid of n==0
        return str(n)
    pieces = []
    def inner(n, w):
        if w <= DECLIM:
            pieces.append(str(n).zfill(w))
            return
        w2 = w >> 1
        hi, lo = divmod(n, 10**w2)
        inner(hi, w - w2)
        inner(lo, w2)
    # The number of drcimal digits is the smallest w such that n <
    # 10**w. Viewed another way, w = floor(log10(n)) + 1 if we used
    # infinite precision. There is no O(1) way to compute this.
    #
    # We don't need to be exact, though -"close" is good enough.
    # Splitting may not be optimal, but that doesn't much matter.
    # If we guess too small, no harm to the result. If we guess too
    # large, there may be leading 0's that need to be stripped.
    #
    # Where k = n.bit_length(), n < 2**k = 10**(log10(2) * k), so
    # log10(n) < log10(2) * k. Due to floating-point rounding
    # errors, though, the computed int(log10(2) * k) may be 1 too
    # small if a true result >= some int rounds to something a
    # little smaller than that int.  But it's close, and more likely
    # too large than too small (since n may be only half of 2**k).
    w = int(n.bit_length() * LOG10OF2) + 1
    inner(n, w)
    assert pieces
    result = "".join(pieces)
    return result.lstrip("0")

For those following, I explained on the linked pull request that this has significantly worse asymptotics than the code in _pylong.py, and that can't be "repaired". CPython's sub-quadratic division is limited by the asymptotics of CPython's Karatsuba multiplication, which in turn has much worse O() behavior than libmpdec's fanciest multiplication.

It's nevertheless a massive improvement over CPython's previous quadratic-time int->str.

I do not think that it has bugs. Note that zeroes padding is only added for the low part.

The only bug in my initial implementation is that it worked incorrectly for negative integers. I was not aware that it is called with negative arguments.

It turned out that values that end with many zeroes like 10**100_000 are not good for testing, because the low parts are degraded to 0. 10**100_000-1 is closer to real word data. I now use the "all nines" examples for fine tuning. It lowers the upper limit where the discussed implementation is faster than the current one to 900_000 bits.

Using cache for pow10 is a good idea. I tried several variants, and the simplest one turned out to be the best (or not worst from more sophisticated code). It makes the code ~5-10% faster in the tested range.

Using the list of chunks does not affect the performance at all. BTW, your latest variant is equal to my code before adding the pow10 cache for 10**270_000-1 and 15% slower for 10**30_000-1 (the lower limit for calling it from the C code). Your initial variant is ~2 times slower.

I think that our goal is to provide an alternate implementation that does not use Decimal to break the loop between _pydecimal and _pylong. Preferably with better than quadratic complexity. It should be used in _pydecimal, and, since it turned out to be faster than the current implementation in the middle range, it could also be used in _pylong directly, even if _decimal is present. Since it is so simple, it could even be implemented in C, this can add few tens of percent to the speed and may made some more optimizations (like using the buffer for concatenation) more viable.

I do not think that it has bugs.

My apologies! You're right. I was suffering an illusion there.

For the rest, please read my comments on your PR. I don't believe there's any need to change _pydecimal after all. At import time, _pylong can pick the new code if the C version of decimal isn't installed, else use the current code.

Please don't complicate this more than necessary to fix the problem. For example, it was very deliberate that we left these simple functions coded in Python. The inputs you're testing on are relatively tiny compared to what we actually cared about - inputs so large that people are routinely tricked into thinking CPython is stuck in an infinite loop when converting a large int. There is no end to ways various ranges could be sped up. But that's not our job. People who want peak speed should be using gmpy2 instead. We're aiming here at inputs with dozens of millions of bits.

The goals here were better asymptotics and minimal maintenance burden. Recoding in C is right out. For truly large inputs, almost all the time is spent multiplying (true even of the newer code). The Python interpreter overhead is insignificant in these cases. The new version inherits O(n**1.585) asymptotics from CPython's Karatsuba multiplication. That's an enormous improvement over quadratic time, but the current code using libmpdec is more like O(n log n) (no, it's not that good, but far better than Karatsuba).

And it's again the case that the advantage of pasting pieces together only once isn't apparent except for very large inputs - the log(d) in O(d log d) increasingly matters the larger d becomes.

To generate cases for testing, I use this when I want an input with bits bits:

hibit = 1 << (bits - 1)
lo = randrange(hibit)
n = lo + hibit
assert n.bit_length() == bits

If it's any consolation, everyone gets tricked by initially testing only on powers of 10 😉. "All 9s" can trick them in a different way: there are no zero digits at all.

Closing this. The main branch now uses a new function in _pylong.py if the C version of decimal isn't available.

#118483