# Difference between revisions of "ILogBase"

From HaskellWiki

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) |
||

− | </ |
+ | </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 |
+ | 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) |
||

− | </ |
+ | </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.