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,,,,