On Monday 13 April 2015 15:25, Paul Rubin wrote: > Dave Angel <da...@davea.name> writes: >> But doesn't math.pow return a float?... >> Or were you saying bignums bigger than a float can represent at all? >> Like: >>>>> x = 2**11111 -1 ... >>>>> math.log2(x) >> 11111.0 > > Yes, exactly that. Thus (not completely tested): > > def isqrt(x): > def log2(x): return math.log(x,2) # python 2 compatibility > if x < 1e9: > return int(math.ceil(math.sqrt(x))) > a,b = divmod(log2(x), 1.0) > c = int(a/2) - 10 > d = (b/2 + a/2 - c + 0.001) > # now c+d = log2(x)+0.001, c is an integer, and > # d is a float between 10 and 11 > s = 2**c * int(math.ceil(2**d)) > return s > > should return slightly above the integer square root of x. This is just > off the top of my head and maybe it can be tweaked a bit. Or maybe it's > stupid and there's an obvious better way to do it that I'm missing.
Check the archives: I started a thread last November titled "Challenge: optimizing isqrt" which is relevant. Also: http://code.activestate.com/recipes/577821-integer-square-root-function/ -- Steve -- https://mail.python.org/mailman/listinfo/python-list
