📄 detailed description of the major calc functions.htm
字号:
<DD><SMALL>This is Gauss's algorithm for reducing a positive definite binary
quadratic form. See L.E. Dickson, <EM>Introduction to the theory of
numbers</EM>, page 69.<BR>The reduced form (A,B,C) satisfies -A < B ≤ A, C
≥ A, with B ≥ 0 if C=A.<BR>The number of steps taken in the reduction is
returned. </SMALL>
<DT>unsigned int REDUCE_POS(MPI *A, MPI *B, MPI *C): reductio.c
<DD><SMALL>Given an indefinite binary quadratic form
ax<SUP>2</SUP>+bxy+cy<SUP>2</SUP>, we use the PQa continued fraction algorithm
to determine a reduced form and thence a cycle of reduced forms.<BR>The length
of the cyle is returned.<BR>Note: d=b<SUP>2</SUP>-4ac > 0, d is not a
perfect square and we assume d < 10<SUP>6</SUP>.<BR>(See <A
href="http://www.numbertheory.org/pdfs/reduce.pdf">explanatory note</A> and
Henri Cohen's <EM>A course in computational number theory</EM>, Edition 1, pp.
257-261.) </SMALL>
<DT>unsigned int REP_DEFINITE(MPI *a, MPI *b, MPI *c, MPI *m, USI print_flag):
reductio.c
<DD><SMALL>Given a positive definite binary quadratic form
ax<SUP>2</SUP>+bxy+cy<SUP>2</SUP>, we use an algorithm of Gauss to determine
if a given positive integer m is expressible as m =
ax<SUP>2</SUP>+bxy+cy<SUP>2</SUP>, x and y integers, gcd(x,y) = 1. <BR>Note:
Here d = b<SUP>2</SUP> - 4ac < 0, a > 0, c > 0.<BR>(See L.E. Dickson,
<EM>Introduction to the theory of numbers</EM>, pages 74-75.)<BR>print_flag =
1 gives the solutions and unimodular transformations, while print_flag = 0
gives only the solutions. </SMALL>
<DT>void ROOTEXPANSION(Stack s): roots.c
<DD><SMALL>Here POLYI P = stackPop(s), MPI *M = stackPop(s). This finds the
first M partial quotients of the continued fraction expansion of all real
roots of the supplied polynomial P using Lagrange's method and methods
presented in a paper by Cantor, Galyean and Zimmer.</SMALL>
<DT>MPMATI *ROWSUBI(USI p, USI q, MPI *Aptr, MPMATI *Mptr): i6I.c
<DD><SMALL>Updates Mptr: subtracts Aptr x the p-th row of Mptr from the
q-th.<BR>0 ≤ p, q < Mprt->R.</SMALL>
<DT>MPI *ROWSUMI(MPMATI *Mptr, USI i): i9.c
<DD><SMALL>Returns the sum of the elements in row i of Mptr.<BR>0 ≤ i <
Mptr->R.</SMALL>
<DT>int RSV(MPI *Aptr, MPI *Bptr): i1.c
<DD><SMALL>Returns 1 if |Aptr| > |Bptr|,<BR>0 if |Aptr| = |Bptr|, -1 if
|Aptr| < |Bptr|.</SMALL>
<DT>void RSV_PADIC(MPIA A, MPIA B, USI m, USI n): p-adic.c
<DD><SMALL>RSV_PADIC() is an adaption of one in i1.c and returns 1,0,-1
according as A >,=,< B.<BR>It is assumed that A and B are to the same
base. </SMALL>
<DT>unsigned long RUSSm(USL a, USL b, USL c, USL p): i5m.c
<DD><SMALL>input: unsigned long ints a, b, c, p, with p > 0.<BR>output: a +
bc (mod p).<BR>Russian Peasant multiplication algorithm. Uses the
identities<BR>RUSSm(a, b, 2c, p) = RUSSm(a, 2b, c, p),<BR>RUSSm(a, b, c + 1,
p) = RUSSm(a + b, b, c, p).<BR>If a, b, c and p are less than 2<SUP>32</SUP>,
so is RUSSm(a, b, c, p).<BR>From H. Lüneburg, <EM>On the Rational Normal Form
of Endomorphisms</EM>,<BR>B.I. WissenSchaftsverlag, Mannheim/Wien/Zurich,
1987, pp 18-19.<BR>Lüneburg's restriction to 2p<2<SUP>32</SUP> removed by
me on 18/4/94.</SMALL>
<DT>void SCHNORRGCD(MPI *N): nfunc.c
<DD><SMALL>Applies LLL to [I<SUB>m</SUB>|ND] with N large<BR>to get small
multipliers for the extended gcd problem.<BR>See [<A
href="http://www.numbertheory.org/calc/krm_calc.html#[Mat]">Matthews</A>].)</SMALL>
<DT>void SERRET(MPI *P, MPI **Xptr, MPI **Yptr): nfunc.c
<DD><SMALL>This program finds positive integers X, Y such
that<BR>X<SUP>2</SUP>+Y<SUP>2</SUP>=P, where P=4n=1 is a prime.<BR>The
algorithm goes back to Serret and is from the book <BR><EM>Computational
methods in number theory, part 1</EM>,<BR>edited by H.W. Lenstra and R.
Tijdeman.</SMALL>
<DT>MPI *SIGMA(MPI *N): primes1.c
<DD><SMALL>Returns sigma(N), the sum of the divisors of N,<BR>Returns NULL if
factorization unsuccessful.</SMALL>
<DT>MPR *SLVECTOR(MPMATR *A, MPR *C, MPR **VALUE): i6R.c
<DD><SMALL>Input: A matrix of integers A with LI LLL reduced rows spanning a
lattice L. C = length-squared of a small lattice vector. Output: if 0 is
returned, this means that VALUE is the shortest length. Otherwise a shorter
length is returned and VALUE will be NULL.<BR>Used in nfunc.c, in SLVECTORX(),
starting with a LLL-reduced matrix and C=||A<SUB>1</SUB>||<SUP>2</SUP>,
eventually 0 is returned. Then FINCKE-POHST is applied to get all the shortest
vectors in L with highest nonzero coord > 0 are printed. <BR>(See "Improved
methods for calculating vectors of short length in a lattice, including a
complexity analysis, U. Fincke and M. Pohst, Mathematics of Computation, 44,
1985, 463-471.)</SMALL>
<DT>MPI **SMITHI(MPMATI *Mptr, MPMATI **Pptr, MPMATI **Qptr, USI *ptr, MPI
*Eptr): i9.c
<DD><SMALL>Returns the invariant factors of Mptr.<BR>Pptr and Qptr are
invertible matrices such that Pptr·Mptr·Qptr<BR>is the Smith normal form Nptr.
ptr is the number of invariant factors.<BR>See <EM>Rings, Modules and Linear
Algebra</EM>, B. Hartley and T.O. Hawkes,<BR>Chapman and Hall, 1970. We use a
pivoting strategy suggested by George Havas. Eptr is the cutoff above which we
bring in MLLL.</SMALL>
<DT>MPI **SMITHI1(MPMATI *Mptr, USI *ptr, MPI *Eptr): i9.c
<DD><SMALL>Same as SMITHI, but with no transforming matrices.</SMALL>
<DT>void SPRINTI(char *buffer, MPI *Mptr): i5I.c
<DD><SMALL>The decimal digits of the MPI Mptr are placed in the string
buffer.<BR>No new-line is incorporated. </SMALL>
<DT>void SPRINTR(char *buffer, MPR *Aptr): i5R.c
<DD><SMALL>Prints the MPR Aptr as (Aptr->N)/(Aptr->D).</SMALL>
<DT>MPI *SQROOT1(MPI *A, MPI *P, USL n): primes1.c
<DD><SMALL>This returns a solution of x<SUP>2</SUP> ≡ A (mod P<SUP>n</SUP>),
where P is an odd prime not dividing A. Returns -1 otherwise.<BR>Let
d=gcd(a,p<SUP>n</SUP>).<BR>Case 1: d=1. Use the standard recursive approach -
two solutions if
soluble.<BR> If
P=2, care is needed, as in the case of solubility, (i) there is 1 solution if
n=1, (ii) 2 solutions if n=2 and (iii) 4 solutions if n ≡ 3.<BR>Case 2:
d=P<SUP>n</SUP>. Then x=0 is the solution.<BR>Case 3: d=P<SUP>r</SUP>, 1 <
r < n. Write a=P<SUP>r</SUP>A, where P does not divide A.<BR>
<OL>
<LI>If r is odd, there is no solution.
<LI>If r is even, say r=2R. Put x=P<SUP>R</SUP>X.<BR>Then X<SUP>2</SUP> ≡ A
(mod P<SUP>n-2R</SUP>), which reduces to Case 1. </LI></OL></SMALL>
<DT>MPI *SQROOT2(MPI *A, USL n): primes1.c
<DD><SMALL>This returns a solution of x<SUP>2</SUP> ≡ A (mod 2<SUP>n</SUP>), A
odd. Returns -1 otherwise. Also returns a global variable
<TT>sqroot2_number</TT>=1,2,4 if n=1,2,or n > 2. This variable is used in
SQROOT</SMALL>
<DT>MPI *SQROOT3(MPI *A, MPI *P, USL n, MPI**EXPONENT): primes1.c
<DD><SMALL>This returns a solution of x<SUP>2</SUP> ≡ A (mod P<SUP>n</SUP>),
where P is an odd prime possibly dividing A. Returns -1 otherwise. Also
returns a "reduced moduli" explained as follows:<BR>If P does not divide A,
the story is well-known.<BR>If P divides A, there are two cases:<BR>(i)
P<SUP>n</SUP> divides A,<BR>(ii) P<SUP>n</SUP> does not divide A.<BR>In case
(i) there are two cases:<BR>(a) n=2m+1, (b) n=2m.<BR>In case (a), the solution
is x ≡ 0 (mod P<SUP>(m+1)</SUP>).<BR>In case (b), the solution is x ≡ 0 (mod
P<SUP>m</SUP>).<BR>(These are called reduced moduli and are returned as
EXPONENT. This variable is used in SQROOT.)<BR>In case (i)
gcd(A,P<SUP>n</SUP>)=P<SUP>r</SUP>, r < n. If r is odd, no solution.<BR>If
r=2m, write x=(P<SUP>m</SUP>)*X, A=(P<SUP>2m</SUP>)*A1, P not dividing
A1.<BR>Then x<SUP>2</SUP> ≡ A (mod P<SUP>n</SUP>) becomes X<SUP>2</SUP> ≡ A1
(mod P<SUP>n-2m</SUP>).<BR>If P is odd, this has 2 solutions X mod
P<SUP>n-2m</SUP> and we get two solutions x (mod P<SUP>n-m</SUP>). If P=2, we
get 1 solution mod (2<SUP>n-m</SUP>) if n-2m=1, 2 solutions mod
(2<SUP>n-m</SUP>) if n-2m=2, 4 solutions mod (2<SUP>n-m</SUP>) if n-2m > 2.
</SMALL>
<DT>MPI *SQROOT(MPI *A, MPI *N, MPIA *SOL, MPI **MODULUS, USI *lptr):
primes1.c
<DD><SMALL>This finds the solutions of x<SUP>2</SUP>≡A (mod N) as residue
classes ±SOL[0],...,±SOL[lptr-1] (mod MODULUS), where 0 ≤ SOL[i] < MODULUS.
The number of solutions mod N is returned. If there is no solution, -1 is
returned, SOL[0]=NULL and lptr=0.</SMALL>
<DT>MPI *SQRTM(MPI *x, MPI *p): qres.c
<DD><SMALL>Calculates sqrt(x) (mod p) using <EM>A simple and fast
probabilistic<BR>algorithm for computing square roots modulo a prime
number</EM>,<BR>I.E.E.E. Trans. Inform. Theory, IT-32, 1986, 846-847, R.
Peralta.<BR>Here x is a quadratic residue mod p. x can be negative.</SMALL>
<DT>unsigned long SQRTm(USL x, USL p): qres.c
<DD><SMALL>Returns sqrt(x) (mod p), as above. Here 1 ≤ x < p.<BR>x is a
quadratic residue mod p.</SMALL>
<DT>Stack STURM(POLYI P): roots.c
<DD><SMALL>Returns a stack of intervals about each of the real roots of P.
Each interval contains only one root. If there are no roots, it returns an
empty stack. P is supposed to have no rational roots, but is not necessarily
squarefree.</SMALL>
<DT>void SUB_PADIC(MPIA A, MPIA B, MPI *P, MPIA *DIFF, USI m, USI n, USI *l):
p-adic.c
<DD><SMALL>SUB0_PADIC() is an adaption of SUB0_I() in i1.c.<BR>Here A ≥ B and
returns l and the array DIFF[]=A-B=DIFF[0]+DIFF[1]P+...+DIFF[l]P<SUP>l</SUP>.
</SMALL>
<DT>MPI *SUB0I(MPI *Aptr, MPI *Bptr): i1.c
<DD><SMALL>Returns Aptr-Bptr, where Aptr ≥ Bptr ≥ 0.</SMALL>
<DT>MPI *SUB0_I(MPI *Aptr, unsigned long b): i1.c
<DD><SMALL>Returns Aptr-b, where Aptr ≥ b ≥ 0.</SMALL>
<DT>MPI *SUBI(MPI *Aptr, MPI *Bptr): i1.c
<DD><SMALL>Returns Aptr-Bptr.</SMALL>
<DT>MPR *SUBR(MPR *Aptr, MPR *Bptr): i5R.c
<DD><SMALL>Returns Aptr-Bptr.</SMALL>
<DT>MPI *SUBM(MPI *Aptr, MPI *Bptr, MPI *Mptr): i5m.c
<DD><SMALL>returns Aptr - Bptr (mod Mptr). <BR>Here 0 ≤ Aptr, Bptr <
Mptr.</SMALL>
<DT>unsigned long SUBm(USL a, USL b, USL m): i5m.c
<DD><SMALL>Returns a - b (mod m) if m > 0; here 0 ≤ a, b < m <
2<SUP>32</SUP>.</SMALL>
<DT>MPI *SUBRESULTANT(POLYI P, POLYI Q): pI.c
<DD><SMALL>This returns the resultant of P and Q, using the
subresultant<BR>algorithm of p. 130. E. Kaltofen, G. E. Collins etc, Algorithm
4.5.<BR>similar to Knuth, Algorithm C, p. 410. </SMALL>
<DT>unsigned int SURD(MPI *D, MPI *T, MPI *U, MPI *V): nfunc.c
<DD><SMALL>This function uses the continued fraction algorithm expansion
<BR>in K. Rosen, <EM>Elementary Number theory and its
applications</EM>,<BR>p.379-381 and Knuth's <EM>The art of computer
programming</EM>,<BR>Vol.2, p. 359. It locates the first complete quotient
that is reduced<BR>and then uses the function REDUCED(D,U,V,i) above to locate
and return<BR>the period of the continued fraction expansion of
(U+T*sqrt(D))/V. </SMALL>
<DT>MPMATI *SWAP_COLSI(USI p, USI q, MPMATI *Mptr): i6I.c
<DD><SMALL>Interchanges cols p and q (C notation) of Mptr.</SMALL>
<DT>MPMATI *SWAP_COLSI1(USI p, USI q, MPMATI *Mptr): i6I.c
<DD><SMALL>Interchanges cols p and q (C notation) of Mptr.<BR>Updates
Mptr.</SMALL>
<DT>MPMATI *SWAP_ROWSSI(USI p, USI q, MPMATI *Mptr): i6I.c
<DD><SMALL>Interchanges rows p and q (C notation) of Mptr.</SMALL>
<DT>MPMATI *SWAP_ROWSSI1(USI p, USI q, MPMATI *Mptr): i6I.c
<DD><SMALL>Interchanges rows p and q (C notation) of Mptr.</SMALL>
<DT>void SelOpt( ): menu.c
<DD><SMALL>This function simply prints the "SELECT OPTION: " prompt.</SMALL>
<DT>USL TABLENEG(MPI *M, MPI *N): reductio.c
<DD><SMALL>Here 1 ≤ m ≤ n < 10<SUP>6</SUP>. Calculates h(-d) for all
squarefree d with m ≤ d ≤ n. The number h of squarefree d in the range is
returned. The output is also sent to tableneg.out. </SMALL>
<DT>USL TABLEPOS(MPI *M, MPI *N): reductio.c
<DD><SMALL>Here 2 ≤ m ≤ n < 10<SUP>6</SUP>. Calculates h(d) for all
squarefree d with m ≤ d ≤ n. The number h of squarefree d in the range is
returned. The output is also sent to tablepos.out. </SMALL>
<DT>MPI *TAU_COMPOSITE(USI n): primes1.c
<DD><SMALL>Returns the value of Ramanujan's tau function by computing its
value at prime power factors of n. See <A
href="http://www.numbertheory.org/php/tau.html">BCMATH program</A>. </SMALL>
<DT>MPI *TAU_PRIMEPOWER(USI n, USI p): primes1.c
<DD><SMALL>Computes the value of tau(p<SUP>n</SUP>), p a prime. </SMALL>
<DT>MPI *TAU(USI n)
<DD><SMALL>Returns the value of Ramanujan's tau function without using the
prime power factorization of n. It is used in <TT>TAU_PRIMEPOWER</TT>.
</SMALL>
<DT>void TESTLOG(MPI *A, MPI *B, MPI *D, MPI *M, MPI *N): log.c
<DD><SMALL>Runs TESTLOG1(A,B,D,R) for R=M,...,N.<BR>This gives a good idea of
the true partial quotients of log(a)/log(b).</SMALL>
<DT>void TESTLOG1(MPI *A, MPI *B, MPI *D, MPI *R): log.c
<DD><SMALL>This is similar to LOG, but is for use in TESTLOG2.</SMALL>
<DT>MPMATI *TRANSPOSEI(MPMATI *Mptr): i6I.c
<DD><SMALL>Returns the transpose of Mptr.</SMALL>
<DT>MPI *TWOI( ): i5I.c
<DD><SMALL>Returns 2.</SMALL>
<DT>void TryAgain( ): menu.c
<DD><SMALL>Prints "Try again"</SMALL>
<DT>void TWOADICSQRT(MPI *A, USI n, MPIA *DIGITS): p-adic.c
<DD><SMALL>TWOADICSQRT() n > 0, returns the first n binary digits of a
2-adic sqroot x of a positive integer a=8k+1. Here x=1 (mod 4). See <A
href="http://www.numbertheory.org/courses/MP313/lectures/lecture23/page3.html">lectures</A>
and <A
href="http://www.numbertheory.org/courses/MP313/solns/soln3/page1.html">solutions</A>.
</SMALL>
<DT>USL UNIMODULAR(MPI *P, MPI *Q, MPI *R, MPI *S): davison.c
<DD><SMALL>This program expresses a unimodular matrix A=[p,q;r,s]
!=I<SUB>2</SUB> or U=[0,1;1,0] with non-negative coefficients, as a product of
the type P, UP, PU, or UPU, where P is a product of matrices of the form
U<SUB>a</SUB>=[a,1;1,0], a>0.<BR>The representation is unique. <BR>(See
Kjell Kolden, <EM>Continued fractions and linear substitutions</EM>, Arch.
Math. Naturvid. 50 (1949), 141-196.<BR>Also see the corresponding <A
href="http://www.numbertheory.org/php/unimodular.html">BCMATH program</A>.)
</SMALL>
<DT>MPI *ZEROI( ): i5I.c
<DD><SMALL>Returns 0.</SMALL>
<DT>MPR *ZEROR( ): i5R.c
<DD><SMALL>Returns 0.</SMALL>
<DT>MPMATI *ZEROMNI(USI m, USI n): i6I.c
<DD><SMALL>Returns the zero max n matrix.</SMALL>
<DT>MPMATR *ZEROMNR(USI m, USI n): i6R.c
<DD><SMALL>Returns the zero max n matrix.</SMALL>
<DT>void init( ): init.c
<DD><SMALL>Install built-in function names in table.</SMALL>
<DT>void initv( ): init.c
<DD><SMALL>Install built-in void function names in table.</SMALL> </DD></DL>
<P><EM>Last modified 27th April 2004</EM> </P></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -