id	summary	reporter	owner	description	type	status	priority	milestone	component	version	resolution	keywords	cc
27	Space leak in to2sComplement	dom	somebody	"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
"	defect	new	major		component1