Return to gcd.c CVS log

Up to [Research Unix] / researchv10no / libmp

Annotation of researchv10no/libmp/gcd.c, revision 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.