find all multiplicands and multipliers for a number

[Steven D'Aprano]

On Monday 13 April 2015 15:25, Paul Rubin wrote:

> 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.

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