📄 detailed description of the major calc functions.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0046)http://www.numbertheory.org/calc/calc_doc.html -->
<HTML><HEAD><TITLE>DETAILED DESCRIPTION OF THE MAJOR CALC FUNCTIONS</TITLE>
<META http-equiv=Content-Type content="text/html; charset=utf-8">
<STYLE type=text/css>BODY {
FONT-FAMILY: Helvetia, sans-serif
}
A:visited {
TEXT-DECORATION: none
}
A:link {
TEXT-DECORATION: none
}
A:hover {
TEXT-DECORATION: underline
}
H3 {
TEXT-ALIGN: center
}
</STYLE>
<META content="MSHTML 6.00.2900.2180" name=GENERATOR></HEAD>
<BODY bgColor=#ffffff>
<H3 align=center>Detailed description of the major CALC functions</H3>For anyone
interested in using my multiprecison arithmetic programs, the following
functions are the ones that would be useful. There are many others lurking in
the background.<BR>I designed my CALC program along the lines of the calculator
programs hoc 1,2,3 in "The UNIX Programming Environment" by B.W. Kernighan and
R. Pike, Prentice-Hall 1984.<BR>Life is more complicated than in K and R's
calculator program, as I deal with MPI's, whereas K and P deal only with
floating point numbers.<BR>I should add that it has been pointed out to me that
my basic multiplication routine is rather primitive, being along the lines of
Flander's book.<BR>One has to add any new functions to the file <TT>init.c</TT>.
This may occasion the need to fashion a new type of prototype function in
<TT>parse.y</TT>.<BR>There are two basic types that are parsed: a builtin -
which returns an MPI and a builtinv - which does not.<BR>Programming is made
tediously complicated by the need to free objects as soon as possible after they
are created, in order to avoid a possibly massive buildup of program size at
execution time. One way in which I achieve this is to ensure that at program's
end, a variable <CODE>nettbytes</CODE> has final value zero. The calculation of
<CODE>nettbytes</CODE> is switched on in the Makefile.
<P>R0=2<SUP>16</SUP><BR>USI stands for unsigned int<BR>USL stands for unsigned
long<BR>An MPI is a multiprecision integer<BR>An MPMATI is a matrix of
multiprecision integers<BR>An MPR is a multiprecision rational<BR>An MPMATR is a
matrix of multiprecision rationals<BR>An MPIA is an array of MPI's<BR>A POLYI is
a polynomial with MPI coefficients<BR>X is a reserved symbol, for use in
polynomials<BR>Stack is used in STURM and also in the wrappers to functions for
later use in init.c. It is only in the latter context that I use
Stack.<BR></P>In what follows I have made no distinction between *Aptr,**Aptr
and Aptr, in the interests of simplicity.
<HR>
<DL>
<DT>MPI *ABSI(MPI *Aptr): i5m.c
<DD><SMALL>Returns |Aptr|.</SMALL>
<DT>void ADD_TO_MPIA(MPIA MA, MPI *V, USL n): i5I.c
<DD><SMALL>Adds the supplied MPI at the subscript n. If slot already exists,
the MPI at that slot is freed and the new one is added. If n is greater than
the number of slots, then the array is correctly resized and the new MPI is
added. Slots between the previous last slots and the new subscript n are
initialised to zero.</SMALL>
<DT>MPI *ADD0I(MPI *Aptr, MPI *Bptr): i1.c
<DD><SMALL>Returns Aptr+Bptr, Aptr ≥ 0, Bptr ≥ 0.</SMALL>
<DT>MPI *ADD0_I(MPI *Aptr, unsigned long b): i1.c
<DD><SMALL>Returns Aptr+b, Aptr ≥ 0, b < R0.</SMALL>
<DT>MPI *ADDI(MPI *Aptr, MPI *Bptr): i1.c
<DD><SMALL>Returns Aptr+Bptr.</SMALL>
<DT>MPI *ADDM(MPI *Aptr, MPI *Bptr, MPI *Mptr): i5m.c
<DD><SMALL>Returns Aptr+Bptr (mod Mptr), where 0 ≤ Aptr,Bptr <
Mptr.</SMALL>
<DT>MPMATI *ADDMATI(MPMATI *Mptr, MPMATI *Nptr): i6I.c
<DD><SMALL>Returns Aptr+Bptr.</SMALL>
<DT>MPR *ADDR(MPR *Aptr, MPR *Bptr): i5R.c
<DD><SMALL>Returns Aptr+Bptr</SMALL>
<DT>void ADD_CUBICR(MPR *X1, MPR *Y1, MPR *X2, MPR *Y2, MPR **Xptr, MPR
**Yptr, MPR *A1, MPR *A2, MPR *A3, MPR *A4, MPR *A6): cubicr.c
<DD><SMALL>(Xptr,Yptr) is the sum of the two points (X1,Y1) and (X2,Y2) on the
elliptic curve
y<SUP>2</SUP>+A1·xy+A3·y=X<SUP>3</SUP>+A2·X<SUP>2</SUP>+A4·x+A6.<BR>See D.
Husemoller, Elliptic curves, page 25.</SMALL>
<DT>void ADD_ELLIPTIC_Q(MPR *X1, MPR *Y1, MPR *X2, MPR *Y2, MPR **Xptr, MPR
**Yptr, MPR *A, MPR *B): elliptic.c
<DD><SMALL>(Xptr, Yptr) is the sum of the two points (X1,Y1) and (X2,Y2) on
the rational elliptic curve y<SUP>2</SUP>=x<SUP>3</SUP>+AX+B, where
4A<SUP>3</SUP>+27b<SUP>2</SUP> is nonzero.</SMALL>
<DT>MPMATI *ADD_MULT_ROWI(USI p, USI q, MPI *Aptr, MPMATI *Mptr): i6I.c
<DD><SMALL>Returns the matrix obtained by adding Aptr times row p to row q of
Mptr.</SMALL>
<DT>MPMATI *ADD_MULT_ROWI0(USI p, USI q, MPI *Aptr, MPMATI *Mptr): i6I.c
<DD><SMALL>Overwrites Mptr by adding Aptr times row p to row q of
Mptr.</SMALL>
<DT>unsigned long ADDm(USL a, USL b, USL m): i5m.c
<DD><SMALL>Returns a+b(mod m), where 0 ≤ a,b < m <
2<SUP>32</SUP>.</SMALL>
<DT>void AXB(): nfunc.c
<DD><SMALL>This solves the linear system AX=B, where the coefficients of A,X,B
are integers. A short solution is found in the case of solubility, if N(A) is
nontrivial. The method is LLL-based.</SMALL>
<DT>void BASE_PADIC(MPI *B, MPI *N, MPIA *BASE, USI *j): p-adic.c
<DD><SMALL>This gives the base B expansion of N >
0.<BR>BASE[]=BASE[0]+BASE[1]B+ ...+BASE[j]B<SUP>j</SUP>.<BR>The integer is
returned, along with BASE[] </SMALL>
<DT>MPMATI *BASIS_REDUCTION(MPMATI *Bptr, MPMATI **Eptr, USI rowstage, USI m1,
USI n1): LLL.c
<DD><SMALL>Input: Bptr, a matrix of MPI's, whose first row is not
zero.<BR>Output: an MPMATI whose rows form a LLL reduced basis for the lattice
spanned by the rows of Bptr in the sense of the paper "Factoring polynomials
with rational coefficients" by A. K. Lenstra, H. W. Lenstra and L. Lovász,
Math. Ann. 261, 515-534 (1982).<BR>We use the modified version in "Solving
exponential Diophantine equations using lattice basis reduction algorithms" by
B. M. M. De Weger, J. No. Theory 26, 325-367 (1987). A change of basis matrix
Eptr is also returned.<BR>De Weger's algorithm has been changed to cater for
arbitrary matrices whose rows are now in general linearly dependent. <BR>We
use the fact that the Gram Schmidt process detects the first row which is a
linear combination of the preceding rows. We employ a modification of the LLL
algorithm outlined by M. Pohst in J. Symbolic Computation (1987)4, 123-127.
<BR>We call this the MLLL algorithm.<BR>The last sigma rows of the matrix Eptr
are relation vectors.<BR>(m1, n1) is usually taken to be (3, 4) for a quick
answer, but (1,1), while slower, usually provides shorter basis vectors and
multiplier.</SMALL>
<DT>MPI *BIG_MTHROOT(MPI *Aptr, unsigned int m): i8.c
<DD><SMALL>The integer part of the mth root of the positive MPI Aptr, 1 < m
< R0, is obtained by Newton's method, using the integer part function. (See
the article by [<A
href="http://www.numbertheory.org/calc/krm_calc.html#[Mat]">Matthews</A>].)</SMALL>
<DT>unsigned int BINARYB(MPI *N): binary.c
<DD><SMALL>Returns the number of binary digits of N.</SMALL>
<DT>MPI *BINOMIAL(USI n, USI m): i5m.c
<DD><SMALL>returns n choose m, where n ≥ m are unsigned integers.</SMALL>
<DT>MPI *BRENT_POLLARD(MPI *Nptr): primes1.c
<DD><SMALL>The Brent-Pollard method returns a proper factor of a composite MPI
Nptr. (see R. Brent, BIT 20, 176 - 184).</SMALL>
<DT>MPMATI *BUILDMATI(unsigned int m, unsigned int n): i6I.c
<DD><SMALL>Allocates space for an m x n matrix of MPI's.</SMALL>
<DT>MPMATR *BUILDMATR(unsigned int m, unsigned int n): i6R.c
<DD><SMALL>Allocates space for an m x n matrix of MPR's.</SMALL>
<DT>MPI *BUILDMPI(unsigned int n): i5I.c
<DD><SMALL>Mallocs space for an MPI of length n.<BR>If there is an MPI of this
size in the bank, then use it rather than malloc.</SMALL>
<DT>MPIA BUILDMPIA(): i5I.c
<DD><SMALL>Allocates space for an array initially of size 11 (enough to hold
a[0] to a[10] and sets these slots to contain the zero MPI. Extra MPI's are
added using ADD_TO_MPIA.</SMALL>
<DT>MPR *BUILDMPR( ): i5R.c
<DD><SMALL>Mallocs space for an MPR.</SMALL>
<DT>MPI *CEILINGI(MPI *A, MPI *B): i2.c
<DD><SMALL>Returns the least integer not less than A/B.</SMALL>
<DT>MPI *CFRAC_PERIOD(MPI *D): i5I.c
<DD><SMALL>Returns the period of the continued fraction of √D using the
half-period approach of Pohst and Zassenhaus.</SMALL>
<DT>MPI *CHANGE(unsigned long n): i5I.c
<DD><SMALL>Converts n, 0 ≤ n < (R0)<SUP>2</SUP> to an MPI.</SMALL>
<DT>MPI *CHANGEI(long n): i5I.c
<DD>C<SMALL>onverts n, 0 ≤ |n| < R0 to an MPI.</SMALL>
<DT>MPI *CHINESE(MPI *A, MPI *B, MPI *M, MPI *N, MPI **Mptr): nfunc.c
<DD><SMALL>Returns the solution mod Mptr=lcm[M,N] and Mptr) of the
simultaneous congruences X = A (mod M) and X = B (mod N), if soluble;
otherwise returns NULL.</SMALL>
<DT>MPI *CHINESE_ARRAY(MPI *A[ ], MPI *M[ ], MPI **Mptr, USI n): nfunc.c
<DD><SMALL>Returns the solution mod Mptr=lcm[M[0],...,M[n-1] and Mptr) of the
congruences X = A[i] (mod M[i]),0 ≤ i < n, if soluble; otherwise returns
NULL.</SMALL>
<DT>MPMATR *CHOLESKYR(MPMATR *A): i6R.c
<DD><SMALL>Input: The positive definite matrix A.<BR>Output: The Cholesky
decomposition of A.<BR>(See U. Finke and M. Pohst, "Improved methods for
calculating vectors of short length in a lattice, including a complexity
analysis." Math. Comp. 44, 463-471, 1985.</SMALL>
<DT>MPI *COLLATZ(MPI *Dptr, *Eptr): nfunc.c
<DD><SMALL>The Collatz 3x+1 function. The iterates x,T(x),.. are printed iff
Eptr is nonzero.</SMALL>
<DT>MPMATI *COLSUBI(USI p, USI q, MPI *Aptr, MPMATI *Mptr): i6I.c
<DD><SMALL>Returns the result of subtracting Aptr times the p-th column of
Mptr from the q-th.<BR>0 ≤e p, q ≤ Mprt->C - 1.</SMALL>
<DT>MPI *COLSUMI(MPMATI *Mptr, USI j): i9.c
<DD><SMALL>Returns the sum of the elements of column j of Mptr.</SMALL>
<DT>int COMPAREI(MPI *Aptr, MPI *Bptr): i1.c
<DD><SMALL>Compares MPI's: Returns 1 if Aptr > Bptr, 0 if Aptr = Bptr, -1
if Aptr < Bptr.</SMALL>
<DT>int COMPARER(MPR *Aptr, MPR *Bptr): i6R.c
<DD><SMALL>Compares MPR's: Returns 1 if Aptr > Bptr, 0 if Aptr = Bptr, -1
if Aptr < Bptr.</SMALL>
<DT>MPI *CONGR(MPI *A, MPI *B, MPI *M, MPI **N): nfunc.c
<DD><SMALL>Returns the least solution (mod N) of the congruence AX=B(mod M)
(and N), where N = M / gcd(A, M); otherwise returns the null pointer.</SMALL>
<DT>MPI *CONTENTPI(POLYI Pptr): pI.c
<DD><SMALL>Cptr is the content of the polynomial Pptr.</SMALL>
<DT>void CONVERGENTS(MPI *A[], MPI **P[], MPI **Q[], MPI *N): i5I.c
<DD><SMALL>Returns the convergents P[0]/Q[0],...,P[N]/Q[N] to
[A[0];A[1],...,A[n]] as arrays P[ ] and Q[ ].</SMALL>
<DT>unsigned long CONVERTI(MPI *N): i5I.c
<DD><SMALL>Returns N as an unsigned long, providing 0 < N <
2<SUP>32</SUP>.</SMALL>
<DT>MPI *COPYI(MPI *Aptr): i5I.c
<DD><SMALL>Returns a copy of the MPI Aptr.</SMALL>
<DT>MPR *COPYR(MPR *Aptr): i5R.c
<DD><SMALL>Returns a copy of the MPR Aptr.</SMALL>
<DT>MPMATI *COPYMATI(MPMATI *Aptr): i6I.c
<DD><SMALL>Returns a copy of the MPMATI Aptr.</SMALL>
<DT>MPMATR *COPYMATR(MPMATR *Aptr): i6R.c
<DD><SMALL>Returns a copy of the MPMATR Aptr.</SMALL>
<DT>VOID CORNACCHIA(MPI *A, MPI *B, MPI *M): primes1.c
<DD><SMALL>This prints the positive primitive solutions (x,y) of
Ax<SUP>2</SUP>+By<SUP>2</SUP>=M, where A,B,M are positive integers, with
gcd(A,M)=1=gcd(A,B).</SMALL>
<DT>void CYCLE(USL d, MPI *m[ ], MPI *X[ ], USL INFINITY, USL RANGE):
collatz.c
<DD><SMALL>This function searches all trajectories of the d-branched
generalized Collatz function, which start from p, |p| <= RANGE/2 (RANGE an
even integer). INFINITY is an upper bound for the size of a trajectory, above
which the trajecory is deemed to be divergent. Floyd's cycle finding algorithm
is used. Also see <A href="http://www.numbertheory.org/pdfs/survey.pdf">survey
(pdf)</A> by the author.</SMALL>
<DT>USL DAVISON(USL l, USL m, USL N): davison.c
<DD><SMALL>We perform the algorithm of J.L. Davison, <SMALL><EM>An algorithm
for the continued fraction of e<SUP>l/m</SUP></EM>, Proceedings of the Eighth
Manitoba Conference on Numerical Mathematics and Computing (Univ. Manitoba,
Winnipeg, 1978), 169-179, Congress. Numer., XXII, Utilitas Math.</SMALL>
<P>The starting point is a result of R.F.C. Walters in <SMALL><EM>Alternate
derivation of some regular continued fractions</EM>, J. Austr. Math. Soc 8
(1968), 205-212):</SMALL> If<BR>
<P align=center><IMG
src="DETAILED DESCRIPTION OF THE MAJOR CALC FUNCTIONS.files/walters.gif"
align=middle><BR></P>then <EM>p<SUB>n</SUB>/r<SUB>n</SUB></EM> and
<EM>q<SUB>n</SUB>/s<SUB>n</SUB></EM> -> <EM>e<SUP>l/m</SUP></EM><BR>We
first find the least n=n* such that
<EM>p<SUB>n</SUB>,q<SUB>n</SUB>,r<SUB>n</SUB>,s<SUB>n</SUB></EM> are
non-negative and repeatedly apply Raney's <A
href="http://www.numbertheory.org/php/raney.html">factorisation</A> for n*≤ k
≤ n*+N, as in Davison's example in §3.<BR>The number (<EM>count</EM>) of
partial quotients of <EM>e<SUP>l/m</SUP></EM> found is returned.<BR>We cannot
predict the value of <EM>count</EM>, but it becomes positive for sufficiently
large N. We exit if 1,000,000 partial quotients are found.<BR></SMALL>
<DT>POLYI DERIV(P): pI.c
<DD><SMALL>Returns the derivative of P.</SMALL>
<DT>MPI *DISCRIMINANT(POLYI P): pI.c
<DD><SMALL>Returns the discriminant of P, namely
(1/a<SUB>n</SUB>)(-1)<SUP>{n(n-1)/2</SUP> RESULTANT(P, P').<BR>See O. Perron,
Algebra, Vol 1, p.212.</SMALL>
<DT>MPI *DIVM(MPI *Aptr, MPI *Bptr, MPI *Mptr): i5m.c
<DD><SMALL>Returns (Aptr / Bptr) mod (Mptr).<BR>Here 0 ≤ Aptr, Bptr < Mptr
and gcd(Bptr, Mptr) = 1.</SMALL>
<DT>unsigned long DIVm(USL a, USL b, USL m): i5m.c
<DD><SMALL>Returns a / b mod m if m > 0<BR>Here 0 ≤ a, b < m < R0,
gcd(b, m) = 1 if m > 0></SMALL>
<DT>MPI *DOTRI(MPMATI *Mptr, USI i, USI j): i7I.c
<DD><SMALL>Returns the dot product of rows i and j in Mptr.</SMALL>
<DT>MPI *EFACTOR(MPI *N, USI m, USI p): elliptic.c
<DD><SMALL>The elliptic curve method is used to try to find a factor of a
composite number N.<BR>Here m, p < 2<SUP>32</SUP> and 1279 ≥ m > 10, p ≥
1.</SMALL>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -