cat inverter.f
cat: cannot open inverter.f
$ cat inverter4.f
/* inverter4.f May 3, 1987 */
/* Completed May 1, 1987 after three months of effort, chasing bugs */
/* This bc script is the model for the algorithm, implemented below in
c. The algorithm needed had to avoid absolute multiplication, and use
modular multiplication directly so that roundoff truncation did not
affect the product of two large numbers.  The first attempt to achive
this result relied on re-entrant code, but was too hard to debug.  This
code avoids recursion, at the expense of added formal complexity  */
/*
define m(a) {
j = 0
r = a
t = b
while ( r > 1 ) {
        a[j] = r
        b[j] = t
        r = a[j] - (b[j] % a[j])
        x[j] = (b[j] / a[j]) + 1
        y[j] = 1
        while( b[j] % r > 0)     {
                u = ( b[j] / r ) + 1
                x[j] = x[j] * u % b
                y[j] = (y[j] * u + 1) % b
                r = r - (b[j] % r)
                                }
                t = a[j]
                j = j + 1
                }
        j = j - 1
        z[j] = x[j]
        k[j] = y[j]
        if (j == 0 )    {
                return(z[0])
                        }
        while( j > 0)   {
                j = j - 1
                z[j] = (x[j] * z[j + 1] - k[j + 1] ) % b
                k[j] = (z[j + 1] * y[j] ) % b
                        }
        return(z[0])
} */
inv(u,v,w) /* This function generates the modular inverse through a process
which was developed using bc and avoids reentrant code. Inverter4 is the
name of the bc script which this function was developed from.      */
char *u , *v, *w ;
{
        char *a[15],*b[15],*x[15],*y[15],*k[15],*z[15] ;
        char *r , *t , *s , *f, *malloc() ;
        int i, j ;
        r = malloc(15) ;
        t = malloc(15) ;
        s = malloc(15) ;
        f = malloc(15) ;
        j = 0 ;
        for( i = 0 ; i < 15 ; i++) a[i] = malloc(15) ;
        for( i = 0 ; i < 15 ; i++) b[i] = malloc(15) ;
        for( i = 0 ; i < 15 ; i++) x[i] = malloc(15) ;
        for( i = 0 ; i < 15 ; i++) y[i] = malloc(15) ;
        for( i = 0 ; i < 15 ; i++) k[i] = malloc(15) ;
        for( i = 0 ; i < 15 ; i++) z[i] = malloc(15) ;
        copy(u,r) ;
        copy(v,t) ;
        while(strcmp(r,one) > 0)
        {
                copy(r,a[j]) ;
                copy(t,b[j]) ;
                copy(b[j],r) ;
                residue(r,a[j]) ;
                copy(r,s) ;
                copy(a[j],r) ;
                sub(r,s) ;
                copy(b[j],x[j]) ;
                divide(x[j],a[j]) ;
                add(x[j],one) ;
                copy(one,y[j]) ;
                copy(b[j],f) ;
                residue(f,r) ;
                while(strcmp(f,xero) > 0 )
                {
                        copy(b[j],t) ;
                        divide(t,r) ;
                        add(t,one) ;
                        multiply(x[j],t,v) ;
                        multiply(y[j],t,v) ;
                        add(y[j],one) ;
                        multiply(y[j],one,v) ;
                        copy(b[j],f) ;
                        residue(f,r) ;
                        sub(r,f) ;
                        copy(b[j],f) ;
                        residue(f,r) ;
                }
                copy(a[j],t) ;
                j = j + 1 ;
        }
        j = j - 1 ;
        copy(x[j],z[j]) ;
        copy(y[j],k[j]) ;
        if ( j == 0)
        {       copy(z[0],w) ;
                return ;
        }
        while( j > 0 )
        {
                i = j ;
                j = j - 1 ;
                copy(z[i],z[j]) ;
                multiply(z[j],x[j],v);
                while(strcmp(z[j],k[i]) < 0) add(z[j],v) ;
                sub(z[j],k[i] ) ;
                multiply(z[j],one,v) ;
                copy(z[i],k[j] ) ;
                multiply(k[j],y[j],v) ;
        }
copy(z[0],w) ;
}

$