readme.c

calc大数库

/* program "readme.c" */
/*
 *  List and description of CALC functions.
 */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "integer.h"
#include "fun.h"

void readme()
{
	char *p, name[10];
	char quit_str[] = "quit";
	char absmod_str[] = "absmod";
	char euclid_str[] = "euclid";
	char gcd_str[] = "gcd";
	char gcdv_str[] = "gcdv";
	char gcda_str[] = "gcda";
	char gcdav_str[] = "gcdav";
	char egcd_str[] = "egcd";
	char sgcd_str[] = "sgcd";
	char lllgcd_str[] = "lllgcd";
	char lllgcd0_str[] = "lllgcd0";
	char lllhermite_str[] = "lllhermite";
	char axb_str[] = "axb";
	char fp_str[] = "fp";
	char inhomfp_str[] = "inhomfp";
	char slv_str[] = "slv";
	char lcm_str[] = "lcm";
	char lcma_str[] = "lcma";
	char length_str[] = "length";
	char pollard_str[] = "pollard";
	char nprime_str[] = "nprime";
	char nprimeap_str[] = "nprimeap";
	char jacobi_str[] = "jacobi";
	char peralta_str[] = "peralta";
	char cong_str[] = "congr";
	char chinese_str[] = "chinese";
	char chinesea_str[] = "chinesea";
	char mthroot_str[] = "mthroot";
	char mthrootr_str[] = "mthrootr";
	char fund_str[] = "fund";
	char pell_str[] = "pell";
	char surd_str[] = "surd";
	char mpower_str[] = "mpower";
	char inv_str[] = "inv";
	char elliptic_str[] = "elliptic";
	char factor_str[] = "factor";
	char tau_str[] = "tau";
	char sigma_str[] = "sigma";
	char mobius_str[] = "mobius";
	char euler_str[] = "euler";
	char lprimroot_str[] = "lprimroot";
	char orderm_str[] = "orderm";
	char lucas_str[] = "lucas";
	char serret_str[] = "serret";
	char collatz_str[] = "collatz";
	char cycle_str[] = "cycle";
	char miller_str[] = "miller";
	char hermite_str[] = "hermite";
	char improvep_str[] = "improvep";
	char mlll_str[] = "mlll";
	char smith_str[] = "smith";
	char rsae_str[] = "rsae";
	char encode_str[] = "encode";
	char decode_str[] = "decode";
	char addcubicr_str[] = "addcubicr";
	char powercubicr_str[] = "powercubicr";
	char ordercubicr_str[] = "ordercubicr";
	char addcubicm_str[] = "addcubicm";
	char powercubicm_str[] = "powercubicm";
	char ordercubicm_str[] = "ordercubicm";
	char convergents_str[] = "convergents";
	char lagrange_str[] = "lagrange";
	char perfectpower_str[] = "perfectpower";
	char leastqnr_str[] = "leastqnr";
	char examples_str[] = "examples";
	char content_str[] = "content";
	char primitive_str[] = "primitive";
	char sturm_str[] = "sturm";
	char rootexp_str[] = "rootexp";
	char log_str[] = "log";
	char log1_str[] = "log1";
	char log2_str[] = "log2";
	char sqroot_str[] = "sqroot";
	char cornacchia_str[] = "cornacchia";
	char patz_str[] = "patz";
	char congq_str[] = "congq";
	char binform_str[] = "binform";
	char ceil_str[] = "ceil";
	char testlog_str[] = "testlog";
	char resultant_str[] = "resultant";
	char discriminant_str[] = "discriminant";
	char deriv_str[] = "deriv";
	char primes_str[] = "primes";
	char sturmsequence_str[] = "sturmsequence";
	char cyclotomic_str[] = "cyclotomic";
	char classnop_str[] = "classnop";
	char classnon_str[] = "classnon";
	char nearint_str[] = "nearint";
	char reduceneg_str[] = "reduceneg";
	char reducepos_str[] = "reducepos";
	char classnop0_str[] = "classnop0";
	char tableneg_str[] = "tableneg";
	char tablepos_str[] = "tablepos";
	char davison_str[] = "davison";
	char raney_str[] = "raney";
	char unimodular_str[] = "unimodular";
	char twoadicsqrt_str[] = "twoadicsqrt";
	char padicsqrt_str[] = "padicsqrt";
	char sigmak_str[] = "sigmak";
	char ramanujan_str[] = "ramanujan";
	char repdefinite_str[] = "repdefinite";
	char powerd_str[] = "powerd";
	char euclid1_str[] = "euclid1";
while(1)
{
	printf("          **************************\n");
	printf("          * List of CALC functions *\n");
	printf("          **************************\n");
	printf("\n");
	printf("absmod, euclid, gcd, gcdv, gcda, gcdav, egcd, sgcd, lllgcd, lllgcd0, \n");
	printf("lllhermite, axb, fp, slv, inhomfp, lcm, lcma, length, \n");
	printf("pollard, nprime, nprimeap, jacobi, peralta, congr, chinese, chinesea, \n");
	printf("mthroot, mthrootr, fund, pell, surd, mpower, inv, elliptic, \n");
	printf("factor, tau, sigma, mobius, euler, lprimroot, orderm, lucas, \n");
	printf("serret, collatz, cycle, miller, hermite, improvep, mlll, smith, \n");
	printf("rsae, encode, decode, addcubicr, powercubicr, ordercubicr, \n");
	printf("addcubicm, powercubicm, ordercubicm, convergents, lagrange, \n");
	printf("perfectpower, leastqnr, content, primitive, sturm, rootexp, log, \n");
        printf("sqroot, cornacchia, patz, congq, binform, ceil, testlog,\n");
        printf("resultant, discriminant, deriv, primes, sturmsequence, cyclotomic,\n");
        printf("classnop, classnon, nearint, reduceneg, reducepos, classnop0,\n");
        printf("tableneg, tablepos, davison, raney, unimodular, twoadicsqrt,\n");
        printf("padicsqrt, sigmak, ramanujan, repdefinite, powerd, euclid1.\n");
	printf("          **************************\n");
	printf("Type a function name or type qu to return to command line:");
	p = Fgets(stdin);
	strcpy(name,p);
	if (strncmp(name, quit_str, 2) == 0)
		break;
	else if (strcmp(name, euclid_str) == 0)
	{
		printf("          **************************\n");
		printf("Usage: euclid(a,b,&q[],&r[],&s[],&t[],&m)\n");
		printf("Description: m=n+1, where the arrays q[0]=NULL,...,q[n],q[n+1]=NULL,\n");
		printf("r[0]=a,r[1]=b,...,r[n+1],\n");
		printf("s[0]=1,s[1]=0,...,s[n+1],\n");
		printf("t[0]=0,t[1]=1,...,t[n+1],\n");
		printf("from Euclid's algorithm are returned and printed in euclid.out:\n");
		printf("r[k]=r[k+1]*q[k+1]+r[k+2], 0 < r[k+2] < r[k+1],\n");
		printf("s[k]=-q[k-1]*s[k-1]+s[k-2],\n");
		printf("t[k]=-q[k-1]*t[k-1]+t[k-2]\n");
		printf("r[n]=gcd(a,b)=s[n]*a+t[n]*b.\n");
		printf("          **************************\n");
		GetReturn();
	}
	else if (strcmp(name, absmod_str) == 0)
	{
		printf("          **************************\n");
		printf("Usage: z=absmod(a,b), b>= 1;\n");
		printf("z=r=a(mod b) if r<=b/2,\n");
		printf("z=r-b) if r>b/2\n");
		printf("          **************************\n");
		GetReturn();
	}
	else if (strcmp(name, gcd_str) == 0)
	{
		printf("          **************************\n");
		printf("Usage: z=gcd(m,n)\n");
		printf("          **************************\n");
		GetReturn();
	}
	else if (strcmp(name, gcdv_str) == 0)
	{
		printf("          **************************\n");
		printf("Usage: z=gcdv(m,n,&s,&t)\n");
		printf("As well as returning z=gcd(m,n),\n");
		printf("this gives numbers s and t satisfying z=s*m+t*n,\n");
		printf("          **************************\n");
		GetReturn();
	}
	else if(strcmp(name, gcdav_str) == 0) {
		printf("\n********************************\n");
		printf("Usage: z=gcdav(a[],&b[])\n");
		printf("z = gcd(a[0],...,a[n-1]). Also gives integers\n");
		printf("b[0],...,b[n-1] satisfying z = b[0]a[0]+...+b[n-1]a[n-1].\n");
		printf("********************************\n");
		GetReturn();
	}
	else if (strcmp(name, gcda_str) == 0)
	{
		printf("          **************************\n");
		printf("Usage: z=gcda(a[])\n");
		printf("z=gcd(a[0],...,a[n-1]),\n");
		printf("where values for a[0],...,a[n-1]\n");
		printf("already exist.\n");
		printf("          **************************\n");
		GetReturn();
	}
	else if (strcmp(name, egcd_str) == 0)
	{
		printf("          **************************\n");
		printf("Usage: z=egcda()\n");

		printf("This does the same as gcda, except that\n");
		printf("one can input the numbers from a file as well.\n");
		printf("The file should have as its first line n, where n\n");
		printf("is the number of integers. The integers should be listed\n");
		printf("on separate lines.  A small multiplier vector P is found\n");
		printf("by LLL based Algorithm 1 of Havas, Majewski and Matthews.\n");
		printf("An m x m$ matrix  whose rows are X_1,...,X_{m-1},P \n");
		printf("is sent to an output file egcdmat.out.\n");
		printf("Here X_1,...,X_{m-1} form a LLL reduced basis\n");
		printf("for the lattice L defined by the equation\n");
		printf("x_1d_1+...+x_md_m=0.\n");
		printf("The inhomogeneous version of the Fincke--Pohst algorithm \n");
		printf("can then be used as an option to find a shortest \n");
		printf("multiplier vector by solving the inequality\n");
          	printf("||P - x_1X_1-...-x_{m-1}X_{m-1}||^2 <= ||P||^2\n");
		printf("in integers x_1,...,x_{m-1}.\n");
		printf("Each time a shorter multiplier vector\n");
		printf("$Q=P-x_1X_1-...-x_{m-1}X_{m-1}$ is found,\n");
		printf("$P$ is replaced by $Q$, until the shortest $Q$ is found.\n");
		printf("The multipliers are sent to an output file called egcdmult.out.\n");
		printf("There is an option for finding all the shortest multipliers.\n");
		printf("          **************************\n");
		GetReturn();
	}
	else if (strcmp(name, sgcd_str) == 0)
	{
		printf("          **************************\n");
		printf("sgcd(): usage: sgcd(N)\n");
		printf("This performs the LLL algorithm on [I_n|NA],\n");
		printf("where A is a column vector of positive integers.\n");
		printf("If N is sufficiently large, the last column will be\n");
		printf("reduced to +-NdE_n, where d=gcd(a[1],...,a[n]).\n");
		printf("Output is sent to sgcdbas.out.\n");
		printf("          **************************\n");
		GetReturn();
	}
	else if (strcmp(name, lllgcd_str) == 0)
	{
		printf("          **************************\n");
		printf("Usage: lllgcd(). This performs a modification of LLL\n");
		printf("which is really a limiting form of sgcd(N) for large N.\n");
		printf("It is superior to egcd() in that it avoids inputting a\n");
		printf("large initial unimodular matrix and instead builds one\n");
		printf("from the identity matrix at the outset. \n");
		printf("The underlying algorithm is explained in a paper at\n");
		printf("http://www.maths.uq.edu.au/~krm/lll.html.\n");
		printf("The multipliers are sent to an output file called lllgcdmult.out.\n");
		printf("The matrix B of that paper is sent to lllgcdmat.out. \n");
		printf("Note: if the shortest vector option is chosen, the last\n");
		printf("row of B has been replaced by this vector.\n");
		printf("There is an option for finding all the shortest multipliers.\n");
		printf("          **************************\n");
		GetReturn();
	}
	else if (strcmp(name, lllgcd0_str) == 0)
	{
		printf("          **************************\n");
		printf("Usage: lllgcd0().  This sits on top of lllgcd()\n");
		printf("and finds a multiplier that in general is better than\n");
		printf("that delivered by lllgcd().\n");
		printf("See the paper at http://www.maths.uq.edu.au/~krm/lll.html.\n");
		printf("The outputs go to lllgcd0mat.out and lllgcd0mult.out.\n");
		printf("          **************************\n");
		GetReturn();
	}
	else if (strcmp(name, lllhermite_str) == 0)
	{
		printf("          **************************\n");
		printf("Usage: lllhermite().  This is a new LLL based algorithm\n");
		printf("for the Hermite normal form HNF(A) of A.\n");
		printf("HNF(A) is sent to lllhermitebas.out, \n");
		printf("while the unimodular transformation matrix P\n");
		printf("is sent to lllhermitetrans.out.\n");
		printf("See the paper at http://www.maths.uq.edu.au/~krm/lll.html.\n");
		printf("          **************************\n");
		GetReturn();
	}
	else if (strcmp(name, axb_str) == 0)
	{
		printf("          **************************\n");
		printf("Usage: axb(). This solves AX=B, where A is mxn,\n");
		printf("X is nx1, B is mx1. The method is MLLL based,\n");
		printf("as in an example of M. Pohst. A short basis is found\n");
		printf("for the nullspace of A and this is used to size-reduce\n");
		printf("an initial large solution.  The option of finding all \n");
		printf("the shortest X is also given. The short solution\n");
		printf("together with all shortest, if requested, are sent to\n");
		printf("axb.out, while the short basis for the nullspace of A\n");
		printf("is sent to axbbas.out.\n");
		printf("See the paper at http://www.maths.uq.edu.au/~krm/lll.html.\n");
		printf("          **************************\n");
		GetReturn();
	}
	else if (strcmp(name, fp_str) == 0)
	{
		printf("          **************************\n");
		printf("Usage: fp(), This is the simplest form of the Fincke-Pohst algorithm.\n");
		printf("This takes an integer matrix with LI rows and a positive integer C\n");
		printf("as input and finds all lattice vectors X with ||X||^2 <= C.\n");
		printf("The vectors found are sent to a file called fp.out. \n");
		printf("It is a good idea to start with a matrix whose rows are LLL reduced.\n");
		printf("          **************************\n");
		GetReturn();
	}
	else if (strcmp(name, inhomfp_str) == 0)
	{
		printf("          **************************\n");
		printf("Usage: inhomfp(). The inhomogeneous version of the Fincke-Pohst algorithm.\n");
		printf("Input: An m x M integer matrix A whose first m-1 rows are LI\n");
		printf("and which are preferably in LLL reduced form.\n");
		printf("A positive integer C is also entered.\n");
		printf("L is the lattice spanned by the first m-1 rows of A\n");
		printf("and P is the last row of A.\n");
		printf("Output: All lattice vectors X of L such that ||X-P||^2 <= C.\n");
		printf("The vectors found are sent to a file called inhomfp.out.\n");
		printf("          **************************\n");
		GetReturn();
	}
	else if (strcmp(name, slv_str) == 0)
	{
		printf("          **************************\n");