Posts Tagged ‘newton’

Programming Praxis – Calculating Logarithms

December 18, 2009

In today’s Programming Praxis problem we have to implement Euler’s method for calculating logarithms (using Newton’s method for calculating square roots). Let’s get started.

First we define our desired accuracy.

eps :: Double
eps = 1e-7

Newton’s method is just repeating the same function until it’s close enough.

sqrt' :: Double -> Double
sqrt' n = head . filter (\x -> abs (x^2 - n) < eps) $
    iterate (\x -> x - (x^2 - n) / (2*x)) 1

In Euler’s algorithm we first find the smallest power of the base higher than n, and then keep calculating the geometric mean between the low and the high number, repeating for whichever of the two resulting intervals holds n until we’re close enough.

log' :: Double -> Double -> Double
log' b n = f 0 0 where
    f lo hi | b ** hi < n             = f lo (hi + 1)
            | abs (lo / hi - 1) < eps = arit
            | geom < n                = f arit hi
            | otherwise               = f lo arit
            where geom = sqrt' (b ** lo * b ** hi)
                  arit = (lo + hi) / 2

A quick test shows that everything is working correctly:

main = do print $ sqrt' 2
          print $ log' 10 612