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

Ryan Ingram ryani.spam at gmail.com
Fri Feb 15 12:21:52 EST 2008


On Thu, Feb 14, 2008 at 8:23 PM, Uwe Hollerbach <uhollerbach at gmail.com> 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.

This seems wrong to me; that routine should take a small constant
amount of time.  I suspect you are measuring the time to construct the
50-million bit numbers as well.  If you constructed a single number
and called this routine on it several times I am sure you would get
far different results, with the first routines taking ~7-11s each and
Stefan's GHC/GMP-magic taking almost nothing.

  -- ryan


More information about the Haskell-Cafe mailing list