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