Space leak in to2sComplement

[dom]

The space leak is actually in to2scomplement. The culprit is reverse - obvious once you think about it. 2^{(106) used to almost destroy my machine and anything bigger actually did grind it to a complete standstill.}

to2sComplement :: Num a => Integer -> [a] to2sComplement n | n >= 0 = 0:(k 7 n) | otherwise = k 8 (fromInteger $ 2^{p + n) where p = length (k 7 (-n-1)) + 1 infixr 5 $$ ($$) = (.).(.) k :: Num a => Integer -> Integer -> [a] k = reverse $$ (map fromInteger) $$ flip (curry (unfoldr nnbIterator)) nnbIterator :: (Integer, Integer) -> Maybe (Integer, (Integer, Integer)) nnbIterator (0,0) = Nothing nnbIterator (0,p) = Just (0,(0,p-1)) nnbIterator (n,0) = Just (n rem 2,(n quot 2,7)) nnbIterator (n,p) = Just (n rem 2,(n quot 2,p-1))}

OTOH this seems to run in log space (which you might expect) consuming about 200k for 2^{(106) (a 300k digit number) which doesn't seem unreasonable.}

This puts more emphasis on changing to use the BitPut? monad. I think it should be straightforward to make the change now everything is monadic. I'll have a look at what's involved but first I want to get the inter-operability testing framework working.

h' :: Integer -> Integer -> BitPut? h' p 0 = do putNBits (fromIntegral p) (0::Word8) h' 0 n = do putNBits 1 (n mod 2) h' 7 (n div 2) h' p n = do putNBits 1 (n mod 2) h' (p-1) (n div 2) to2sComplementReverse :: Integer -> BitPut? to2sComplementReverse n | n >= 0 = do h' 7 n putNBits 1 (0::Word8) | otherwise = h' 8 (2^{(l n) + n) l n = genericLength ((flip (curry (unfoldr nnbIterator)) 7) (-n-1)) + 1 to2sComplementUsingReverse :: Integer -> BL.ByteString? to2sComplementUsingReverse n = BL.reverse (BL.map reverseBits (runBitPut (to2sComplementReverse n)))}

reverseBits :: Word8 -> Word8 reverseBits = reverseBits3 . reverseBits2 . reverseBits1 reverseBits1 :: Word8 -> Word8 reverseBits1 x = shiftR x 4 .|. shiftL x 4 reverseBits2 :: Word8 -> Word8 reverseBits2 x = shiftR (x .&. 0xcc) 2 .|. shiftL (x .&. 0x33) 2 reverseBits3 :: Word8 -> Word8 reverseBits3 x = shiftR (x .&. 0xaa) 1 .|. shiftL (x .&. 0x55) 1