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     ! 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.