integer nth roots for arbitrary sized integer

[jzakiya at gmail.com]

FYI for people who need this.

I was looking here

http://www.codecodex.com/wiki/Calculate_an_integer_square_root

for an efficient/fast algorithm for computing integer squareroots.

Based on one of the C version examples, I think this is the most efficient/fastest that always produces correct results for arbitrary sized integers.

>>> def isqrt(n):
...   root, bitn_mask = 0, (1 << (n.bit_length() // 2 + 1))
...   while bitn_mask != 0:
...     root |= bitn_mask
...     if (root * root) > n: root ^= bitn_mask
...     bitn_mask >>= 1
...   return root
... 
>>> n = 10**35; isqrt(n)
316227766016837933
>>> n = 10**111
>>> isqrt(n)
31622776601683793319988935444327185337195551393252168268L
>>> n = 10**110; isqrt(n)
10000000000000000000000000000000000000000000000000000000L
>>> n = 10**210; isqrt(n)
1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000L
>>> n = 10**211; isqrt(n)
3162277660168379331998893544432718533719555139325216826857504852792594438639238221344248108379300295187347L

With a small modification, the algorithm will find the exact integer nth root for arbitrary sized integers.

>>> def irootn(num, n):
...   root, bitn_mask = 0, (1 << (num.bit_length() // n + 1))
...   while bitn_mask != 0:
...     root |= bitn_mask
...     if root**n  > num: root ^= bitn_mask
...     bitn_mask >>= 1
...   return root
... 
>>> n = 10**35; isqrt(n)
316227766016837933
>>> n = 10**35; irootn(n, 2)
316227766016837933
>>> n = 10**39; irootn(n, 2)
31622776601683793319L
>>> n = 10**39; irootn(n, 3)
10000000000000
>>> n = 10**39; irootn(n, 4)
5623413251
>>> n = 10**144; irootn(n, 2)
1000000000000000000000000000000000000000000000000000000000000000000000000L
>>> n = 10**144; irootn(n, 3)
1000000000000000000000000000000000000000000000000L
>>> n = 10**144; irootn(n, 4)
1000000000000000000000000000000000000L
>>> n = 10**144; irootn(n, 6)
1000000000000000000000000L
>>> n = 10**144; irootn(n, 8)
1000000000000000000
>>> n = 10**144; irootn(n, 11)
12328467394420
>>> n = 10**144; irootn(n, 12)
1000000000000
>>>