[Haskell-cafe] How to calculate de number of digits of an
integer? (was: Is logBase right?)
Edward Kmett
ekmett at gmail.com
Sat Aug 29 21:12:27 EDT 2009
I have a version of this inside of the monoid library buried in the
Data.Ring.Semi.BitSet module:
http://comonad.com/haskell/monoids/dist/doc/html/monoids/src/Data-Ring-Semi-BitSet.html#hwm
<http://comonad.com/haskell/monoids/dist/doc/html/monoids/src/Data-Ring-Semi-BitSet.html#hwm>To
do any better by walking the raw Integer internals you need to know the
'finger' size for the GMP for your platform, which isn't possible to do
portably.
-Edward Kmett
On Wed, Aug 26, 2009 at 10:42 AM, Uwe Hollerbach <uhollerbach at gmail.com>wrote:
> Here's my version... maybe not as elegant as some, but it seems to
> work. For base 2 (or 2^k), it's probably possible to make this even
> more efficient by just walking along the integer as stored in memory,
> but that difference probably won't show up until at least tens of
> thousands of digits.
>
> Uwe
>
> ilogb :: Integer -> Integer -> Integer
> ilogb b n | n < 0 = ilogb b (- n)
> | n < b = 0
> | otherwise = (up 1) - 1
> where up a = if n < (b ^ a)
> then bin (quot a 2) a
> else up (2*a)
> bin lo hi = if (hi - lo) <= 1
> then hi
> else let av = quot (lo + hi) 2
> in if n < (b ^ av)
> then bin lo av
> else bin av hi
>
> numDigits n = 1 + ilogb 10 n
>
> [fire up ghci, load, etc]
>
> *Main> numDigits (10^1500 - 1)
> 1500
> *Main> numDigits (10^1500)
> 1501
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090829/e2b3f9ef/attachment.html
More information about the Haskell-Cafe
mailing list