ILogBase

From HaskellWiki
Revision as of 22:05, 3 January 2009 by Peaker (talk | contribs) (Accurate and fast Integral logBase)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

The Haskell Prelude includes logBase, a floating-point based logarithm-taking function.

Since it is floating-point based, it is limited in number sizes, and has accuracy errors that render it unusable even for simple purposes such as digit counting.

A naive way to implement logBase accurately for Integral types is:

naiveLogBase base

   | base <= 1 = error "base <= 1"
   | otherwise = length . takeWhile (>=base) . iterate (`div` base)

However, this implementation is slow, and has O(result), or O(log(n)) time complexity.

For purposes such as digit counting, an Integral only logBase can be both accurate and fast:

iLogBase :: Integral a => a -> a -> (a, a) iLogBase base n

   | base <= 1 = error "iLogBase: base <= 1"
   | n < 0 = error "iLogBase: negative n"
   | n < base = (0, n)
   | otherwise =
       let (res, remain) = iLogBase (base*base) n
           mres = res*2
           (i, r) = if remain < base
                      then (mres, remain)
                      else (mres+1, remain `div` base)
       in (i, r)

The above implementation has O(log(result)), or O(log(log(n))) time complexity.