Re: [Haskell] for large x, log (x::Integer) :: Double
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?
On Mon, Jul 05, 2004 at 10:08:04AM +0100, Edmund GRIMLEY EVANS wrote:
Does Haskell provide any means of determining the number of binary digits in an Integer other than by repeated division?
See the Data.Bits library: http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data.Bits.html Peace, Dylan
Edmund GRIMLEY EVANS asks (to the Haskell mailing list):
Does Haskell provide any means of determining the number of binary digits in an Integer other than by repeated division?
Dylan Thurston answers:
See the Data.Bits library:
http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data.Bits.html
This library will let you use a shift instead of a division, but won't give you a constant time size function for Integers. Cheers, Ronny Wichers Schreur
On Mon, Jul 12, 2004 at 04:29:22PM +0200, Ronny Wichers Schreur wrote:
Edmund GRIMLEY EVANS asks (to the Haskell mailing list):
Does Haskell provide any means of determining the number of binary digits in an Integer other than by repeated division?
Dylan Thurston answers:
See the Data.Bits library:
http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data.Bits.html
This library will let you use a shift instead of a division, but won't give you a constant time size function for Integers.
You can easily get a logarithmic time size function from the shift. But did you see Data.Bits.bitsize? Peace, Dylan
On Tue, Jul 13, 2004 at 05:01:32PM +0800, Dylan Thurston wrote:
This library will let you use a shift instead of a division, but won't give you a constant time size function for Integers.
You can easily get a logarithmic time size function from the shift. But did you see Data.Bits.bitsize?
My mistake, bitSize is not useful for this purpose. Peace, Dylan
participants (3)
-
dpt＠lotus.bostoncoop.net -
Edmund GRIMLEY EVANS -
Ronny Wichers Schreur