nth root

[Steve Holden]

Mark Dickinson wrote:
> On Jan 31, 5:43 am, "Tim Roberts" <t.robe... at cqu.edu.au> wrote:
>> Dan,
>>
>> Thanks - you're probably right - just my intuition said to me that rather than calculating that the 13th root of 4021503534212915433093809093996098953996019232
>> is 3221.2904208350265....
>> there must be a quicker way of finding out its between 3221 and 3222....
>>
>> ....but perhaps not.
> 
> I don't think you'll find anything much quicker than n**(1./13)
> (though I hope
> that if you're doing this millions of time then you're precomputing
> the 1./13
> rather than redoing the division every single time.
> 
Compared with the computation involved in the power computation I think
you'll find this makes a negligible difference in timing. But that's
just mu gut instinct, and we both know that a benchmark is the only way
to be certain, right? It just seems like a possibly premature
optimization to me. [sigh. I had to start this, didn't i?]

>>> t1 = timeit.Timer("x =
4021503534212915433093809093996098953996019232**(1.0/13)")
>>> t2 = timeit.Timer("x =
4021503534212915433093809093996098953996019232**power", "power=1.0/13")
>>> t1.timeit()
1.4860000610351562
>>> t2.timeit()
1.3789999485015869
>>>

Hmm, well, I suppose an 9% speed gain might be worth it.


> What happens behind the scenes here is that your integer is
> immediately
> converted to a float, then the system math library is used for the
> power operation.  The integer -> float conversion is probably quite
> significant, timewise.
> 
I bow to your superior intuition!

> I'd also be a bit worried about accuracy.   Is it important to you
> that the
> integer part of the result is *exactly* right, or is it okay if
> (n**13)**(1./13) sometimes comes out as slightly less than n, or if
> (n**13-1)**(1./13) sometimes comes out as n?
> 
Much more significant points, given the limited precision of the doubles
Python will be using. Could gmpy do this better, I wonder?

regards
 Steve
-- 
Steve Holden        +1 571 484 6266   +1 800 494 3119
Holden Web LLC              http://www.holdenweb.com/