Return to mdiv.c CVS log

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

Annotation of researchv8dc/lib/libmp/mdiv.c, revision 1.1

1.1     ! root        1: #include "mp.h"
        !             2: int mpdivdebug;
        !             3: mdiv(a,b,q,r) mint *a,*b,*q,*r;
        !             4: {      mint *x,*y, *z;
        !             5:        int alen, blen;
        !             6:        x = itom(0), y = itom(0);
        !             7:        z = itom(0);
        !             8:        move(a, x);
        !             9:        move(b, y);
        !            10:        alen = x->len;
        !            11:        if(x->len<0) {x->len= -x->len;}
        !            12:        blen = y->len;
        !            13:        if(y->len<0) {y->len= -y->len;}
        !            14:        xfree(q);
        !            15:        xfree(r);
        !            16:        m_div(x,y,q,r);
        !            17:        if(mpdivdebug) {
        !            18:                mult(y, q, z);
        !            19:                madd(z, r, z);
        !            20:                if(mcmp(z, x) != 0) {
        !            21:                        mout(a);
        !            22:                        mout(b);
        !            23:                        fatal("mdiv err");
        !            24:                }
        !            25:        }
        !            26:        if(alen < 0) {
        !            27:                mint o;
        !            28:                short i = 1;
        !            29:                o.len = 1;
        !            30:                o.val = &i;
        !            31:                if(r->len == 0) {
        !            32:                        if(blen > 0)
        !            33:                                q->len = -q->len;
        !            34:                        goto out;
        !            35:                }
        !            36:                msub(r, y, r);
        !            37:                r->len = -r->len;
        !            38:                madd(q, &o, q);
        !            39:                if(blen > 0)
        !            40:                        q->len = -q->len;
        !            41:                goto out;
        !            42:        }
        !            43:        if(blen < 0)
        !            44:                q->len = -q->len;
        !            45: out:
        !            46:        mfree(z);
        !            47:        mfree(y);
        !            48:        mfree(x);
        !            49: }
        !            50: #ifdef vax
        !            51: union zz {
        !            52:        long a;
        !            53:        struct {
        !            54:                unsigned int lo:15, hi:15;
        !            55:        } b;
        !            56: };
        !            57: #endif
        !            58: m_dsb(q,n,a,b) short *a,*b;
        !            59: {      long int qx, u;
        !            60:        union zz x;
        !            61:        int borrow,j;
        !            62:        qx=q;
        !            63:        x.a = 0;
        !            64:        for(j = 0; j < n; j++) {
        !            65:                x.a = qx * a[j] + x.b.hi;
        !            66:                if((b[j] -= x.b.lo) < 0) {
        !            67:                        b[j] += (1 << 15);
        !            68:                        x.b.hi += 1;
        !            69:                }
        !            70:        }
        !            71:        if((b[j] -= x.b.hi) >= 0)
        !            72:                return(0);
        !            73:        borrow=0;
        !            74:        for(j=0;j<n;j++)
        !            75:        {       u=a[j]+b[j]+borrow;
        !            76:                if(u & 0100000)
        !            77:                        borrow = 1;
        !            78:                else borrow=0;
        !            79:                b[j]=u&077777;
        !            80:        }
        !            81:        { return(1);}
        !            82: }
        !            83: m_trq(v1,v2,u1,u2,u3)
        !            84: {      long int d;
        !            85:        long int x1;
        !            86:        if(u1==v1) d=077777;
        !            87:        else d=(u1*0100000L+u2)/v1;
        !            88:        while(1)
        !            89:        {       x1=u1*0100000L+u2-v1*d;
        !            90:                x1=x1*0100000L+u3-v2*d;
        !            91:                if(x1<0) d=d-1;
        !            92:                else {return(d);}
        !            93:        }
        !            94: }
        !            95: m_div(a,b,q,r) mint *a,*b,*q,*r;
        !            96: {      mint u,v,x,w;
        !            97:        short d,*qval;
        !            98:        int qq,n,v1,v2,j;
        !            99:        u.len=v.len=x.len=w.len=0;
        !           100:        if(b->len==0) { fatal("mdiv divide by zero"); return;}
        !           101:        if(b->len==1)
        !           102:        {       r->val=xalloc(1,"m_div1");
        !           103:                sdiv(a,b->val[0],q,r->val);
        !           104:                if(r->val[0]==0)
        !           105:                {       shfree(r->val);
        !           106:                        r->len=0;
        !           107:                }
        !           108:                else r->len=1;
        !           109:                return;
        !           110:        }
        !           111:        if(a->len < b->len)
        !           112:        {       q->len=0;
        !           113:                r->len=a->len;
        !           114:                r->val=xalloc(r->len,"m_div2");
        !           115:                for(qq=0;qq<r->len;qq++) r->val[qq]=a->val[qq];
        !           116:                return;
        !           117:        }
        !           118:        x.len=1;
        !           119:        x.val = &d;
        !           120:        n=b->len;
        !           121:        d=0100000L/(b->val[n-1]+1L);
        !           122:        mult(a,&x,&u); /*subtle: relies on fact that mult allocates extra space */
        !           123:        mult(b,&x,&v);
        !           124:        v1=v.val[n-1];
        !           125:        v2=v.val[n-2];
        !           126:        qval=xalloc(a->len-n+1,"m_div3");
        !           127:        for(j=a->len-n;j>=0;j--)
        !           128:        {       qq=m_trq(v1,v2,u.val[j+n],u.val[j+n-1],u.val[j+n-2]);
        !           129:                if(m_dsb(qq,n,v.val,&(u.val[j]))) qq -= 1;
        !           130:                qval[j]=qq;
        !           131:        }
        !           132:        x.len=n;
        !           133:        x.val=u.val;
        !           134:        mcan(&x);
        !           135:        sdiv(&x,d,&w,(short *)&qq);
        !           136:        r->len=w.len;
        !           137:        r->val=w.val;
        !           138:        q->val=qval;
        !           139:        qq=a->len-n+1;
        !           140:        if(qq>0 && qval[qq-1]==0) qq -= 1;
        !           141:        q->len=qq;
        !           142:        if(qq==0) shfree(qval);
        !           143:        if(x.len!=0) xfree(&u);
        !           144:        xfree(&v);
        !           145:        return;
        !           146: }

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