[Haskell-cafe] fast integer base-2 log function?

[Stefan O'Rear]

On Thu, Feb 14, 2008 at 08:23:29PM -0800, Uwe Hollerbach wrote:
> Stefan's routine is, as expected, much much faster still: I tested the
> first two routines on numbers with 5 million or so bits and they took
> ~20 seconds of CPU time, whereas I tested Stefan's routine with
> numbers with 50 million bits, and it took ~11 seconds of CPU time. The
> limitation of Stefan's routine is of course that it's limited to base
> 2 -- it is truly a bit-length routine -- and I guess another potential
> limitation is that it uses GHC extensions, not pure Haskell (at least
> I had to compile it with -fglasgow-exts). But it's the speed king if
> those limitations aren't a problem!

At the risk of stating the obvious, it also hard-codes 32 bit words and
certain configurable (but nobody bothers) details of the GMP data
representation (big endian, 0 nails).

Stefan
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20080214/2126afcc/attachment.bin