gh-118164: Break a loop between _pydecimal and _pylong and optimize int to str conversion (GH-118483)

For converting large ints to strings, CPython invokes a function in _pylong.py,
which uses the decimal module to implement an asymptotically waaaaay
sub-quadratic algorithm. But if the C decimal module isn't available, CPython
uses _pydecimal.py instead. Which in turn frequently does str(int). If the int
is very large, _pylong ends up doing the work, which in turn asks decimal to do
"big" arithmetic, which in turn calls str(big_int), which in turn ... it can
become infinite mutual recursion.

This change introduces a different int->str function that doesn't use decimal.
It's asymptotically worse, "Karatsuba time" instead of quadratic time, so
still a huge improvement. _pylong switches to that when the C decimal isn't
available. It is also used for not too large integers (less than 450_000 bits),
where it is faster (up to 2 times for 30_000 bits) than the asymptotically
better implementation that uses the C decimal.

Co-authored-by: Tim Peters <tim.peters@gmail.com>

1 files changed, 4 insertions, 0 deletions

diff --git a/Misc/NEWS.d/next/Core and Builtins/2024-05-02-15-57-07.gh-issue-118164.AF6kwI.rst b/Misc/NEWS.d/next/Core and Builtins/2024-05-02-15-57-07.gh-issue-118164.AF6kwI.rst
new file mode 100644
index 0000000..5eb3b6f
--- /dev/null
+++ b/Misc/NEWS.d/next/Core and Builtins/2024-05-02-15-57-07.gh-issue-118164.AF6kwI.rst
@@ -0,0 +1,4 @@
+Break a loop between the Python implementation of the :mod:`decimal` module
+and the Python code for integer to string conversion. Also optimize integer
+to string conversion for values in the range from 9_000 to 135_000 decimal
+digits.