# Ticket #27 (new defect)

Opened 8 years ago

## Space leak in to2sComplement

Reported by: | dom | Owned by: | somebody |
---|---|---|---|

Priority: | major | Milestone: | |

Component: | component1 | Version: | |

Keywords: | Cc: |

### Description

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

mod2) h' 7 (ndiv2) h' p n = do putNBits 1 (nmod2) h' (p-1) (ndiv2) 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

**Note:**See TracTickets for help on using tickets.