[Haskell-cafe] bitSize

[Daniel Fischer]

On Monday 29 August 2011, 12:32:51, Maciej Marcin Piechotka wrote:
> On Fri, 2011-08-26 at 20:30 +0100, Andrew Coppin wrote:
> > 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)...
> 
> According to random side (http://gruntthepeon.free.fr/ssemath/) not so
> new computers can compute 15.5 milions of serial logarithms per second
> (62 millions in total). I'd say that overhead of Integer might be much
> bigger then cost of logarithm.

Well, converting the Integer to Double can easily take longer than 
calculating the logarithm.

The main problem with this approach, however, is that only smallish 
(cryptographically speaking) Integers can be converted to Double with 
something resembling adequate precision (above 2^1024-2^972, you'll get 
Infinity from the conversion, log is Infinity: boom).