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