Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!newsfeed.xs4all.nl!newsfeed4.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path: <davea@davea.name>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.063
X-Spam-Evidence: '*H*': 0.87; '*S*': 0.00; 'value,': 0.04; 'root': 0.05; 'method.': 0.07; 'subject:number': 0.09; 'conceivably': 0.16; 'operation,': 0.16; 'subject:skip:m 10': 0.16; 'wrote:': 0.18; 'trying': 0.19; 'header:User-Agent:1': 0.23; 'integer': 0.24; 'stopping': 0.24; 'paul': 0.24; 'header:In-Reply-To:1': 0.27; 'point': 0.28; '20%': 0.31; 'though.': 0.31; 'writes:': 0.31; 'subject:all': 0.32; "i'd": 0.34; 'could': 0.34; 'version': 0.36; 'doing': 0.36; 'too': 0.37; 'arrange': 0.38; 'e.g.': 0.38; 'to:addr:python-list': 0.38; 'pm,': 0.38; 'sure': 0.39; 'to:addr:python.org': 0.39; 'even': 0.60; 'around.': 0.60; 'times': 0.62; 'real': 0.63; 'charset:windows-1252': 0.65; 'close': 0.67; 'received:74.208': 0.68; 'fact,': 0.69; 'square': 0.74; 'divide': 0.84; 'subject:find': 0.84
Date: Sun, 12 Apr 2015 22:35:56 -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>
In-Reply-To: <87zj6czt84.fsf@jester.gateway.sonic.net>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
X-Provags-ID: V03:K0:WgK9L4YGyGDOG4EiZYGZZ+tZ66dLN93z3HlGQxZ7SPiCrjH0Qw6 aFx+10DHvnXC0pBOBcJMq9Rcc2RAK44tszZuozK0Oo+rEnMdijdD4leG8R3fY8OzomXJ3FM 1t4wYc6lpOUceOqH/Zt5pJOunkj5QgsdY2LZ/u9faF5yIjOCc6y6u1qfFxHlcxta6kBhsEy 7iLJycsxLZMSLqoQc4n3A==
X-UI-Out-Filterresults: notjunk:1;
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.20
Precedence: list
List-Id: General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe: <https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <http://mail.python.org/pipermail/python-list/>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups: comp.lang.python
Message-ID: <mailman.262.1428892580.12925.python-list@python.org>
Lines: 20
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1428892580 news.xs4all.nl 2873 [2001:888:2000:d::a6]:48895
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:88904

On 04/12/2015 09:56 PM, Paul Rubin wrote:
> Marko Rauhamaa <marko@pacujo.net> writes:
>> And in fact, the sqrt optimization now makes the original version 20%
>> faster: ...
>>      bound = int(math.sqrt(n))
>
> That could conceivably fail because of floating point roundoff or
> overflow, e.g. fac(3**1000).  A fancier approach to finding the integer
> square root might be worthwhile though.
>

If I were trying to get a bound for stopping the divide operation, on a 
value too large to do exact real representation, I'd try doing just a 
few iterations of Newton's method.  Even if you don't converge it to get 
an exact value, you can arrange that you have a number that's for sure 
no less than the square root.  And you can get pretty close in just a 
few times around.

-- 
DaveA