This is algorithm 1.26 from the reference cited above:
from functools import lru_cache
@lru_cache
def integer_log(y: int, x: int):
r = e = 0
while y >= x:
d = x
m = 1
while y >= d:
y, rem = divmod(y, d)
r = r or rem
e += m
if y > d:
d *= d
m *= 2
return e
# Algorithm 1.26:
#@profile
def format_int(A: int, B: int = 10) -> str:
"""Format integer A as a string in base B"""
if A.bit_length() < 1000:
# Here we use str for the base case but really this should be something
# that works for arbitrary bases using the standard O(n^2) algorithm.
# The threshold should be tuned.
return str(A)
else:
# find k so that B**(2*k-2) <= A < B**(2*k)
e = integer_log(A, B)
if e % 2 == 1:
k = (e + 1) // 2
else:
k = e // 2 + 1
#assert B**(2*k - 2) <= A < B**(2*k)
Bk = B**k
Q, R = divmod(A, Bk)
r = format_int(R, B)
q = format_int(Q, B)
pad = '0'*(k - len(r))
return ''.join([q, pad, r])
Unfortunately it doesn’t seem to perform as well as algorithm 1.25 and seems to have quadratic run time. For large inputs half of the time is in divmod and half in integer_log. Improving integer_log might not be difficult but improving divmod seems harder. I’m wondering if divmod has the complexity I thought it had…