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