Programming Praxis – Integer Logarithms

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.

2 Responses to “Programming Praxis – Integer Logarithms”

1. Turning Egyptian Division Into Logarithms | Site Title Says:

[…] For a I used values from 1 to 1,000,000. For b I used the values 2, 3, 5, and 7. I borrowed this testing regimen from a Bonsai Code blog entry. […]

2. Turning Egyptian Division Into Logarithms | Second Generation Programmer Says:

[…] For a I used values from 1 to 1,000,000. For b I used the values 2, 3, 5, and 7. I borrowed this testing regimen from a Bonsai Code blog entry. […]