[Haskell] for large x, log (x::Integer) :: Double

Edmund GRIMLEY EVANS do_not_use at yahoo.co.uk
Mon Jul 5 05:08:04 EDT 2004


Dylan Thurston:

> For those who aren't aware: working with logs base 2 internally will
> be very much faster than logs base 10, since the numbers are stored
> internally in a base-2 representation.  (Note that 'show' converts to
> base 10, which involves a large number of divisions in the easy
> algorithm.)

Does Haskell provide any means of determining the number of binary
digits in an Integer other than by repeated division? In the absence
of an appropriate built-in or library function it may be that the
fastest way is to use (length (show x)), multiply by some fiddle
factor, add some fiddle term to get n, then check whether x < 2 ** n.

Could "log2 :: Integer -> Integer" be added to some wish list?


More information about the Haskell mailing list