find all multiplicands and multipliers for a number

Dave Angel davea at
Mon Apr 13 04:35:56 CEST 2015

On 04/12/2015 09:56 PM, Paul Rubin wrote:
> Marko Rauhamaa <marko at> 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.


More information about the Python-list mailing list