lllgcd.c

calc大数库

					FREEMATI(MATI3);
					MATI3 = M;
				}
			}

			COEFF = SHORTESTX(Q, XX, &count);
if (count>record)
{
			record=count;
			outfile = fopen(buff, "a");
			printf("(i1,i2,i3,i4)=(%u,%u,%u,%u): record=%u\n", i1,i2,i3,i4, record);
			fprintf(outfile, "(i1,i2,i3,i4)=(%u,%u,%u,%u): record=%u\n", i1,i2,i3,i4, record);
			fclose(outfile);
}
			for (j = 0; j < p; j++)
				FREEMPI(XX[j]);
			ffree((char *)XX, p * sizeof(MPI *));
			SIGMA = (MPR **)mmalloc(p * sizeof(MPR *));
			for (j = 0; j < count; j++)
			{
				/*printf("SIGMA[%u]=", j);*/
				for (K = p - 1; K >= 0; K--)
				{
					SUMR = COPYR(elt(LMATRIX, m - 1, K));
					for (r = p - 1; r > K; r--)
					{
						tR2 = COPYR(elt(LMATRIX, r, K));
						tempR = BUILDMPR();
						tempR->N = COPYI(COEFF[j][r]);
						tempR->D = ONEI();
						tR3 = MULTR(tR2, tempR);
						FREEMPR(tempR);
						FREEMPR(tR2);
						tR1 = SUMR;
						SUMR = ADDR(SUMR, tR3);
						FREEMPR(tR1);
						FREEMPR(tR3);
					}
					SIGMA[K] = SUMR;
					/*PRINTR(SIGMA[K]);
					printf(" ");*/
					tempR = BUILDMPR();
					tempR->N = COPYI(COEFF[j][K]);
					tempR->D = ONEI();
					tempR1 = ADDR(tempR, SIGMA[K]);
					tempI = ABSI(tempR1->N);
					e = RSV(tempI, tempR1->D);
					FREEMPR(tempR);
					FREEMPR(tempR1);
					FREEMPI(tempI);
					if (e >= 0)
					{
						fprintf(stderr, "conjecture false:j = %u, K = %d\n", j,  K + 1);
						outfile = fopen(buff, "a"), count;
		fprintf(outfile, "(i1,i2,i3,i4)=(%u,%u,%u,%u): ", i1,i2,i3,i4);
						fprintf(outfile, "conjecture false: j = %u, K = %d\n", j, K + 1);
						fclose(outfile);
						exit (1);
					}
				}
				/*printf("\n");*/
				for (K = 0; K < p; K++)
					FREEMPR(SIGMA[K]);
			}
			ffree((char *)SIGMA, p * sizeof(MPR *));

			ffree((char *)COEFF, GCD_MAX * sizeof(MPI **));
			for (j = 0; j < count; j++)
			{
				ffree((char *)COEFF[j], p * sizeof(MPI *));
				for (i = 0; i < p; i++)
					FREEMPI(COEFF[j][i]);
			}
			FREEMATI(MATI3);
			FREEMATI(Q);
			FREEMATR(LMATRIX);
		}
	}
	}
	}
	}
	return;
}

void GCD3()
/* We print out all shortest multipliers for a[1],a[2],a[3].
 * in the range p1<=a[1]<=q1 etc. and rel prime.
 * The output is sent to gcd3.out.
 */
{
	USI p1, q1, p2, q2, p3, q3;
	USI i1, i2, i3, p;
	USL x, y;
	USI m1, n1, m, n, i, j;
	MPMATI *MATI1, *MATI2, *Q, *M, *MATI3;
	MPI *A, **XX, **X, *Temp;
	MPMATR *LMATRIX;
	char buff[20];
	FILE *outfile;

	printf("Enter alpha=m/n,  1/4 < m/n <= 1:  (ie enter  m  and n)");
	scanf("%u%u", &m1, &n1);
	strcpy(buff, "gcd3.out");
	if(access(buff, R_OK) == 0)
	  unlink(buff);
	printf("Enter  the ranges pi,qi; 2 <= pi < qi < 2^32, i = 1,..3: ");
	scanf("%u%u%u%u%u%u", &p1, &q1, &p2, &q2, &p3, &q3);
	Flush();
	m = 3;
	p = m - 1;
	for (i1 = p1; i1 <= q1; i1++)
	{
	for (i2 = p2; i2 <= q2; i2++)
	{
	for (i3 = p3; i3 <= q3; i3++)
	{
		x = GCDm((USL)i1, (USL)i2);
		y = GCDm(x, (USL)i3);
		if (y == 1)
		{
			MATI1 = BUILDMATI(m, 1);
			MATI1->V[0][0] = CHANGE((USL) i1);
			MATI1->V[1][0] = CHANGE((USL) i2);
			MATI1->V[2][0] = CHANGE((USL) i3);

			m = MATI1->R;
			MATI2 = LLLGCDL(MATI1, &A, m, m1, n1, &LMATRIX);
			FREEMATI(MATI1);
			FREEMPI(A);
			MATI3 = BUILDMATI(1, m);
			for (i = 0;i < m;i++)
				MATI3->V[0][i] = COPYI(MATI2->V[m - 1][i]); 
			p = m - 1;
			XX = (MPI **)mmalloc((USL)(p * sizeof(MPI *)));
			for (j = 0; j < p; j++)
				XX[j] = ZEROI();

			Q = MATI2;
			n = Q->R;
			while (1)
			{
				M = SHORTESTT0(Q, &X);
				for (j = 0; j < p; j++)
				{
					Temp = XX[j];
					XX[j] = ADDI(XX[j], X[j]);
					FREEMPI(Temp);
					FREEMPI(X[j]);
				}
				ffree((char *)X, p * sizeof(MPI *));
				if (M == NULL)
					break;
				else
				{
					for (j = 0; j < Q->C; j++)
					{
						FREEMPI(Q->V[n - 1][j]);
						Q->V[n - 1][j] = COPYI(M->V[0][j]);
					}
					FREEMATI(MATI3);
					MATI3 = M;
				}
			}

			outfile = fopen(buff, "a");
			printf("(i1,i2,i3)=(%u,%u,%u):", i1, i2, i3);
			fprintf(outfile, "(i1,i2,i3)=(%u,%u,%u):", i1, i2, i3);
			printf("(MU[21],MU[31],MU[32]=");
			fprintf(outfile, "(MU[21],MU[31],MU[32]=");
			PRINTR(elt(LMATRIX, 1, 0));
			FPRINTR(outfile, elt(LMATRIX, 1, 0));
			printf(",");
			fprintf(outfile, ",");
			PRINTR(elt(LMATRIX, 2, 0));
			FPRINTR(outfile, elt(LMATRIX, 2, 0));
			printf(",");
			fprintf(outfile, ",");
			PRINTR(elt(LMATRIX, 2, 1));
			FPRINTR(outfile, elt(LMATRIX, 2, 1));
			printf(":\n");
			fprintf(outfile, ":\n");
			fclose(outfile);
			SHORTEST(Q, XX, 4, 1);
			for (j = 0; j < p; j++)
				FREEMPI(XX[j]);
			ffree((char *)XX, p * sizeof(MPI *));
			FREEMATI(MATI3);
			FREEMATI(Q);
			FREEMATR(LMATRIX);
		}
	}
	}
	}
	return;
}

void GCDCONJECTURE6()
/* We test our LLLGCD conjecture for a[1],a[2],a[3],a[4],a[5],a[6] 
 * in the range p1<=a[1]<=q1 etc. and rel prime.
 */
{
	USI p1, q1, p2, q2, p3, q3, p4, q4, p5, q5, p6, q6;
	USI i1, i2, i3, i4, i5, i6, p, record=1;
	USL x, y, z, u, v;
	USI m1, n1, m, n, i, j, count;
	int r, e, K;
	MPMATI *MATI1, *MATI2, *Q, *M, *MATI3;
	MPI *A, **XX, **X, *Temp, ***COEFF, *tempI;
	MPMATR *LMATRIX;
	MPR **SIGMA, *SUMR, *tR1, *tR2, *tR3, *tempR, *tempR1;
	char buff[20];
	FILE *outfile;

	printf("Enter alpha=m/n,  1/4 < m/n <= 1:  (ie enter  m  and n)");
	scanf("%u%u", &m1, &n1);
	strcpy(buff, "conjecture6.out");
	if(access(buff, R_OK) == 0)
	  unlink(buff);
	printf("Enter  the ranges pi,qi; 2 <= pi < qi < 2^32, i = 1,...,6: ");
	scanf("%u%u%u%u%u%u%u%u%u%u%u%u", &p1, &q1, &p2, &q2, &p3, &q3, &p4, &q4, &p5, &q5, &p6, &q6);
	Flush();
	m = 6;
	p = m - 1;
	for (i1 = p1; i1 <= q1; i1++)
	{
	for (i2 = p2; i2 <= q2; i2++)
	{
	for (i3 = p3; i3 <= q3; i3++)
	{
	printf("(i1,i2,i3)=(%u,%u,%u)\n", i1,i2,i3);
	for (i4 = p4; i4 <= q4; i4++)
	{
	for (i5 = p5; i5 <= q5; i5++)
	{
	for (i6 = p6; i6 <= q6; i6++)
	{
/*printf("(i1,i2,i3,i4,i5,i6)=(%u,%u,%u,%u,%u,%u)\n", i1,i2,i3,i4,i5,i6);*/
		x = GCDm((USL)i1, (USL)i2);
		y = GCDm(x, (USL)i3);
		z = GCDm(y, (USL)i4);
		u = GCDm(z, (USL)i5);
		v = GCDm(u, (USL)i6);
		if (v == 1)
		{
			MATI1 = BUILDMATI(m, 1);
			MATI1->V[0][0] = CHANGE((USL) i1);
			MATI1->V[1][0] = CHANGE((USL) i2);
			MATI1->V[2][0] = CHANGE((USL) i3);
			MATI1->V[3][0] = CHANGE((USL) i4);
			MATI1->V[4][0] = CHANGE((USL) i5);
			MATI1->V[5][0] = CHANGE((USL) i6);

			m = MATI1->R;
			MATI2 = LLLGCDL(MATI1, &A, m, m1, n1, &LMATRIX);
			FREEMATI(MATI1);
			FREEMPI(A);
			MATI3 = BUILDMATI(1, m);
			for (i = 0;i < m;i++)
				MATI3->V[0][i] = COPYI(MATI2->V[m - 1][i]); 
			p = m - 1;
			XX = (MPI **)mmalloc((USL)(p * sizeof(MPI *)));
			for (j = 0; j < p; j++)
				XX[j] = ZEROI();

			Q = MATI2;
			n = Q->R;
			while (1)
			{
				M = SHORTESTT0(Q, &X);
				for (j = 0; j < p; j++)
				{
					Temp = XX[j];
					XX[j] = ADDI(XX[j], X[j]);
					FREEMPI(Temp);
					FREEMPI(X[j]);
				}
				ffree((char *)X, p * sizeof(MPI *));
				if (M == NULL)
					break;
				else
				{
					for (j = 0; j < Q->C; j++)
					{
						FREEMPI(Q->V[n - 1][j]);
						Q->V[n - 1][j] = COPYI(M->V[0][j]);
					}
					FREEMATI(MATI3);
					MATI3 = M;
				}
			}

			COEFF = SHORTESTX(Q, XX, &count);
if (count>record)
{
			record=count;
			outfile = fopen(buff, "a");
			printf("(i1,i2,i3,i4,i5,i6)=(%u,%u,%u,%u,%u,%u): record=%u\n", i1,i2,i3,i4,i5,i6, record);
			fprintf(outfile, "(i1,i2,i3,i4,i5,i6)=(%u,%u,%u,%u,%u,%u): record=%u\n", i1,i2,i3,i4,i5,i6, record);
			fclose(outfile);
}
			for (j = 0; j < p; j++)
				FREEMPI(XX[j]);
			ffree((char *)XX, p * sizeof(MPI *));
			SIGMA = (MPR **)mmalloc(p * sizeof(MPR *));
			for (j = 0; j < count; j++)
			{
				/*printf("SIGMA[%u]=", j);*/
				for (K = p - 1; K >= 0; K--)
				{
					SUMR = COPYR(elt(LMATRIX, m - 1, K));
					for (r = p - 1; r > K; r--)
					{
						tR2 = COPYR(elt(LMATRIX, r, K));
						tempR = BUILDMPR();
						tempR->N = COPYI(COEFF[j][r]);
						tempR->D = ONEI();
						tR3 = MULTR(tR2, tempR);
						FREEMPR(tempR);
						FREEMPR(tR2);
						tR1 = SUMR;
						SUMR = ADDR(SUMR, tR3);
						FREEMPR(tR1);
						FREEMPR(tR3);
					}
					SIGMA[K] = SUMR;
					/*PRINTR(SIGMA[K]);
					printf(" ");*/
					tempR = BUILDMPR();
					tempR->N = COPYI(COEFF[j][K]);
					tempR->D = ONEI();
					tempR1 = ADDR(tempR, SIGMA[K]);
					tempI = ABSI(tempR1->N);
					e = RSV(tempI, tempR1->D);
					FREEMPR(tempR);
					FREEMPR(tempR1);
					FREEMPI(tempI);
					if (e >= 0)
					{
						fprintf(stderr, "conjecture false:j = %u, K = %d\n", j,  K + 1);
						outfile = fopen(buff, "a"), count;
		fprintf(outfile, "(i1,i2,i3,i4,i5,i6)=(%u,%u,%u,%u,%u,%u): ", i1,i2,i3,i4,i5,i6);
						fprintf(outfile, "conjecture false: j = %u, K = %d\n", j, K + 1);
						fclose(outfile);
						exit (1);
					}
				}
				/*printf("\n");*/
				for (K = 0; K < p; K++)
					FREEMPR(SIGMA[K]);
			}
			ffree((char *)SIGMA, p * sizeof(MPR *));

			ffree((char *)COEFF, GCD_MAX * sizeof(MPI **));
			for (j = 0; j < count; j++)
			{
				ffree((char *)COEFF[j], p * sizeof(MPI *));
				for (i = 0; i < p; i++)
					FREEMPI(COEFF[j][i]);
			}
			FREEMATI(MATI3);
			FREEMATI(Q);
			FREEMATR(LMATRIX);
		}
	}
	}
	}
	}
	}
	}
	return;
}

void GCDCONJECTURE7()
/* We test our LLLGCD conjecture for a[1],...,a[7] 
 * in the range p1<=a[1]<=q1 etc. and rel prime.
 */
{
	USI p1, q1, p2, q2, p3, q3, p4, q4, p5, q5, p6, q6, p7, q7;
	USI i1, i2, i3, i4, i5, i6, i7, p, record=1;
	USL x, y, z, u, v, w;
	USI m1, n1, m, n, i, j, count;
	int r, e, K;
	MPMATI *MATI1, *MATI2, *Q, *M, *MATI3;
	MPI *A, **XX, **X, *Temp, ***COEFF, *tempI;
	MPMATR *LMATRIX;
	MPR **SIGMA, *SUMR, *tR1, *tR2, *tR3, *tempR, *tempR1;
	char buff[20];
	FILE *outfile;

	printf("Enter alpha=m/n,  1/4 < m/n <= 1:  (ie enter  m  and n)");
	scanf("%u%u", &m1, &n1);
	strcpy(buff, "conjecture7.out");
	if(access(buff, R_OK) == 0)
	  unlink(buff);
	printf("Enter  the ranges pi,qi; 2 <= pi < qi < 2^32, i = 1,...,7: ");
	scanf("%u%u%u%u%u%u%u%u%u%u%u%u%u%u", &p1, &q1, &p2, &q2, &p3, &q3, &p4, &q4, &p5, &q5, &p6, &q6, &p7, &q7);
	Flush();
	m = 7;
	p = m - 1;
	for (i1 = p1; i1 <= q1; i1++)
	{
	for (i2 = p2; i2 <= q2; i2++)
	{
	for (i3 = p3; i3 <= q3; i3++)
	{
/*	printf("(i1,i2,i3)=(%u,%u,%u)\n", i1,i2,i3);*/
	for (i4 = p4; i4 <= q4; i4++)
	{
	for (i5 = p5; i5 <= q5; i5++)
	{
	for (i6 = p6; i6 <= q6; i6++)
	{
	for (i7 = p7; i7 <= q7; i7++)
	{
printf("(i1,i2,i3,i4,i5,i6,i7)=(%u,%u,%u,%u,%u,%u,%u)\n", i1,i2,i3,i4,i5,i6,i7);
		x = GCDm((USL)i1, (USL)i2);
		y = GCDm(x, (USL)i3);
		z = GCDm(y, (USL)i4);
		u = GCDm(z, (USL)i5);
		v = GCDm(u, (USL)i6);
		w = GCDm(v, (USL)i7);
		if (w == 1)
		{
			MATI1 = BUILDMATI(m, 1);
			MATI1->V[0][0] = CHANGE((USL) i1);
			MATI1->V[1][0] = CHANGE((USL) i2);
			MATI1->V[2][0] = CHANGE((USL) i3);
			MATI1->V[3][0] = CHANGE((USL) i4);
			MATI1->V[4][0] = CHANGE((USL) i5);
			MATI1->V[5][0] = CHANGE((USL) i6);
			MATI1->V[6][0] = CHANGE((USL) i7);

			m = MATI1->R;
			MATI2 = LLLGCDL(MATI1, &A, m, m1, n1, &LMATRIX);
			FREEMATI(MATI1);
			FREEMPI(A);
			MATI3 = BUILDMATI(1, m);
			for (i = 0;i < m;i++)
				MATI3->V[0][i] = COPYI(MATI2->V[m - 1][i]); 
			p = m - 1;
			XX = (MPI **)mmalloc((USL)(p * sizeof(MPI *)));
			for (j = 0; j < p; j++)
				XX[j] = ZEROI();

			Q = MATI2;
			n = Q->R;
			while (1)
			{
				M = SHORTESTT0(Q, &X);
				for (j = 0; j < p; j++)
				{
					Temp = XX[j];
					XX[j] = ADDI(XX[j], X[j]);
					FREEMPI(Temp);
					FREEMPI(X[j]);
				}
				ffree((char *)X, p * sizeof(MPI *));
				if (M == NULL)
					break;
				else
				{
					for (j = 0; j < Q->C; j++)
					{
						FREEMPI(Q->V[n - 1][j]);
						Q->V[n - 1][j] = COPYI(M->V[0][j]);
					}
					FREEMATI(MATI3);
					MATI3 = M;
				}
			}

			COEFF = SHORTESTX(Q, XX, &count);
if (count>record)
{
			record=count;
			outfile = fopen(buff, "a");
			printf("(i1,i2,i3,i4,i5,i6,i7)=(%u,%u,%u,%u,%u,%u,%u): record=%u\n", i1,i2,i3,i4,i5,i6,i7, record);
			fprintf(outfile, "(i1,i2,i3,i4,i5,i6,i7)=(%u,%u,%u,%u,%u,%u,%u): record=%u\n", i1,i2,i3,i4,i5,i6,i7, record);
			fclose(outfile);
}
			for (j = 0; j < p; j++)
				FREEMPI(XX[j]);
			ffree((char *)XX, p * sizeof(MPI *));
			SIGMA = (MPR **)mmalloc(p * sizeof(MPR *));
			for (j = 0; j < count; j++)
			{
				/*printf("SIGMA[%u]=", j);*/
				for (K = p - 1; K >= 0; K--)
				{
					SUMR = COPYR(elt(LMATRIX, m - 1, K));
					for (r = p - 1; r > K; r--)
					{
						tR2 = COPYR(elt(LMATRIX, r, K));
						tempR = BUILDMPR();
						tempR->N = COPYI(COEFF[j][r]);
						tempR->D = ONEI();
						tR3 = MULTR(tR2, tempR);
						FREEMPR(tempR);
						FREEMPR(tR2);
						tR1 = SUMR;
						SUMR = ADDR(SUMR, tR3);
						FREEMPR(tR1);
						FREEMPR(tR3);
					}
					SIGMA[K] = SUMR;
					/*PRINTR(SIGMA[K]);
					printf(" ");*/
					tempR = BUILDMPR();
					tempR->N = COPYI(COEFF[j][K]);
					tempR->D = ONEI();
					tempR1 = ADDR(tempR, SIGMA[K]);
					tempI = ABSI(tempR1->N);
					e = RSV(tempI, tempR1->D);
					FREEMPR(tempR);
					FREEMPR(tempR1);
					FREEMPI(tempI);
					if (e >= 0)
					{
						fprintf(stderr, "conjecture false:j = %u, K = %d\n", j,  K + 1);
						outfile = fopen(buff, "a"), count;
		fprintf(outfile, "(i1,i2,i3,i4,i5,i6,i7)=(%u,%u,%u,%u,%u,%u,%u): ", i1,i2,i3,i4,i5,i6,i7);
						fprintf(outfile, "conjecture false: j = %u, K = %d\n", j, K + 1);
						fclose(outfile);
						exit (1);
					}
				}
				/*printf("\n");*/
				for (K = 0; K < p; K++)
					FREEMPR(SIGMA[K]);
			}
			ffree((char *)SIGMA, p * sizeof(MPR *));

			ffree((char *)COEFF, GCD_MAX * sizeof(MPI **));
			for (j = 0; j < count; j++)
			{
				ffree((char *)COEFF[j], p * sizeof(MPI *));
				for (i = 0; i < p; i++)
					FREEMPI(COEFF[j][i]);
			}
			FREEMATI(MATI3);
			FREEMATI(Q);
			FREEMATR(LMATRIX);
		}
	}
	}
	}
	}
	}
	}
	}
	return;
}

void GC