[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