4.3BSD - /usr/src/usr.lib/libmp/gcd.c

   1: /*
   2:  * Copyright (c) 1980 Regents of the University of California.
   3:  * All rights reserved.  The Berkeley software License Agreement
   4:  * specifies the terms and conditions for redistribution.
   5:  */
   6: 
   7: #ifndef lint
   8: static char sccsid[] = "@(#)gcd.c	5.2 (Berkeley) 3/13/86";
   9: #endif not lint
  10: 
  11: #include <mp.h>
  12: gcd(a,b,c) MINT *a,*b,*c;
  13: {   MINT x,y,z,w;
  14:     x.len=y.len=z.len=w.len=0;
  15:     move(a,&x);
  16:     move(b,&y);
  17:     while(y.len!=0)
  18:     {   mdiv(&x,&y,&w,&z);
  19:         move(&y,&x);
  20:         move(&z,&y);
  21:     }
  22:     move(&x,c);
  23:     xfree(&x);
  24:     xfree(&y);
  25:     xfree(&z);
  26:     xfree(&w);
  27:     return;
  28: }
  29: invert(a, b, c) MINT *a, *b, *c;
  30: {   MINT x, y, z, w, Anew, Aold;
  31:     int i = 0;
  32:     x.len = y.len = z.len = w.len = Aold.len = 0;
  33:     Anew.len = 1;
  34:     Anew.val = xalloc(1, "invert");
  35:     *Anew.val = 1;
  36:     move(b, &x);
  37:     move(a, &y);
  38:     while(y.len != 0)
  39:     {   mdiv(&x, &y, &w, &z);
  40:         move(&Anew, &x);
  41:         mult(&w, &Anew, &Anew);
  42:         madd(&Anew, &Aold, &Anew);
  43:         move(&x, &Aold);
  44:         move(&y, &x);
  45:         move(&z, &y);
  46:         i++;
  47:     }
  48:     move(&Aold, c);
  49:     if( (i&01) == 0) msub(b, c, c);
  50:     xfree(&x);
  51:     xfree(&y);
  52:     xfree(&z);
  53:     xfree(&w);
  54:     xfree(&Aold);
  55:     xfree(&Anew);
  56: }

Defined functions

Defined variables