/*
  Author:  Pate Williams (c) 1997

  Algorithm 1.3.6 (Euclid Extended). Given two
  non-negative integers a and b, this algorithm
  determines (u, v, d) such that
  a * u + b * v = d = (a, b) = gcd(a, b). See "A
  Course in Computational Algebraic Number Theory"
  by Henri Cohen page 16.
*/

#include <stdio.h>

#define DEBUG

void Euclid_extended(long a, long b, long *u,
                     long *v, long *d)
{
  long q, t1, t3, v1, v3;

  *u = 1, *d = a;
  if (b == 0) {
    *v = 0;
    return;
  }
  v1 = 0, v3 = b;
  #ifdef DEBUG
  printf("----------------------------------\n");
  printf(" q    t3   *u   *d   t1   v1   v3\n");
  printf("----------------------------------\n");
  #endif
  while (v3 != 0) {
    q = *d / v3;
    t3 = *d - q * v3;
    t1 = *u - q * v1;
    *u = v1, *d = v3;
    #ifdef DEBUG
    printf("%4ld %4ld %4ld ", q, t3, *u);
    printf("%4ld %4ld %4ld %4ld\n", *d, t1, v1, v3);
    #endif
    v1 = t1, v3 = t3;
  }
  *v = (*d - a * *u) / b;
  #ifdef DEBUG
  printf("----------------------------------\n");
  #endif
}

int main(void)
{
  long a = 4864, b = 3458, d, u, v;

  Euclid_extended(a, b, &u, &v, &d);
  printf("a = %ld b = %ld ", a, b);
  printf("u = %ld v = %ld d = %ld\n", u, v, d);
  return 0;
}