V10/libmp/bundled

# To unbundle, sh this file
echo gcd.c 1>&2
sed 's/.//' >gcd.c <<'//GO.SYSIN DD gcd.c'
-#include "mp.h"
-mgcd(a,b,c) mint *a,*b,*c;
-{	mint *x,*y,*z,*w;
-	x = itom(0), y = itom(0), z = itom(0), w = itom(0);
-	move(a,x);
-	move(b,y);
-	while(y->len!=0){
-		mdiv(x,y,w,z);
-		move(y,x);
-		move(z,y);
-	}
-	move(x,c);
-	mfree(x);
-	mfree(y);
-	mfree(z);
-	mfree(w);
-}
-invert(a, b, c) mint *a, *b, *c;
-{	mint x, y, z, w, Anew, Aold;
-	int i = 0;
-	x.len = y.len = z.len = w.len = Aold.len = 0;
-	Anew.len = 1;
-	Anew.val = xalloc(1, "invert");
-	*Anew.val = 1;
-	move(b, &x);
-	move(a, &y);
-	while(y.len != 0)
-	{	mdiv(&x, &y, &w, &z);
-		move(&Anew, &x);
-		mult(&w, &Anew, &Anew);
-		madd(&Anew, &Aold, &Anew);
-		move(&x, &Aold);
-		move(&y, &x);
-		move(&z, &y);
-		i++;
-	}
-	move(&Aold, c);
-	if( (i&01) == 0) msub(b, c, c);
-	xfree(&x);
-	xfree(&y);
-	xfree(&z);
-	xfree(&w);
-	xfree(&Aold);
-	xfree(&Anew);
-}
-
-lineq(a, b, x, y, u)	/* ax + by = u */
-mint *a, *b, *x, *u, *y;
-{	mint *at, *bt, *xo, *yo, *q, *r, *z;
-	static mint *zero, *one;
-	int i;
-	at = itom(0), bt = itom(0), xo = itom(0);
-	yo = itom(0), q = itom(0), r = itom(0), z = itom(0);
-	if(zero == 0) zero = itom(0);
-	if(one == 0) one = itom(1);
-	move(a, at);
-	move(b, bt);
-	move(zero, x);
-	move(one, xo);
-	move(zero, yo);
-	move(one, y);
-	if(bt->len == 0) {
-		move(one, x);
-		move(zero, y);
-		move(a, u);
-		goto out;
-	}
-	for(i = 0; ; i++) {
-		mdiv(at, bt, q, r);
-		if(r->len == 0)
-			break;
-		move(xo, z);
-		move(x, xo);
-		mult(q, xo, x);
-		madd(z, x, x);
-		move(yo, z);
-		move(y, yo);
-		mult(q, yo, y);
-		madd(z, y, y);
-		move(bt, at);
-		move(r, bt);
-	}
-	move(bt, u);
-	if(i & 1)
-		y->len = -y->len;
-	else
-		x->len = -x->len;
-out:
-	mfree(z), mfree(r), mfree(q), mfree(yo);
-	mfree(xo), mfree(bt), mfree(at);
-}
//GO.SYSIN DD gcd.c
echo halloc.c 1>&2
sed 's/.//' >halloc.c <<'//GO.SYSIN DD halloc.c'
-/* list allocator */
-
-typedef struct hdr {
-	struct hdr *next;
-	struct hdr **list;
-	short d[1];
-} hdr;
-extern char *malloc();
-
-hdr *h1, *h4, *h6;
-
-hfree(d)
-short *d;
-{	hdr *p;
-	if(d == (short *)1)
-		return;
-	p = (hdr *)((char *)d - 2 * sizeof(hdr *));
-	if(p->list == 0) {
-		free((char *)p);
-		return;
-	}
-	p->next = *p->list;
-	*p->list = p;
-}
-
-short *
-halloc(n)
-{	short *x;
-	hdr *p;
-	if(n <= 0)
-		return((short *)1);	/* and unusable */
-	if(n <= 2) {
-		if(!h1)
-			makelist(4, &h1);
-		x = h1->d;
-		h1 = h1->next;
-		return(x);
-	}
-	if(n <= 8) {
-		if(!h4)
-			makelist(16, &h4);
-		x = h4->d;
-		h4 = h4->next;
-		return(x);
-	}
-	if(n <= 64) {
-		if(!h6)
-			makelist(128, &h6);
-		x = h6->d;
-		h6 = h6->next;
-		return(x);
-	}
-	p = (hdr *) malloc(sizeof(hdr) + (n - 1) * sizeof(short));
-	p->list = 0;
-	return(p->d);
-}
-
-makelist(n, p)
-hdr **p;
-{	int i, d;
-	char *s;
-	hdr *h;
-	d = sizeof(hdr) + sizeof(short) * (n-1);
-	d = (d + 3) & (~3);
-	s = malloc(128 * d);
-	h = *p = (hdr *)s;
-	for(i = 0; i < 127; i++) {
-		h->next = (hdr *)(s + d);
-		h->list = p;
-		s += d;
-		h = (hdr *)s;
-	}
-	h->next = 0;
-	h->list = p;
-}
//GO.SYSIN DD halloc.c
echo madd.c 1>&2
sed 's/.//' >madd.c <<'//GO.SYSIN DD madd.c'
-#include "mp.h"
-m_add(a,b,c) mint *a,*b,*c;
-{	register int carry,i;
-	register int x;
-	register short *cval;
-	cval=xalloc(a->len+1,"m_add");
-	carry=0;
-	for(i=0;i<b->len;i++)
-	{	x=carry+a->val[i]+b->val[i];
-		if(x&0100000)
-		{	carry=1;
-			cval[i]=x&077777;
-		}
-		else
-		{	carry=0;
-			cval[i]=x;
-		}
-	}
-	for(;i<a->len;i++)
-	{	x=carry+a->val[i];
-		if(x&0100000) cval[i]=x&077777;
-		else
-		{	carry=0;
-			cval[i]=x;
-		}
-
-	}
-	if(carry==1)
-	{	cval[i]=1;
-		c->len=i+1;
-	}
-	else c->len=a->len;
-	c->val=cval;
-	if(c->len==0) shfree(cval);
-	return;
-}
-madd(a,b,c) mint *a,*b,*c;
-{	mint x,y,z;
-	int sign;
-	x.len=a->len;
-	x.val=a->val;
-	y.len=b->len;
-	y.val=b->val;
-	z.len=0;
-	sign=1;
-	if(x.len>=0)
-		if(y.len>=0)
-			if(x.len>=y.len) m_add(&x,&y,&z);
-			else m_add(&y,&x,&z);
-		else
-		{	y.len= -y.len;
-			msub(&x,&y,&z);
-		}
-	else	if(y.len<=0)
-		{	x.len = -x.len;
-			y.len= -y.len;
-			sign= -1;
-			madd(&x,&y,&z);
-		}
-		else
-		{	x.len= -x.len;
-			msub(&y,&x,&z);
-		}
-	 xfree(c);
-	c->val=z.val;
-	c->len=sign*z.len;
-	return;
-}
-m_sub(a,b,c) mint *a,*b,*c;
-{	register int x,i;
-	register int borrow;
-	short one;
-	mint mone;
-	one=1; mone.len= 1; mone.val= &one;
-	c->val=xalloc(a->len,"m_sub");
-	borrow=0;
-	for(i=0;i<b->len;i++)
-	{	x=borrow+a->val[i]-b->val[i];
-		if(x&0100000)
-		{	borrow= -1;
-			c->val[i]=x&077777;
-		}
-		else
-		{	borrow=0;
-			c->val[i]=x;
-		}
-	}
-	for(;i<a->len;i++)
-	{	x=borrow+a->val[i];
-		if(x&0100000) c->val[i]=x&077777;
-		else
-		{	borrow=0;
-			c->val[i]=x;
-		}
-	}
-	if(borrow<0)
-	{	for(i=0;i<a->len;i++) c->val[i] ^= 077777;
-		c->len=a->len;
-		madd(c,&mone,c);
-	}
-	for(i=a->len-1;i>=0;--i)
-		if(c->val[i]>0) {
-			if(borrow==0) c->len=i+1;
-			else c->len= -i-1;
-			return;
-		}
-	shfree(c->val);
-	return;
-}
-msub(a,b,c) mint *a,*b,*c;
-{	mint x,y,z;
-	int sign;
-	x.len=a->len;
-	y.len=b->len;
-	x.val=a->val;
-	y.val=b->val;
-	z.len=0;
-	sign=1;
-	if(x.len>=0)
-		if(y.len>=0)
-			if(x.len>=y.len) m_sub(&x,&y,&z);
-			else
-			{	sign= -1;
-				msub(&y,&x,&z);
-			}
-		else
-		{	y.len= -y.len;
-			madd(&x,&y,&z);
-		}
-	else	if(y.len<=0)
-		{	sign= -1;
-			x.len= -x.len;
-			y.len= -y.len;
-			msub(&x, &y, &z);
-		}
-		else
-		{	x.len= -x.len;
-			madd(&x,&y,&z);
-			sign= -1;
-		}
-	if(a==c && x.len!=0) xfree(a);
-	else if(b==c && y.len!=0) xfree(b);
-	else xfree(c);
-	c->val=z.val;
-	c->len=sign*z.len;
-	return;
-}
//GO.SYSIN DD madd.c
echo mdiv.c 1>&2
sed 's/.//' >mdiv.c <<'//GO.SYSIN DD mdiv.c'
-#include "mp.h"
-int mpdivdebug;
-mdiv(a,b,q,r) mint *a,*b,*q,*r;
-{	mint *x,*y, *z;
-	int alen, blen;
-	x = itom(0), y = itom(0);
-	z = itom(0);
-	move(a, x);
-	move(b, y);
-	alen = x->len;
-	if(x->len<0) {x->len= -x->len;}
-	blen = y->len;
-	if(y->len<0) {y->len= -y->len;}
-	xfree(q);
-	xfree(r);
-	m_div(x,y,q,r);
-	if(mpdivdebug) {
-		mult(y, q, z);
-		madd(z, r, z);
-		if(mcmp(z, x) != 0) {
-			mout(a);
-			mout(b);
-			fatal("mdiv err");
-		}
-	}
-	if(alen < 0) {
-		mint o;
-		short i = 1;
-		o.len = 1;
-		o.val = &i;
-		if(r->len == 0) {
-			if(blen > 0)
-				q->len = -q->len;
-			goto out;
-		}
-		msub(r, y, r);
-		r->len = -r->len;
-		madd(q, &o, q);
-		if(blen > 0)
-			q->len = -q->len;
-		goto out;
-	}
-	if(blen < 0)
-		q->len = -q->len;
-out:
-	mfree(z);
-	mfree(y);
-	mfree(x);
-}
-#ifdef vax
-union zz {
-	long a;
-	struct {
-		unsigned int lo:15, hi:15;
-	} b;
-};
-#endif
-m_dsb(q,n,a,b) short *a,*b;
-{	long int qx, u;
-	union zz x;
-	int borrow,j;
-	qx=q;
-	x.a = 0;
-	for(j = 0; j < n; j++) {
-		x.a = qx * a[j] + x.b.hi;
-		if((b[j] -= x.b.lo) < 0) {
-			b[j] += (1 << 15);
-			x.b.hi += 1;
-		}
-	}
-	if((b[j] -= x.b.hi) >= 0)
-		return(0);
-	borrow=0;
-	for(j=0;j<n;j++)
-	{	u=a[j]+b[j]+borrow;
-		if(u & 0100000)
-			borrow = 1;
-		else borrow=0;
-		b[j]=u&077777;
-	}
-	{ return(1);}
-}
-m_trq(v1,v2,u1,u2,u3)
-{	long int d;
-	long int x1;
-	if(u1==v1) d=077777;
-	else d=(u1*0100000L+u2)/v1;
-	while(1)
-	{	x1=u1*0100000L+u2-v1*d;
-		x1=x1*0100000L+u3-v2*d;
-		if(x1<0) d=d-1;
-		else {return(d);}
-	}
-}
-m_div(a,b,q,r) mint *a,*b,*q,*r;
-{	mint u,v,x,w;
-	short d,*qval;
-	int qq,n,v1,v2,j;
-	u.len=v.len=x.len=w.len=0;
-	if(b->len==0) { fatal("mdiv divide by zero"); return;}
-	if(b->len==1)
-	{	r->val=xalloc(1,"m_div1");
-		sdiv(a,b->val[0],q,r->val);
-		if(r->val[0]==0)
-		{	shfree(r->val);
-			r->len=0;
-		}
-		else r->len=1;
-		return;
-	}
-	if(a->len < b->len)
-	{	q->len=0;
-		r->len=a->len;
-		r->val=xalloc(r->len,"m_div2");
-		for(qq=0;qq<r->len;qq++) r->val[qq]=a->val[qq];
-		return;
-	}
-	x.len=1;
-	x.val = &d;
-	n=b->len;
-	d=0100000L/(b->val[n-1]+1L);
-	mult(a,&x,&u); /*subtle: relies on fact that mult allocates extra space */
-	mult(b,&x,&v);
-	v1=v.val[n-1];
-	v2=v.val[n-2];
-	qval=xalloc(a->len-n+1,"m_div3");
-	for(j=a->len-n;j>=0;j--)
-	{	qq=m_trq(v1,v2,u.val[j+n],u.val[j+n-1],u.val[j+n-2]);
-		if(m_dsb(qq,n,v.val,&(u.val[j]))) qq -= 1;
-		qval[j]=qq;
-	}
-	x.len=n;
-	x.val=u.val;
-	mcan(&x);
-	sdiv(&x,d,&w,(short *)&qq);
-	r->len=w.len;
-	r->val=w.val;
-	q->val=qval;
-	qq=a->len-n+1;
-	if(qq>0 && qval[qq-1]==0) qq -= 1;
-	q->len=qq;
-	if(qq==0) shfree(qval);
-	if(x.len!=0) xfree(&u);
-	xfree(&v);
-	return;
-}
//GO.SYSIN DD mdiv.c
echo mout.c 1>&2
sed 's/.//' >mout.c <<'//GO.SYSIN DD mout.c'
-#include <stdio.h>
-#include "mp.h"
-m_in(a,b,f) mint *a; FILE *f;
-{	mint x,y,ten;
-	int sign,c;
-	short qten,qy;
-	xfree(a);
-	sign=1;
-	ten.len=1;
-	ten.val= &qten;
-	qten=b;
-	x.len=0;
-	y.len=1;
-	y.val= &qy;
-	while((c=getc(f))!=EOF)
-	switch(c)
-	{
-	case '\\':	getc(f);
-		continue;
-	case '\t':
-	case '\n':
-		goto done;
-	case ' ':
-		continue;
-	case '-': sign = -sign;
-		continue;
-	default: if(c>='0' && c<= '9')
-		{	qy=c-'0';
-			mult(&x,&ten,a);
-			madd(a,&y,a);
-			move(a,&x);
-			continue;
-		}
-		else
-		{	(void) ungetc(c,stdin);
-done:
-			a->len *= sign;
-			mcan(a);
-			return(0);
-		}
-	}
-	return(EOF);
-}
-m_out(a,b,f) mint *a; FILE *f;
-{	int sign,xlen,i;
-	short r;
-	mint x;
-	char *obuf;
-	register char *bp;
-	sign=1;
-	xlen=a->len;
-	if(xlen<0)
-	{	xlen= -xlen;
-		sign= -1;
-	}
-	if(xlen==0)
-	{	fprintf(f,"0\n");
-		return;
-	}
-	x.len=xlen;
-	x.val=xalloc(xlen,"m_out");
-	for(i=0;i<xlen;i++) x.val[i]=a->val[i];
-	obuf=(char *)malloc(7*xlen);
-	bp=obuf+7*xlen-1;
-	*bp--=0;
-	while(x.len>0)
-	{	for(i=0;i<10&&x.len>0;i++)
-		{	sdiv(&x,b,&x,&r);
-			*bp--=r+'0';
-		}
-		if(x.len>0) *bp--=' ';
-	}
-	if(sign==-1) *bp--='-';
-	fprintf(f,"%s\n",bp+1);
-	free(obuf);
-	xfree(&x);
-	return;
-}
-sdiv(a,n,q,r) mint *a,*q; short *r;
-{	mint x,y;
-	int sign;
-	sign=1;
-	x.len=a->len;
-	x.val=a->val;
-	if(n<0) {
-		sign= -sign;
-		n= -n;
-	}
-	if(x.len<0) {
-		sign = -sign;
-		x.len= -x.len;
-	}
-	else if(x.len == 0) {
-		xfree(q);
-		*r = 0;
-		return;
-	}
-	s_div(&x,n,&y,r);
-	xfree(q);
-	q->val=y.val;
-	q->len=sign*y.len;
-	*r = *r*sign;
-	return;
-}
-s_div(a,n,q,r) mint *a,*q; short *r;
-{	int qlen,i;
-	long int x;
-	short *qval;
-	x=0;
-	qlen=a->len;
-	qval=xalloc(qlen,"s_div");
-	for(i=qlen-1;i>=0;i--)
-	{
-		x=x*0100000L+a->val[i];
-		qval[i]=x/n;
-		x=x%n;
-	}
-	*r=x;
-	if(qval[qlen-1]==0) qlen--;
-	q->len=qlen;
-	q->val=qval;
-	if(qlen==0) shfree(qval);
-	return;
-}
-min(a) mint *a;
-{
-	return(m_in(a,10,stdin));
-}
-omin(a) mint *a;
-{
-	return(m_in(a,8,stdin));
-}
-mout(a) mint *a;
-{
-	m_out(a,10,stdout);
-}
-omout(a) mint *a;
-{
-	m_out(a,8,stdout);
-}
-fmout(a,f) mint *a; FILE *f;
-{	m_out(a,10,f);
-}
-fmin(a,f) mint *a; FILE *f;
-{
-	return(m_in(a,10,f));
-}
//GO.SYSIN DD mout.c
echo msqrt.c 1>&2
sed 's/.//' >msqrt.c <<'//GO.SYSIN DD msqrt.c'
-#include "mp.h"
-msqrt(a,b,r) mint *a,*b,*r;
-{	mint x,junk,y;
-	int j;
-	x.len=junk.len=y.len=0;
-	if(a->len<0) fatal("msqrt: neg arg");
-	if(a->len==0)
-	{	b->len=0;
-		r->len=0;
-		return(0);
-	}
-	if(a->len%2==1) x.len=(1+a->len)/2;
-	else x.len=1+a->len/2;
-	x.val=xalloc(x.len,"msqrt");
-	for(j=0;j<x.len;x.val[j++]=0);
-	if(a->len%2==1) x.val[x.len-1]=0400;
-	else x.val[x.len-1]=1;
-	xfree(b);
-	xfree(r);
-loop:
-	mdiv(a,&x,&y,&junk);
-	xfree(&junk);
-	madd(&x,&y,&y);
-	sdiv(&y,2,&y,(short *)&j);
-	if(mcmp(&x,&y)>0)
-	{	xfree(&x);
-		move(&y,&x);
-		xfree(&y);
-		goto loop;
-	}
-	xfree(&y);
-	move(&x,b);
-	mult(&x,&x,&x);
-	msub(a,&x,r);
-	xfree(&x);
-	return(r->len);
-}
-
-/* pathology: n<= 0 => r=rem=0, num <= 0, r=rem=0 */
-/* this is a lazy implementation, assuming n>=3 => root is a legal double */
-mroot(n, num, r, rem)
-mint *num, *r, *rem;
-{	extern double log(), exp();
-	double z;
-	int i;
-	static mint *xn, *xn1, *top, *bot;
-	static init;
-	if(!init++) {
-		xn = itom(0), xn1 = itom(0), top = itom(0), bot = itom(0);
-	}
-	if(n < 0 || num->len <= 0) {
-		msub(r, r, r);
-		move(r, rem);
-		return;
-	}
-	if(n == 1) {
-		move(num, r);
-		msub(rem, rem, rem);
-		return;
-	}
-	if(n == 2) {
-		msqrt(num, r, rem);
-		return;
-	}
-	/* compute approx bigger than root */
-	for(z = 0, i = 0; i < num->len; i++)
-		z = z/32768 + num->val[i];
-	/* num = z * 2^15*(len-1) */
-	z = exp((log(z) + 15*(num->len-1)*log(2.))/n);
-	z = 1.01 * z + 1;	/* make sure it is bigger than root */
-	dtom(z, r);
-	/* ((n-1)*x^n+num)/(n*x^(n-1))*/
-	for(;;) {
-		rpow(r, n - 1, xn1);
-		mult(r, xn1, xn);
-		imult(n-1, xn, top);
-		madd(top, num, top);
-		imult(n, xn1, bot);
-		mdiv(top, bot, xn1, rem);
-		switch(mcmp(xn1, r)) {
-		case -1:
-			move(xn1, r);
-			continue;
-		case 0:
-			move(xn1, r);
-			msub(num, xn, rem);
-			return;
-		case 1:	/* since r was too large to start with */
-			msub(num, xn, rem);
-			return;
-		}
-	}
-}
-
-static
-imult(n, a, b)
-mint *a, *b;
-{	mint *x;
-	x = itom(n);
-	mult(x, a, b);
-	msub(x, x,x);
-}
//GO.SYSIN DD msqrt.c
echo mult.c 1>&2
sed 's/.//' >mult.c <<'//GO.SYSIN DD mult.c'
-#include <mp.h>
-#undef unfast
-mult(a,b,c) mint *a,*b,*c;
-{	mint x,y,z;
-	int sign;
-	sign = 1;
-	x.val=a->val;
-	y.val=b->val;
-	z.len=0;
-	if(a->len<0)
-	{	x.len= -a->len;
-		sign= -sign;
-	}
-	else	x.len=a->len;
-	if(b->len<0)
-	{	y.len= -b->len;
-		sign= -sign;
-	}
-	else	y.len=b->len;
-	if(x.len == 0 || y.len == 0)
-		z.len = 0;
-	else if(x.len<y.len) m_mult(&y,&x,&z);
-	else m_mult(&x,&y,&z);
-	xfree(c);
-	if(sign<0) c->len= -z.len;
-	else c->len=z.len;
-	c->val=z.val;
-}
-#define S2 x=a->val[j];
-#define S3 x=x*b->val[i-j];
-#ifdef unfast
-#define S4 tradd(&carry,&sum,x);
-#else
-#define S4 sum.xx += x; if(sum.yy.high & 0100000) {sum.yy.high &= 077777; carry++;}
-#endif
-#define S5 c->val[i]=sum.yy.low&077777;
-#define S6 sum.xx=sum.xx>>15;
-#define S7 sum.yy.high=carry;
-m_mult(a,b,c)
-register mint *a,*b,*c;
-{	register long x;
-	union {long xx; struct half yy;} sum;
-	int carry;
-	int i,j;
-	c->val=xalloc(a->len+b->len,"m_mult");
-	sum.xx=0;
-	for(i=0;i<b->len;i++)
-	{	carry=0;
-		for(j=0;j<i+1;j++)
-		{	S2
-			S3
-			S4
-		}
-		S5
-		S6
-		S7
-	}
-	for(;i<a->len;i++)
-	{	carry=0;
-		for(j=i-b->len+1;j<i+1;j++)
-		{	S2
-			S3
-			S4
-		}
-		S5
-		S6
-		S7
-	}
-	for(;i<a->len+b->len;i++)
-	{	carry=0;
-		for(j=i-b->len+1;j<a->len;j++)
-		{	S2
-			S3
-			S4
-		}
-		S5
-		S6
-		S7
-	}
-	if(i == 0 || c->val[i-1]!=0)
-		c->len=a->len+b->len;
-	else	c->len=a->len+b->len-1;
-	return;
-}
-tradd(a,b,c)
-long c;
-int *a;
-register union {long xx; struct half yy;} *b;
-{
-	b->xx += c;
-	if(b->yy.high&0100000)
-	{	b->yy.high= b->yy.high&077777;
-		*a += 1;
-	}
-	return;
-}
//GO.SYSIN DD mult.c
echo pow.c 1>&2
sed 's/.//' >pow.c <<'//GO.SYSIN DD pow.c'
-#include "mp.h"
-static
-mpow(a,b,c,d) mint *a,*b,*c,*d;
-{	int i,j,n;
-	mint x,y;
-	x.len=y.len=0;
-	xfree(d);
-	d->len=1;
-	d->val=xalloc(1,"mpow");
-	*d->val=1;
-	for(j=0;j<b->len;j++)
-	{	n=b->val[b->len-j-1];
-		for(i=0;i<15;i++)
-		{	mult(d,d,&x);
-			mdiv(&x,c,&y,d);
-			if((n=n<<1)&0100000)
-			{	mult(a,d,&x);
-				mdiv(&x,c,&y,d);
-			}
-		}
-	}
-	xfree(&x);
-	xfree(&y);
-	return;
-}
-rpow(a,n,b) mint *a,*b;
-{	mint x,y;
-	int i;
-	x.len=1;
-	x.val=xalloc(1,"rpow");
-	*x.val=n;
-	y.len=n*a->len+4;
-	y.val=xalloc(y.len,"rpow2");
-	for(i=0;i<y.len;i++) y.val[i]=0;
-	y.val[y.len-1]=010000;
-	xfree(b);
-	mpow(a,&x,&y,b);
-	xfree(&x);
-	xfree(&y);
-	return;
-}
//GO.SYSIN DD pow.c
echo util.c 1>&2
sed 's/.//' >util.c <<'//GO.SYSIN DD util.c'
-extern char *malloc();
-#include "stdio.h"
-#include "mp.h"
-move(a,b) mint *a,*b;
-{	int i,j;
-	if(a == b)
-		return;
-	xfree(b);
-	b->len=a->len;
-	if((i=a->len)<0)
-		i = -i;
-	if(i==0)
-		return;
-	b->val=xalloc(i,"move");
-	for(j=0;j<i;j++)
-		b->val[j]=a->val[j];
-	return;
-}
-dummy(){ }
-/*ARGSUSED*/
-short *xalloc(nint,s) char *s;
-{	short *i;
-	extern short *halloc();
-	i = halloc(nint);
-#ifdef DBG
-	i=(short *)malloc(2*(unsigned)nint+4);
-	if(dbg) fprintf(stderr, "%s: %o\n",s,i);
-#endif
-	if(i!=NULL) return(i);
-	fatal("mp: no free space");
-	return(0);
-}
-fatal(s) char *s;
-{
-	fprintf(stderr,"%s\n",s);
-	(void) fflush(stdout);
-	sleep(2);
-	abort();
-}
-xfree(c) mint *c;
-{
-#ifdef DBG
-	if(dbg) fprintf(stderr, "xfree ");
-#endif
-	if(c->len==0) return;
-	/*shfree(c->val);*/
-	hfree(c->val);
-	c->len=0;
-	return;
-}
-
-mfree(a)
-mint *a;
-{
-	xfree(a);
-	hfree(a);
-}
-mcan(a) mint *a;
-{	int i,j;
-	if((i=a->len)==0) return;
-	else if(i<0) i= -i;
-	for(j=i;j>0 && a->val[j-1]==0;j--);
-	if(j==i) return;
-	if(j==0) {	
-		xfree(a);
-		return;
-	}
-	if(a->len > 0) a->len=j;
-	else a->len = -j;
-}
-mint *itom(n)
-{	mint *a;
-	a=(mint *)xalloc(2,"itom");
-	if(n>0) {	
-		a->len=1;
-		a->val=xalloc(1,"itom1");
-		*a->val=n;
-		return(a);
-	}
-	else if(n<0) {	
-		a->len = -1;
-		a->val=xalloc(1,"itom2");
-		*a->val= -n;
-		return(a);
-	}
-	else {	
-		a->len=0;
-		return(a);
-	}
-}
-mcmp(a,b) mint *a,*b;
-{	mint c;
-	int res;
-	if(a->len < b->len)
-		return(-1);
-	if(a->len > b->len)
-		return(1);
-	c.len=0;
-	msub(a,b,&c);
-	res=c.len;
-	xfree(&c);
-	if(res < 0)
-		return(-1);
-	else if(res == 0)
-		return(0);
-	else
-		return(1);
-}
-
-dtom(z, r)
-double z;
-mint *r;
-{	int i, sgn;
-	static mint *c;
-	if(!c) {
-		c = itom(16384);
-		madd(c, c, c);
-	}
-	if(z < 0) {
-		sgn = 1;
-		z = -z;
-	}
-	else
-		sgn = 0;
-	for(i = 0; z >= 32768; i++)
-		z /= 32768;
-	move(c, r);
-	r->len = 1;
-	r->val[0] = z;
-	while(--i >= 0) {
-		z -= r->val[0];
-		z *= 32768;
-		mult(r, c, r);
-		r->val[0] = z;
-	}
-	if(sgn)
-		r->len = -r->len;
-}
//GO.SYSIN DD util.c
echo Makefile 1>&2
sed 's/.//' >Makefile <<'//GO.SYSIN DD Makefile'
-DESTDIR=/usr/lib
-CFLAGS=
-OBJS= pow.o gcd.o msqrt.o mdiv.o mout.o mult.o madd.o util.o halloc.o 
-
-libmp.a: $(OBJS)
-	ar cr libmp.a $(OBJS)
-
-install: libmp.a
-	cp libmp.a ${DESTDIR}
-	ranlib ${DESTDIR}/libmp.a
-
-clean:
-	rm -f *.o libmp.a
//GO.SYSIN DD Makefile