find all multiplicands and multipliers for a number
Dave Angel
davea at davea.name
Mon Apr 13 07:43:07 CEST 2015
On 04/13/2015 01:25 AM, 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.
Well that value x has some 3300 digits, and I seem to recall that float
only can handle 10**320 or so. But if the point of all this is to
decide when to stop dividing, I think our numbers here are somewhere
beyond the heat death of the universe.
Thus (not completely tested):
>
> def isqrt(x):
> def log2(x): return math.log(x,2) # python 2 compatibility
> if x < 1e9:
Now 10**9 is way below either limit of floating point. So i still don't
know which way you were figuring it. Just off the top of my head, I
think 10**18 is approx when integers don't get exact representation, and
10**320 is where you can't represent numbers as floats at all.
> 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.
>
If you're willing to use the 10**320 or whatever it is for the limit, I
don't see what's wrong with just doing floating point sqrt. Who cares
if it can be an exact int, since we're just using it to get an upper limit.
And I can't figure out your code at this hour of night, but it's much
more complicated than Newton's method would be anyway.
--
DaveA
More information about the Python-list
mailing list