ILogBase
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.