[ create a new paste ] login | about

Link: http://codepad.org/IOQsqHax    [ raw code | output | fork ]

C, pasted on Oct 28:
#include <stdio.h>

int print_i(i, ai, xi, yi) {
  printf("a%i = %i,   x%i = %i,   y%i = %i.\n", i, ai, i, xi, i, yi);
}

int euclid(int a0, int a1) {
  int amm = 0; // a_{i-2}
  int am = a0;  // a_{i-1}
  int a = a1;   // a_{i}
  int i = 1;

  int xmm = 0, ymm = 0;
  int xm = 1, ym = 0;
  int x = 0, y = 1;

  print_i(0, am, xm, ym);
  do {
    // output
    print_i(i, a, x, y);

    // increment index i
    i++;
    // update a's, x's, and y's.
    amm = am; am = a;
    xmm = xm; xm = x;
    ymm = ym; ym = y;

    int q = amm / am; // quotient
    a = amm - am * q; // new remainder

    x = xmm - q * xm;
    y = ymm - q * ym;
  }
  while(a>0);

  printf("gcd(%i,%i) = %i\n", a0, a1, am);
}

int main () {
  euclid(4620, 101);
  return 0;
}


Output:
1
2
3
4
5
6
7
8
9
a0 = 4620,   x0 = 1,   y0 = 0.
a1 = 101,   x1 = 0,   y1 = 1.
a2 = 75,   x2 = 1,   y2 = -45.
a3 = 26,   x3 = -1,   y3 = 46.
a4 = 23,   x4 = 3,   y4 = -137.
a5 = 3,   x5 = -4,   y5 = 183.
a6 = 2,   x6 = 31,   y6 = -1418.
a7 = 1,   x7 = -35,   y7 = 1601.
gcd(4620,101) = 1


Create a new paste based on this one


Comments: