1 /*
 2  *  bignum_mul.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 M
13 //
14 // factor1 x factor2 = product
15 //
16 bignum_t *
17 bignum_mul (bignum_t *prod, bignum_t *fac1, bignum_t *fac2)
18 {
19   u_int64_t j = 0;
20   u_int64_t t = 0;
21   u_int64_t b = prod->base;
22   u_int64_t m = fac1->oofm;
23   
24   // if either number is zero, the product is 
25   // also zero. return.
26   //
27   if (bignum_iszero(fac1) || bignum_iszero(fac2)) {
28     bignum_set(prod, 0);
29     return prod;
30   }
31   
32   // STEP M1
33   //
34   __bignum_zero(prod);
35   
36   // STEP M2 - M6
37   //
38   // i = 0
39   // k = 0
40   //
41   // t = fac1_sub_i x fac2_sub_j + prod_sub_i+j + k
42   // prod_sub_i+j = t mod b
43   // k = floor_of(t / b)
44   //
45   // prod_sub_j+m = k
46   //
47   do {
48     u_int64_t i = 0;
49     u_int64_t k = 0;
50     u_int64_t y = 0;
51     
52     if (0 != __bignum_get(fac2,j)) {
53       do {
54         t = (u_int64_t)__bignum_get(fac1,i) * (u_int64_t)__bignum_get(fac2,j) + (u_int64_t)__bignum_get(prod,i+j) + k;
55         k = t / b;
56         y = t - (k * b);
57         
58         __bignum_set(prod, i+j, y);
59         
60         if (y != 0 && i+j >= prod->oofm)
61           prod->oofm = i + j + 1;
62       }
63       while (++i < fac1->oofm);
64     }
65     
66     __bignum_set(prod, j+m, k);
67     
68     if (k != 0 && j+m >= prod->oofm)
69       prod->oofm = j + m + 1;
70   }
71   while (++j < fac2->oofm);
72   
73   if (fac1->sign == BIGNUM_NEGATIVE && fac2->sign == BIGNUM_NEGATIVE)
74     prod->sign = BIGNUM_POSITIVE;
75   else if (fac1->sign == BIGNUM_NEGATIVE || fac2->sign == BIGNUM_NEGATIVE)
76     prod->sign = BIGNUM_NEGATIVE;
77   
78   return prod;
79 }
syntax highlighted by Code2HTML, v. 0.9.1