[Haskell-cafe] bitSize
Daniel Fischer
daniel.is.fischer at googlemail.com
Fri Aug 26 22:37:25 CEST 2011
On Friday 26 August 2011, 21:30:02, Andrew Coppin wrote:
> You wouldn't want to know how many bits you need to store on disk to
> reliably recreate the value? Or how many bits of randomness you need to
> compute a value less than or equal to this one?
>
> I suppose I could use a binary logarithm. I'm just concerned that it
> would be rather slow. After all, I'm not interested in the exact
> logarithm (which is fractional), just the number of bits (which is a
> small integer)...
As of GHC-7.2, there's GHC.Integer.Logarithms in both, integer-gmp and
integer-simple, providing
integerLog2# :: Integer -> Int#
(integer-* lives before base, so there's no Int yet) which exploits the
representation of Integers and should be fast enough [at least for
integer-gmp, where it's bounded time for normally represented values, the
representation of Integers in integer-simple forces it to be O(log n)].
Caution: integerLog2# expects its argument to be positive, havoc might
ensue if it isn't.
GHC.Float exports
integerLogBase :: Integer -> Integer -> Int
also before 7.2, now it calls the above if the base is 2, so should have
decent performance. (It requires that the base is > 1 and the second
argument positive, of course.)
More information about the Haskell-Cafe
mailing list