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 >>> -- https://mail.python.org/mailman/listinfo/python-list
