find all multiplicands and multipliers for a number
davea at davea.name
Mon Apr 13 04:35:56 CEST 2015
On 04/12/2015 09:56 PM, Paul Rubin wrote:
> Marko Rauhamaa <marko at 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.
More information about the Python-list