Posts Tagged ‘logarithm’

Programming Praxis – Integer Logarithms

May 7, 2010

In today’s Programming Praxis exercise we have to write an algorithm to find the integer logarithm of a number, i.e. the largest power the base can be raised to that does not exceed the number. Let’s get started.

First, the O(n) solution, which works the same as the Scheme version.

ilog :: Integral a => a -> a -> Integer
ilog b n = if n == 0 then -1 else ilog b (div n b) + 1

For the O(log n) version, we use the until function to determine the bounds rather than using explicit recursion. Other than that, there’s not much to be had in the way of improvements.

ilognew :: (Ord a, Num a) => a -> a -> Integer
ilognew b n = f (div ubound 2) ubound where
    ubound = until (\e -> b ^ e >= n) (* 2) 1
    f lo hi | mid == lo   = if b ^ hi == n then hi else lo
            | b ^ mid < n = f mid hi
            | b ^ mid > n = f lo mid
            | otherwise   = mid
            where mid = div (lo + hi) 2

Like the Scheme solution, we check the equivalence of the two methods by testing a few different bases and the numbers 1 to a million.

main :: IO ()
main = print $ and [ilognew b n == ilog b n
                   | b <- [2,3,5,7], n <- [1..1000000]]

Only a 30% reduction in lines this time compared to the Scheme solution, since most of the code is checking conditions. Oh well, it’ll do.

Advertisements

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