Return to gcd.c CVS log

Up to [Research Unix] / researchv10no / libmp

Annotation of researchv10no/libmp/gcd.c, revision 1.1.1.1

1.1       root        1: #include "mp.h"
                      2: mgcd(a,b,c) mint *a,*b,*c;
                      3: {      mint *x,*y,*z,*w;
                      4:        x = itom(0), y = itom(0), z = itom(0), w = itom(0);
                      5:        move(a,x);
                      6:        move(b,y);
                      7:        while(y->len!=0){
                      8:                mdiv(x,y,w,z);
                      9:                move(y,x);
                     10:                move(z,y);
                     11:        }
                     12:        move(x,c);
                     13:        mfree(x);
                     14:        mfree(y);
                     15:        mfree(z);
                     16:        mfree(w);
                     17: }
                     18: invert(a, b, c) mint *a, *b, *c;
                     19: {      mint x, y, z, w, Anew, Aold;
                     20:        int i = 0;
                     21:        x.len = y.len = z.len = w.len = Aold.len = 0;
                     22:        Anew.len = 1;
                     23:        Anew.val = xalloc(1, "invert");
                     24:        *Anew.val = 1;
                     25:        move(b, &x);
                     26:        move(a, &y);
                     27:        while(y.len != 0)
                     28:        {       mdiv(&x, &y, &w, &z);
                     29:                move(&Anew, &x);
                     30:                mult(&w, &Anew, &Anew);
                     31:                madd(&Anew, &Aold, &Anew);
                     32:                move(&x, &Aold);
                     33:                move(&y, &x);
                     34:                move(&z, &y);
                     35:                i++;
                     36:        }
                     37:        move(&Aold, c);
                     38:        if( (i&01) == 0) msub(b, c, c);
                     39:        xfree(&x);
                     40:        xfree(&y);
                     41:        xfree(&z);
                     42:        xfree(&w);
                     43:        xfree(&Aold);
                     44:        xfree(&Anew);
                     45: }
                     46: 
                     47: lineq(a, b, x, y, u)   /* ax + by = u */
                     48: mint *a, *b, *x, *u, *y;
                     49: {      mint *at, *bt, *xo, *yo, *q, *r, *z;
                     50:        static mint *zero, *one;
                     51:        int i;
                     52:        at = itom(0), bt = itom(0), xo = itom(0);
                     53:        yo = itom(0), q = itom(0), r = itom(0), z = itom(0);
                     54:        if(zero == 0) zero = itom(0);
                     55:        if(one == 0) one = itom(1);
                     56:        move(a, at);
                     57:        move(b, bt);
                     58:        move(zero, x);
                     59:        move(one, xo);
                     60:        move(zero, yo);
                     61:        move(one, y);
                     62:        if(bt->len == 0) {
                     63:                move(one, x);
                     64:                move(zero, y);
                     65:                move(a, u);
                     66:                goto out;
                     67:        }
                     68:        for(i = 0; ; i++) {
                     69:                mdiv(at, bt, q, r);
                     70:                if(r->len == 0)
                     71:                        break;
                     72:                move(xo, z);
                     73:                move(x, xo);
                     74:                mult(q, xo, x);
                     75:                madd(z, x, x);
                     76:                move(yo, z);
                     77:                move(y, yo);
                     78:                mult(q, yo, y);
                     79:                madd(z, y, y);
                     80:                move(bt, at);
                     81:                move(r, bt);
                     82:        }
                     83:        move(bt, u);
                     84:        if(i & 1)
                     85:                y->len = -y->len;
                     86:        else
                     87:                x->len = -x->len;
                     88: out:
                     89:        mfree(z), mfree(r), mfree(q), mfree(yo);
                     90:        mfree(xo), mfree(bt), mfree(at);
                     91: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.