On Dec 3, 2007 10:05 PM, David Benbennick
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