find all multiplicands and multipliers for a number

[Paul Rubin]

Dave Angel <davea at 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.