
Sterling Clover wrote:
Actually, I suspect GHC's strictness analyzer will give you reasonable performance with even the naive version, but fancier ideas are at http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog
If given an 'n' you are looking for the (2^x) such that 2^x >= n > 2^(x-1) then you could use the method at http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 This does not return 'x', it returns the integer '2^x' instead. Here is my contribution:
import Data.Bits
-- Takes input Integer >=0 -- let p = roundUpPower2 r -- in assert ( ((r==0) && (p==1)) -- || (r>0) && (p>=r) && (p<2*r) -- || (r<0) && (p>=r) && (2*p
Integer roundUpPower2 r = case compare r 0 of LT -> let p' = negate (roundUpPower2 (negate r)) in if p' == r then p' else p' `div` 2 EQ -> 1 GT -> shifting (pred r) 1 where shifting !v !k | sv == 0 = succ v | otherwise = shifting (v .|. sv) (shiftL k 1) where sv = shiftR v k test = map (\r -> (r,roundUpPower2 r)) [-17..17]
check (r,p) = ((r==0) && (p==1)) || (r>0) && (p>=r) && (p<2*r) || (r<0) && (p>=r) && (2*p
main = do mapM_ print test print (all check test)