[Haskell-cafe] Looking for largest power of 2 <= Integer
Dan Piponi
dpiponi at gmail.com
Tue Dec 4 13:48:03 EST 2007
On Dec 3, 2007 10:05 PM, David Benbennick <dbenbenn at gmail.com> wrote:
> Could you please post your code here when you're done? I'd be
> interested to see the final result.
This is just experimental code I'm playing with in order to implement
exact real arithmetic, so there'll never be a "final" result :-) But
this is what I'm currently playing with. It's hard-coded for a
platform with 64 bit Ints and 64 bit "limbs" of Integers. This is my
first ever foray into the binary underbelly of Haskell, using
information from
http://www.haskell.org/ghc/docs/4.06/users_guide/ghc-libs-ghc.html,
and I've probably written this code really stupidly.
import GHC.Exts
import Data.Bits
fastTestBit :: Integer -> Int -> Bool
fastTestBit n i = case n of
S# m -> testBit (I# m) i
J# l d -> let I# w = shiftR i 6
b = i .&. 63
in testBit (I# (indexIntArray# d w)) b
-- Assumes n/=0
topBit :: Integer -> Int
topBit n = case n of
S# m -> topBit' n 63
J# l _ -> topBit' n (64*I# l-1)
where
topBit' n i = if fastTestBit n i then i else topBit' n (i-1)
I don't need something super-fast (ie. clever bit twiddling tricks),
just something not stupidly slow. Despite what dons says, testBit is
stupidly slow :-) fastTestbit takes microseconds instead of seconds on
2^10000000. Maybe a portable tidied up version of fastTestBit ought to
go into Data.Bits. These kinds of operations are ubiquitous in
numerical algorithms.
And note the fixed title :-)
--
Dan
More information about the Haskell-Cafe
mailing list