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