Natürliche Zahlen, Addition

• Darstellung

  type Digit = Word64 ; data N = Z | C Digit N
  

• Semantik

  value :: N -> Natural 
  value Z = 0 ; value (C x xs) = x + 2^64 * value xs
  

• Rechnung

  instance Num N where (+) = plus_carry False
  plus_carry :: Bool -> N -> N -> N
  plus_carry cin (C x xs) (C y ys) = 
    let z = bool 0 1 cin + x + y 
        cout = z < x || z < y || ...
    in  C z (plus_carry cout xs ys)
  plus_carry ...