1 /*
2 * bignum_gcd.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 //
13 // Knuth 1.1 - Algorithm E
14 //
15 // http://en.wikipedia.org/wiki/Euclidean_algorithm
16 //
17 bignum_t *
18 bignum_gcd (bignum_t *res, bignum_t *num1, bignum_t *num2)
19 {
20 //int i = 0;
21 //printf("%s().. starting\n", __PRETTY_FUNCTION__);
22
23 bignum_t *a = bignum_alloc();
24 bignum_t *b = bignum_alloc();
25 bignum_t *t = bignum_alloc();
26 //bignum_t *x = NULL;
27
28 bignum_set_bn(a, num1);
29 bignum_set_bn(b, num2);
30
31 while (!bignum_iszero(b))
32 {
33 // printf("%s().. while loop, iteration #%d\n", __PRETTY_FUNCTION__, (++i));
34
35 bignum_set_bn(t, b);
36
37 // x = t; // swap t <=> b via x
38 // t = b; // store b in t for a, next time around
39 // b = x; //
40
41 bignum_mod(b, a, t); // b = a % b
42
43 bignum_set_bn(a, t);
44
45 // x = a; // swap a <=> t via x
46 // a = t; // set a to the previous value of b
47 // t = x; //
48
49 // printf("%s().. a @ %d = ", __PRETTY_FUNCTION__, (int)a); bignum_print(a);
50 // printf("%s().. b @ %d = ", __PRETTY_FUNCTION__, (int)b); bignum_print(b);
51 // printf("%s().. t @ %d = ", __PRETTY_FUNCTION__, (int)t); bignum_print(t);
52 // printf("\n");
53 }
54
55 bignum_set_bn(res, a);
56
57 bignum_free( a );
58 bignum_free( b );
59 bignum_free( t );
60
61 //printf("%s().. ending\n", __PRETTY_FUNCTION__);
62
63 return res;
64 }
syntax highlighted by Code2HTML, v. 0.9.1