Big Numbers: Addition, Subtraction, And Multiplication
May 31, 2011
For addition, it’s best to make a table to figure out all the signs:
| |a| < |b| | a > 0 | b > 0 | a + b |
| |a| < |b| | a > 0 | b < 0 | −(|b| − a) |
| |a| < |b| | a < 0 | b < 0 | −(|a| + b) |
| |a| < |b| | a < 0 | b > 0 | b − |a| |
| |a| > |b| | a > 0 | b > 0 | a + b |
| |a| > |b| | a > 0 | b < 0 | a − |b| |
| |a| > |b| | a < 0 | b < 0 | −(|a| + b) |
| |a| > |b| | a < 0 | b > 0 | −(|a| − b) |
Then it’s easy enough to write the addition function. Add adds two big-numbers, big-digit by big-digit, carrying when necessary, starting from the least significant big-digit. Sub does the same, but with a borrow instead of a carry, and calls reduce to strip any leading zero big-digits in the result. The main body of the function handles zero and figures out the required operation and sign of the result:
(define (big-plus big1 big2)
(define (reduce xs)
(if (null? (cdr xs)) xs
(if (positive? (car xs)) xs
(reduce (cdr xs)))))
(define (add b1 b2)
(let loop ((b1 b1) (b2 b2) (c 0) (bs '()))
(cond ((null? b1)
(if (zero? c) (reverse bs) (reverse (cons 1 bs))))
((null? b2)
(let* ((sum (+ (car b1) c))
(new-c (if (<= big-base sum) 1 0)))
(loop (cdr b1) b2 new-c
(cons (modulo sum big-base) bs))))
(else (let* ((sum (+ (car b1) (car b2) c))
(new-c (if (<= big-base sum) 1 0)))
(loop (cdr b1) (cdr b2) new-c
(cons (modulo sum big-base) bs)))))))
(define (sub b1 b2)
(let loop ((b1 b1) (b2 b2) (c 0) (bs '()))
(cond ((null? b1) (reverse (reduce bs)))
((null? b2)
(let* ((diff (- (car b1) c))
(new-c (if (< diff 0) 1 0)))
(loop (cdr b1) b2 new-c
(cons (modulo diff big-base) bs))))
(else (let* ((diff (- (car b1) (car b2) c))
(new-c (if (< diff 0) 1 0)))
(loop (cdr b1) (cdr b2) new-c
(cons (modulo diff big-base) bs)))))))
(if (zero? (car big1)) big2
(if (zero? (car big2)) big1
(let* ((b1 (cdr big1)) (b2 (cdr big2))
(lt? (big-lt? (big-abs big1) (big-abs big2)))
(s1 (if (positive? (car big1)) 1 -1))
(s2 (if (positive? (car big2)) 1 -1))
(x (apply (if (= s1 s2) add sub)
(if lt? (list b2 b1) (list b1 b2))))
(len (length x)))
(if (equal? x (list 0)) x
(cons (* len (if (or (and lt? (= s2 1))
(and (not lt?) (= s1 1)))
1 -1))
x))))))
To subtract, we add the negative:
(define (big-minus big1 big2)
(big-plus big1 (big-negate big2)))
Internally, multiplication is similar to addition, except that the carry can be any digit, not just 0 or 1. Times does the work, multiplying each digit of the multiplier, least significant digit first, with every digit of the multiplicand, with c the carry and p the next big-digit of the current partial product. In grade-school the partial products were built into a tableau and added all at once, after all the partial products were computed, but we find it easier to add the partial products as they are computed. Add is the same as big-number addition:
(define (big-times big1 big2)
(define (add b1 b2)
(let loop ((b1 b1) (b2 b2) (c 0) (bs '()))
(cond ((null? b1)
(if (zero? c) (reverse bs) (reverse (cons 1 bs))))
((null? b2)
(let* ((sum (+ (car b1) c))
(new-c (if (<= big-base sum) 1 0)))
(loop (cdr b1) b2 new-c
(cons (modulo sum big-base) bs))))
(else (let* ((sum (+ (car b1) (car b2) c))
(new-c (if (<= big-base sum) 1 0)))
(loop (cdr b1) (cdr b2) new-c
(cons (modulo sum big-base) bs)))))))
(define (sign x) (if (negative? x) -1 (if (positive? x) 1 0)))
(define (times big1 big2)
(let loop ((b1 big1) (b2 big2) (zs '())
(c 0) (ps '()) (bs '()))
(cond ((null? b1) bs)
((null? b2) (let ((zs (cons 0 zs)))
(loop (cdr b1) big2 zs 0 zs
(add (reverse (if (zero? c) ps (cons c ps))) bs))))
(else (let* ((x (+ (* (car b1) (car b2)) c))
(c (quotient x big-base))
(p (modulo x big-base)))
(loop b1 (cdr b2) zs c (cons p ps) bs))))))
(if (or (big-zero? big1) (big-zero? big2)) (list 0)
(let* ((b1 (cdr big1)) (b2 (cdr big2))
(x (times b1 b2)) (len (length x)))
(cons (* len (sign (* (car big1) (car big2)))) x))))
You can see the big-number library, including the code from the previous exercise and some simple examples of today’s functions, at http://programmingpraxis.codepad.org/gAbRGnwD. We’ll do more next Tuesday.
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)))