euclidean.frink

Download or view euclidean.frink in plain text format

/** Program to calculate the extended Euclidean algorithm. */
gcde[a,b] :=
{
  a = a < 0 ? -a : a
  b = b < 0 ? -b : b
  if a < b
  {
    tmp = a
    a = b
    b = tmp
  }
  if b == 0
  {
    if a == 0
      return [0,0,0,0,0]
    else
      return [a,1,b,0,a]
  }
  r = a % b
  q = a div b
  u0 = 1
  v0 = -q
  if r == 0
  {
    u1 = u0
    v1 = v0 + 1
    g = b
  } else
  {
    r2 = b % r
    q1 = b div r
    if r2 == 0
    {
      u1 = u0
      v1 = v0
      g = r
    } else 
    {
      u1 = -q1
      v1 = (q * q1) + 1
      do
      {
        r3 = r % r2
        q2 = r div r2
        if r3 == 0
        {
          g = r2
          r = -1
        } else
        {
          u_tmp = u1
          v_tmp = v1
          u1 = (-q2 * u1) + u0
          v1 = (-q2 * v1) + v0
          u0 = u_tmp
          v0 = v_tmp
          r = r2
          r2 = r3
        }
      } while r > r2
    }
  }
  return [a,u1,b,v1,g]
}


Download or view euclidean.frink in plain text format

This is a program written in the programming language Frink.
For more information, view the Frink Documentation or see More Sample Frink Programs.

Alan Eliasen, eliasen@mindspring.com