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.

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 598 other followers

%d bloggers like this: