1 /*
2 * bignum_sub.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 S
13 //
14 // c - b = a
15 //
16 // minuend (c) - subtrahend (b) = difference (a)
17 //
18 bignum_t *
19 bignum_sub (bignum_t *dif, bignum_t *min, bignum_t *sub)
20 {
21 u_int64_t j = 0; // iterates through the magnitudes
22 int k = 0; // tracks carries (-1, 0)
23 u_int64_t b = dif->base; // radix base
24
25 __bignum_zero(dif);
26
27 // if exactly one of the two numbers is negative,
28 // perform addition after temporarily setting
29 // that negative number to positive.
30 //
31 if (min->sign == BIGNUM_NEGATIVE && sub->sign == BIGNUM_POSITIVE) {
32 min->sign = BIGNUM_POSITIVE;
33 bignum_add(dif, min, sub);
34 dif->sign = BIGNUM_NEGATIVE;
35 min->sign = BIGNUM_NEGATIVE;
36 return dif;
37 }
38 else if (min->sign == BIGNUM_POSITIVE && sub->sign == BIGNUM_NEGATIVE) {
39 sub->sign = BIGNUM_POSITIVE;
40 bignum_add(dif, min, sub);
41 dif->sign = BIGNUM_POSITIVE;
42 sub->sign = BIGNUM_NEGATIVE;
43 return dif;
44 }
45
46 // cmp > 0 if min > sub
47 // cmp == 0 if min == sub
48 // cmp < 0 if min < sub
49 //
50 int cmp = bignum_cmp(min, sub);
51
52 // if the minuend and the subtrahend are equal, then
53 // the difference is equal to zero. set it and return.
54 //
55 if (0 == cmp)
56 return dif;
57
58 // if the minuend is less than the subtrahend, such that
59 // the result of this operation will be negative, we need
60 // to swap their positions, and set the sign of the
61 // difference to negative.
62 //
63 else if (0 > cmp) {
64 bignum_sub(dif, sub, min);
65 dif->sign = BIGNUM_NEGATIVE;
66 return dif;
67 }
68
69 // we can assume that the minuend is greater than the
70 // subtrahend at this point, so if the subtrahend is zero
71 // then the difference is equal to the minuend. set it
72 // and return.
73 //
74 else if (bignum_iszero(sub)) {
75 bignum_set_bn(dif, min);
76 return dif;
77 }
78
79 // STEP S2
80 //
81 // sum_sub_j = (min_sub_j - sub_sub_j + k) mod b
82 // k = floor_of(min_sub_j - sub_sub_j + k) / b
83 //
84 do {
85 u_int64_t x, y;
86
87 x = (u_int64_t)__bignum_get(min,j) - (u_int64_t)__bignum_get(sub,j) + k;
88 k = x / b;
89 y = x - (k * b);
90
91 __bignum_set(dif, j, y);
92
93 if (y != 0 && j >= dif->oofm)
94 dif->oofm = j+1;
95 }
96 while (++j < min->oofm);
97
98 return dif;
99 }
syntax highlighted by Code2HTML, v. 0.9.1