Path: csiph.com!usenet.pasdenom.info!news.redatomik.org!newsfeed.xs4all.nl!newsfeed1a.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Date: Mon, 13 Apr 2015 01:43:07 -0400
From: Dave Angel <davea@davea.name>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.5.0
MIME-Version: 1.0
To: python-list@python.org
Subject: Re: find all multiplicands and multipliers for a number
References: <890bd388-f50a-4dec-9ef5-27715427472a@googlegroups.com> <mailman.209.1428714381.12925.python-list@python.org> <55288135$0$12997$c3e8da3$5496439d@news.astraweb.com> <87egnrb3il.fsf@jester.gateway.sonic.net> <87619387c0.fsf@elektro.pacujo.net> <90a8e07c-adb3-499f-8971-4ea49f6aea4b@googlegroups.com> <87lhhx7r44.fsf@elektro.pacujo.net> <87zj6czt84.fsf@jester.gateway.sonic.net> <mailman.262.1428892580.12925.python-list@python.org> <87vbh0zow3.fsf@jester.gateway.sonic.net> <mailman.263.1428899720.12925.python-list@python.org> <87r3rozjjp.fsf@jester.gateway.sonic.net>
In-Reply-To: <87r3rozjjp.fsf@jester.gateway.sonic.net>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.265.1428903800.12925.python-list@python.org>
Lines: 49
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:88911

On 04/13/2015 01:25 AM, Paul Rubin wrote:
> Dave Angel <davea@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