Difference between revisions of "ILogBase"

From HaskellWiki
Jump to: navigation, search
m
 
Line 1: Line 1:
The Haskell Prelude includes logBase, a floating-point based logarithm-taking function.
+
The Haskell Prelude includes <code>logBase</code>, 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.
 
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:
+
A naive way to implement <code>logBase</code> accurately for Integral types is:
   
<pre>
 
  +
<haskell>
   
 
naiveLogBase base
 
naiveLogBase base
Line 11: Line 11:
 
| otherwise = length . takeWhile (>=base) . iterate (`div` base)
 
| otherwise = length . takeWhile (>=base) . iterate (`div` base)
   
</pre>
+
</haskell>
   
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.
   
For purposes such as digit counting, an Integral only logBase can be both accurate and fast:
+
For purposes such as digit counting, an <code>Integral</code>-only <code>logBase</code> can be both accurate and fast:
   
<pre>
 
  +
<haskell>
   
 
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>
+
</haskell>
   
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.
  +
  +
[[Category:Code]]

Latest revision as of 01:51, 14 July 2021

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.