Difference between revisions of "ILogBase"
Jump to navigation
Jump to search
(Accurate and fast Integral logBase) |
|||
Line 5: | Line 5: | ||
A naive way to implement logBase accurately for Integral types is: |
A naive way to implement logBase accurately for Integral types is: |
||
− | < |
+ | <pre> |
naiveLogBase base |
naiveLogBase base |
||
Line 11: | Line 11: | ||
| otherwise = length . takeWhile (>=base) . iterate (`div` base) |
| otherwise = length . takeWhile (>=base) . iterate (`div` base) |
||
− | </ |
+ | </pre> |
However, this implementation is slow, and has O(result), or O(log(n)) time complexity. |
However, this implementation is slow, and has O(result), or O(log(n)) time complexity. |
||
Line 17: | Line 17: | ||
For purposes such as digit counting, an Integral only logBase can be both accurate and fast: |
For purposes such as digit counting, an Integral only logBase can be both accurate and fast: |
||
− | < |
+ | <pre> |
iLogBase :: Integral a => a -> a -> (a, a) |
iLogBase :: Integral a => a -> a -> (a, a) |
||
Line 32: | Line 32: | ||
in (i, r) |
in (i, r) |
||
− | </ |
+ | </pre> |
The above implementation has O(log(result)), or O(log(log(n))) time complexity. |
The above implementation has O(log(result)), or O(log(log(n))) time complexity. |
Revision as of 22:21, 3 January 2009
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.