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