http://qs1969.pair.com?node_id=134438

in reply to Re: Help w/ Code Optimization
in thread Help w/ Code Optimization

I tried calculating the roots with logarithms, but the problem with that is that the built-in log() function is only accurate to a fixed number of places. Other than the logarithm method and Newton's method, I don't know of any other ways to calculate roots. Does anyone know how to calculate a logarithm manually? That is, calculate a logarithm without using the built-in log() function?

My C and C++ skills are virtually non-existent, so sadly, that option isn't really available to me. This might be a good time to improve those skill, eh? ;-)
___________________
Kurt

Replies are listed 'Best First'.
Re: Re: Re: Help w/ Code Optimization
by runrig (Abbot) on Dec 26, 2001 at 23:21 UTC
There's an algorithm here to compute natural logarithms to any precision. It works for me, you might have to combine it with Math::BigFloat to get the precision you want (Oh, you're already using that...)
:-)

However, I don't know if going this route is any better than your current algorithm for getting the nth root of a number...

Update: By request, here's what I did to make the algorithm in the link above work (in the Read More link at the bottom of this post). This is not a perfect implementation, I'm pretty sure I'm losing precision somewhere, and you could probably make better use of Math::BigFloat, but it seems to be on the right track. And I don't know how this compares with the other ways of finding the root of a number...

Update: Works alot better now, not losing so much precision anymore (in fact, it looks like results are accurate to the precision you specify now) :-)

Updated code to reflect new version of Math::BigFloat
Also, did some rough benchmarks computing the 60th root of 1000. "Rough," because sifukurt's algorithm specifies 'iterations' to get precision, and I specify decimal places. For 50 decimal places on mine, and for 1 of his iterations (which is lt 40 decimal places), his wins, for 2 iterations (which is slightly gt 50 decimal places), mine wins slightly, and for 3 iterations mine wins by alot (but then his is accurate to much gt 50 places). And I'm still using operator overloading, which is a speed hit (though I'm not sure how much, and so far we're both using it).
For 90 decimal places, his takes 3 iterations, and the time mine takes is right in the middle of the time his takes to do 2 or 3 of his iterations.

Re: Re: Re: Help w/ Code Optimization
by John M. Dlugosz (Monsignor) on Dec 27, 2001 at 02:12 UTC
My first thought is that logs are computed using the same concept, so it doesn't make it any faster or more accurate. However, it's always log, with other things expressed in terms of log, so that function can be optomized.

Then I realized that real libraries use a Taylor/Macloren (spelling?) series to compute log and other functions, not Newton's method. This is code tuned to the specific function, and you can't do as well with an arbitrary input function unless you input the first derivitive as well.