Big Numbers: Addition, Subtraction, And Multiplication
May 31, 2011
In the previous exercise, we decided on a representation for big numbers and wrote some simple functions concerning them. In today’s exercise we look at addition, subtraction, and multiplication. We will use the standard grade-school algorithms; there are better ways to do multiplication, but it’s best to get something working first, and maybe later we can improve it.
The trick with all of these functions is to handle the sign separately from the arithmetic. Consider addition. If you want to calculate a + b = c, you must first figure out which of |a| + |b|, |a| − |b|, or |b| − |a| is equal to |c|, perform the appropriate arithmetic, then attach the appropriate sign. Likewise subtraction, except that the result may have fewer big-digits than either input, so you have to be careful to remove redundant leading zeros from the result. Multiplication is simpler; the result is positive if the signs are the same, otherwise negative.
For addition, the arithmetic is done by iterating over the big-digits from least to most significant, adding the two big-digits in each position and carrying to the next position any excess over the digit base. Since the carry is always either 0 or 1, it is not possible for a single carry to propagate beyond the next big-digit (though several big-digit sums may incur carries in succession). In those cases where the addition is done by subtraction, the carry (in grade-school they called it borrow) is either 0 or -1, and it may indeed propagate to multiple big-digits (think of decimal 1000 − 1, where the borrow propagates three positions).
Subtraction is done by changing the sign and calling the function for addition, in order to eliminate the need for duplicating code.
Multiplication is only a little bit harder. The grade-school method forms partial products for each big-digit, and adds all the partial products at the end, but it is easier to add the partial products at each big-digit. The carry may be greater than 1, but it is still true that a single carry cannot propagate beyond the next big-digit.
Your task is to write functions that perform big number addition, subtraction and multiplication. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
My Haskell solution (see http://bonsaicode.wordpress.com/2011/05/31/programming-praxis-big-numbers-addition-subtraction-and-multiplication/ for a version with comments):
instance Num BigNum where a@(B l1 ds1) + b@(B l2 ds2) = B (length ds * signum l) ds where B l _ = if abs b > abs a then b else a ds = f 0 $ (if abs b > abs a then flip else id) (prep $ if signum l1 == -signum l2 then (-) else (+)) ds1 ds2 prep op (x:xs) (y:ys) = op (toInteger x) (toInteger y) : prep op xs ys prep _ xs ys = map toInteger $ xs ++ ys f r (x:xs) = let (d,m) = divMod (r + x) base in fromIntegral m : f d xs f r [] = if r == 0 then [] else [fromIntegral r] (B l1 ds1) * (B l2 ds2) = B (signum l1 * signum l2 * sl) sds where B sl sds = sum $ mult ds1 ds2 mult (x:xs) (y:ys) = fromIntegral (toInteger x * toInteger y) : map shift (mult xs (y:ys)) ++ map shift (mult [x] ys) mult _ _ = [] shift (B l ds) = B (l + 1) (0 : ds)My Scheme solution:
; Some utilities (define (push el li) (append li (list el))) (define (bignum-sign bignum) (sign (car bignum))) (define (sign num) (cond ((positive? num) 1) ((negative? num) -1) (else 0))) (define (bignum-plus a b radix) (define (add a b) (let loop ((num1 (cdr a)) (num2 (cdr b)) (carry 0) (res '())) (if (and (null? num1) (null? num2)) (let ((tres (if (> carry 0) (push carry res) res))) (cons (length tres) tres)) (let ((t (+ carry (if (null? num1) 0 (car num1)) (if (null? num2) 0 (car num2))))) (loop (if (null? num1) num1 (cdr num1)) (if (null? num2) num2 (cdr num2)) (quotient t radix) (push (remainder t radix) res)))))) (define (sub a b) (let loop ((num1 (cdr a)) (num2 (cdr b)) (carry 0) (res '())) (if (null? num1) (cons (length res) res) (let ((t (+ (car num1) (if (null? num2) 0 (- (car num2))) carry))) (loop (cdr num1) (if (null? num2) num2 (cdr num2)) (if (negative? t) -1 0) (push (+ t (if (negative? t) radix 0)) res)))))) (cond ((and (bignum-negative? a) (bignum-negative? b)) (bignum-negate (add (bignum-negate a) (bignum-negate b)))) ((bignum-negative? b) (if (bignum-gt? (bignum-abs a) (bignum-abs b)) (sub a b) (bignum-negate (sub (bignum-negate b) (bignum-negate a))))) ((bignum-negative? a) (bignum-negate (bignum-plus (bignum-negate a) (bignum-negate b) radix))) (else (add a b)))) (define (bignum-minus a b radix) (bignum-plus a (bignum-negate b) radix)) (define (bignum-times-int bignum num radix) (if (zero? num) (int->bignum 0 radix) (let loop ((rest (cdr bignum)) (res '()) (carry 0)) (if (null? rest) (let ((tres (if (zero? carry) res (push carry res)))) (cons (length tres) tres)) (let ((t (+ (* (car rest) num) carry))) (loop (cdr rest) (push (remainder t radix) res) (quotient t radix))))))) (define (bignum-times a b radix) (define (shift-left bignum k) (let loop ((res (cdr bignum)) (k k)) (if (zero? k) (cons (length res) res) (loop (cons 0 res) (sub1 k))))) (define (mult a b) (let ((a-abs (bignum-abs a))) (let loop ((res (int->bignum 0 radix)) (sh 0) (num2 (cdr b))) (if (null? num2) res (loop (bignum-plus res (shift-left (bignum-times-int a-abs (car num2) radix) sh) radix) (add1 sh) (cdr num2)))))) (if (= (* (bignum-sign a) (bignum-sign b)) -1) (bignum-negate (mult a b)) (mult a b)))