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.

About these ads

Pages: 1 2

2 Responses to “Big Numbers: Addition, Subtraction, And Multiplication”

  1. 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)
    
  2. brdassign said

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 634 other followers

%d bloggers like this: