Calculating Logarithms
December 18, 2009
Our solution is based on a description by Ed Sandifer. We define epsilon
as the desired accuracy of the final result:
(define epsilon 1e-7)
Newton’s method uses an initial estimate of 1.0, then calculates a new estimate using the formula for the derivative:
(define (newton x2)
(let loop ((x 1.0))
(if (< (abs (- (* x x) x2)) epsilon) x
(loop (- x (/ (- (* x x) x2) (+ x x)))))))
The implementation of Euler’s method merges two loops into one. The first pesudo-loop, at the (< hi n)
condition, calculates the smallest power of base
greater than n
. The second pseudo-loop performs Euler’s algorithm; next
is the geometric mean, log-next
is the arithmetic mean, and the if
chooses the sub-interval of the bisection:
(define (euler base n)
(let loop ((lo 1.0) (log-lo 0.0) (hi 1.0) (log-hi 0.0))
(cond ((< hi n) (loop lo log-lo (* hi base) (+ log-hi 1)))
((< (abs (- (/ log-lo log-hi) 1)) epsilon)
(/ (+ log-lo log-hi) 2))
(else (let* ((next (newton (* lo hi)))
(log-next (/ (+ log-lo log-hi) 2)))
(if (< next n)
(loop next log-next hi log-hi)
(loop lo log-lo next log-next)))))))
Here are some sample calculations:
> (newton 2)
1.4142135623746899
> (euler 10 612)
2.7867514193058014
> (expt 10 2.7867514193058014)
611.9999959982614
You can run the code at http://programmingpraxis.codepad.org/oOdXhS7g.
[…] Praxis – Calculating Logarithms By Remco Niemeijer In today’s Programming Praxis problem we have to implement Euler’s method for calculating logarithms […]
My Haskell solution (see http://bonsaicode.wordpress.com/2009/12/18/programming-praxis-calculating-logarithms/ for a version with comments):
Mine, in Python
[…] calculated the value of pi, and logarithms to seven digits, in two previous exercises. We continue that thread in the current exercise with a function that calculates […]
I note that the approved solution calculates (- (* x x) x2)) twice. Is there some reason you don’t use a temporary?
(define (newton x2)
(let loop ((x 1.0))
(let ((t (- (* x x) x2)))
(if (< (abs t) epsilon) x
(loop (- x (/ t (+ x x))))))))
In Erlang.
Interactive Erlang session