Return to gcd.c CVS log

Up to [Research Unix] / researchv8dc / lib / libmp

Annotation of researchv8dc/lib/libmp/gcd.c, revision 1.1.1.1

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

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