1 /*
 2  *  bignum_add.c
 3  *  BigMath
 4  *
 5  *  Created by Curtis Jones on 2007.08.05.
 6  *  Copyright 2007 __MyCompanyName__. All rights reserved.
 7  *
 8  */
 9 
10 #include "bignum.h"
11 
12 // Knuth 4.3.1 - Algorithm A
13 //
14 bignum_t *
15 bignum_add (bignum_t *sum, bignum_t *num1, bignum_t *num2)
16 {
17   u_int64_t j = 0;          // iterates through the digits of the number
18   u_int64_t k = 0;          // tracks carries 
19   u_int64_t n = 0;          // max magnitudes of num1, num2
20   u_int64_t b = sum->base;  // radix base
21   
22   __bignum_zero(sum);
23   
24   // if exactly one of the two numbers is negative,
25   // perform subtraction after temporarily setting
26   // that negative number to positive.
27   //
28   if (num1->sign == BIGNUM_NEGATIVE && num2->sign == BIGNUM_POSITIVE) {
29     num1->sign = BIGNUM_POSITIVE;
30     bignum_sub(sum, num1, num2);
31     sum->sign = sum->sign == BIGNUM_POSITIVE ? BIGNUM_NEGATIVE : BIGNUM_POSITIVE;
32     num1->sign = BIGNUM_NEGATIVE;
33     return sum;
34   }
35   else if (num1->sign == BIGNUM_POSITIVE && num2->sign == BIGNUM_NEGATIVE) {
36     num2->sign = BIGNUM_POSITIVE;
37     bignum_sub(sum, num1, num2);
38     sum->sign = sum->sign == BIGNUM_POSITIVE ? BIGNUM_NEGATIVE : BIGNUM_POSITIVE;
39     num2->sign = BIGNUM_NEGATIVE;
40     return sum;
41   }
42   
43   // n represents the magnitude of the larger of the
44   // two numbers. this is the number of times that we
45   // must iterate in the next step.
46   //
47   n = BIGNUM_MAX(num1->oofm, num2->oofm);
48 
49   // STEP A2
50   //
51   // sum_sub_j = (num1_sub_j + num2_sub_j + k) mod b
52   // k = floor_of(num1_sub_j + num2_sub_j + k) / b
53   //
54   do {
55     u_int64_t x, y;
56     
57     x = (u_int64_t)__bignum_get(num1,j) + (u_int64_t)__bignum_get(num2,j) + k;
58     k = x / b;
59     y = x - (k * b);
60     
61     __bignum_set(sum, j, y);
62   }
63   while (++j < n);
64   
65   // STEP A3
66   //
67   // if k != 0
68   //   sum_sub_j = k (if k != 0)
69   //
70   if (k != 0) {
71     __bignum_set(sum, j, k);
72     sum->oofm = j + 1;
73   }
74   else
75     sum->oofm = j;
76   
77   // if both of the numbers are negative, then the sum is
78   // also negative.
79   //
80   if (num1->sign == BIGNUM_NEGATIVE && num2->sign == BIGNUM_NEGATIVE)
81     sum->sign = BIGNUM_NEGATIVE;
82   
83   return sum;
84 }


syntax highlighted by Code2HTML, v. 0.9.1