#   This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author tim.peters mark.dickinson, martin.panter, ned.deily, rhettinger, steven.daprano, tim.peters 2016-08-17.05:17:28 -1.0 Yes <1471411048.91.0.920263162646.issue27761@psf.upfronthosting.co.za>
Content
```Noting that `floor_nroot` can be sped a lot by giving it a better starting guess.  In the context of `nroot`, the latter _could_ pass `int(x**(1/n))` as an excellent starting guess.  In the absence of any help, this version figures that out on its own; an optional `a=None` argument (to supply a starting guess, if desired) would make sense.

def floor_nroot(x, n):
"""For positive integers x, n, return the floor of the nth root of x."""

bl = x.bit_length()
if bl <= 1000:
a = int(float(x) ** (1.0/n))
else:
xhi = x >> (bl - 53)
# x ~= xhi * 2**(bl-53)
# x**(1/n) ~= xhi**(1/n) * 2**((bl-53)/n)
# Let(bl-53)/n = w+f where w is the integer part.
# 2**(w+f) is then 2**w * 2**f, where 2**w is a shift.
a = xhi ** (1.0 / n)
t = (bl - 53) / n
w = int(t)
a *= 2.0 ** (t - w)
m, e = frexp(a)
a = int(m * 2**53)
e += w - 53
if e >= 0:
a <<= e
else:
a >>= -e
# A guess of 1 can be horribly slow, since then the next
# guess is approximately x/n.  So force the first guess to
# be at least 2.  If that's too large, fine, it will be
# cut down to 1 right away.
a = max(a, 2)
a = ((n-1)*a + x // a**(n-1)) // n
while True:
d = x // a**(n-1)
if a <= d:
return a
a = ((n-1) * a + d) // n

I haven't yet found a case in the context of `nroot` where it doesn't get out on the first `if a <= d:` test.  Of course you can provoke as many iterations as you like by passing `x` with a lot more than 53 "significant" bits (the large `x` passed by `nroot` are mostly long strings of trailing 0 bits).```
History
Date User Action Args
2016-08-17 05:17:29tim.peterssetrecipients: + tim.peters, rhettinger, mark.dickinson, ned.deily, steven.daprano, martin.panter