?? detailed description of the major calc functions.htm
字號:
<DT>unsigned int EQUALI (MPI *Aptr, MPI *Bptr): i5I.c
<DD><SMALL>Returns 1 if Aptr = Bptr, otherwise = 0.</SMALL>
<DT>unsigned int EQUALR (MPR *Aptr, MPR *Bptr): i5R.c
<DD><SMALL>Returns 1 if Aptr = Bptr, otherwise = 0.</SMALL>
<DT>unsigned int EQMINUSONECI(MPCI *Mptr): i3.c
<DD><SMALL>Returns 1 if Mptr = -1, 0 otherwise.</SMALL>
<DT>unsigned int EQMINUSONECR(MPCR *Mptr): i3.c
<DD><SMALL>Returns 1 if Mptr = -1, 0 otherwise.</SMALL>
<DT>unsigned int EQMINUSONEI(MPI *Mptr): i3.c
<DD><SMALL>Returns 1 if Mptr = -1, 0 otherwise.</SMALL>
<DT>unsigned int EQMINUSONER(MPR *Mptr): i3.c
<DD><SMALL>Returns 1 if Mptr = -1, 0 otherwise.</SMALL>
<DT>unsigned int EQONEI(MPI *Mptr): i3.c
<DD><SMALL>Returns 1 if Mptr = 1, 0 otherwise.</SMALL>
<DT>unsigned int EQONER(MPR *Mptr): i3.c
<DD><SMALL>Returns 1 if Mptr = 1, 0 otherwise.</SMALL>
<DT>unsigned int EQONECI(MPCI *Mptr): i3.c
<DD><SMALL>Returns 1 if Mptr = 1, 0 otherwise.</SMALL>
<DT>unsigned int EQONECR(MPCR *Mptr): i3.c
<DD><SMALL>Returns 1 if Mptr = 1, 0 otherwise.</SMALL>
<DT>unsigned int EQZEROI(MPI *Mptr): i3.c
<DD><SMALL>Returns 1 if Mptr = 0, but 0 otherwise.</SMALL>
<DT>unsigned int EQZEROR(MPR *Mptr): i3.c
<DD><SMALL>Returns 1 if Mptr = 0, but 0 otherwise.</SMALL>
<DT>unsigned int EQZEROCI(MPCI *Mptr): i3.c
<DD><SMALL>Returns 1 if Mptr = 0, but 0 otherwise.</SMALL>
<DT>unsigned int EQZEROCR(MPCR *Mptr): i3.c
<DD><SMALL>Returns 1 if Mptr = 0, but 0 otherwise.</SMALL>
<DT>MPI *EUCLIDI(MPI *Pptr, MPI *Qptr, MPI **Hptr, MPI **Kptr): nfunc.c
<DD><SMALL>Returns gcd(Pptr, Qptr) = Hptr · Pptr + Kptr · Qptr.</SMALL>
<DT>MPI *EUCLIDI1(MPI *Pptr, MPI *Qptr): i5I.c
<DD><SMALL>Returns the length of Euclid's algorithm for Pptr/Qptr.</SMALL>
<DT>void EUCLID(MPI *Aptr, MPI *Bptr, MPI **Q[ ], MPI **R[ ], MPI **S[ ], MPI
**T[ ], MPI **Dptr)
<DD><SMALL>Returns Q[0]=NULL,Q[1],...Q[n],Q[n+1]=NULL,<BR>* R[0],...R[n +
1],<BR>* S[0],...S[n + 1], T[0],...T[n + 1]<BR>* for Euclid's algorithm on
R[0]=Aptr, R[1]=Bptr.<BR>* R[0]=R[1]*Q[1]+R[2]<BR>* R[1]=R[2]*Q[2]+R[3]<BR>*
.....<BR>* R[n-2]=R[n-1]*Q[n-1]+R[n]<BR>* R[n-1]=R[n]*Q[n], R[n+1]=0.<BR>*
S[0]=1,S[1]=0, S[j]=s[j-2]-Q[j-1]*S[j-1],<BR>* T[0]=0,T[1]=1,
T[j]=T[j-2]-Q[j-1]*T[j-1], j=2,...,n+1<BR>* Here *Dptr = n.<BR></SMALL>
<DT>MPI *EULER(MPI *N): primes1.c
<DD><SMALL>Returns Euler's function phi(N).</SMALL>
<DT>FACTOR(Mptr *Nptr): primes1.c
<DD><SMALL>Attempts to factor Nptr using the Multiple Polynomial Quadratic
sieve.<BR>If that fails, it uses the elliptic curve method. (No Peter
Montgomery fine-tuning.)<BR>I suggest one uses it for 55 or less digit
numbers.</SMALL>
<DT>unsigned long *FFI(USL N, USL *b, USL w, USL p): i5m.c
<DD><SMALL>Fast Fourier Interpolation.<BR>Here N is a power of 2, b is an
array of N elements from Z<SUB>p</SUB>,<BR>w is a primitive N-th root of unity
mod p and N | p - 1.<BR>Outputs
a(x)=a[0]x<SUP>0</SUP>+···+a[0]x<SUP>N-1</SUP>, where a(w<SUP>k</SUP>)=b[k], 0
≤ k < N.<BR>(See "Elements of Algebra and Algebraic Computing", J.D.
Lipson, p.303.<BR>I have been unable to free the arrays B and C, due to the
way the recursion works. </SMALL>
<DT>unsigned long *FFP(USL N, USL *a, USL *b, USL m, USL n, USL w, USL p):
i5m.c
<DD><SMALL>Input: arrays a and b of USL's mod p, representing polynomials
<BR>of degrees m, n, respectively; N = 2<SUP>e</SUP> > m + n, N | p - 1. w
is a primitive N-th root of unity mod p.<BR>Output: array c mod p,
representing a(x)b(x).</SMALL>
<DT>MPI *CRA(USL n, USL *a, USL *m): i5m.c
<DD><SMALL>Garner's Chinese Remainder Theorem.<BR>Page 180, <EM>Algorithms for
computer algebra</EM>, K.O. Geddes, S.R. Czapor, G. Labahn.<BR>Here
gcd(m[i],m[j])=1 if i != j.<BR>Returns the least remainder mod(m[0].....m[n])
of u = a[i]mod(m[i]), 0 < =i < = n.</SMALL>
<DT>MPI *FFM(MPI *a, MPI *b, USL K): i5m.c
<DD><SMALL>Returns the product of a=(a[0],...,a[m])<SUB>B</SUB> and
b=(b[0],...,b[n])<SUB>B</SUB>, B=2<SUP>16</SUP>,<BR>m = a->D, n = b->D,
using the Discrete Fast Fourier Transform.<BR>Let M = min(m,n). Then
a(x)b(x)=c(x), where 0 ≤ c[k] < (M+1)B<SUP>2</SUP>.<BR>Using the CRA mod
fp[i] for 0 ≤ i ≤ K-1, enables us to reconstruct c(B),<BR>provided that
fp[0]···fp[K-1] ≥ (M+1)B<SUP>2</SUP>.<BR>We also need m+n < N =
2<SUP>e</SUP>, where N | fp[i] - 1.<BR>If m <B and n < B, then M < B,
then K=3 primes suffice as fp[i]>=B<BR>and we take e>=17.<BR>If m <
2<SUP>26</SUP> and n < 2<SUP>26</SUP>, then M < 2<SUP>26</SUP>, then K=4
primes suffice and we take e > = 27, N = 2^27.<BR>External
variables:<BR>fp[0] = 2013265921, lprimroot[0] = 31, primitive Nth root =
440564289;<BR>fp[1] = 2281701377, lprimroot[1] = 3, primitive Nth root =
129140163;<BR>fp[2] = 3221225473, lprimroot[2] = 5, primitive Nth root =
229807484;<BR>fp[3] = 3489660929, lprimroot[3] = 3, primitive Nth root =
1392672017.<BR>See <EM>Elements of Algebra and Algebraic Computing</EM>, J.D.
Lipson, p.310.<BR>I do not use FFM, as my implementation seems slow. If the
user wants to invoke it, go to i1.c and uncomment the relevant parts of MULTI(
).</SMALL>
<DT>MPI *FIBONACCI(USI n): functions.c
<DD><SMALL>Returns the nth Fibonacci number.</SMALL>
<DT>void FINCKE_POHST(MPMATR *A, MPR *C): i6R.c
<DD><SMALL>Input: A matrix of integers A with LI rows spanning a lattice
L.<BR>Output: The integer vectors X with ||X||<SUP>2</SUP> ≤ C, highest
nonzero coord ≤ 0.<BR>(See <EM>Improved methods for calculating vectors of
short length<BR>in a lattice including a complexity analysis</EM>,<BR>U.
Fincke and M. Pohst, Mathematics of Computation, 44, 1985, 463-471.</SMALL>
<DT>MPI *FINPUTI(FILE *f, unsigned int *uptr): i5I.c
<DD><SMALL>Converts decimal input from stream into an MPI Mptr.<BR>Ignores the
combination '\' followed by '\n'.<BR>If a rubbish character is met before
decimal input, Mptr is set to 0<BR>and 0 is returned. All characters up to and
including the first newline<BR>met are wiped.<BR>If a rubbish character is met
immediately after decimal input,<BR>uptr = 0 is returned and all characters up
to and including <BR>the first newline met are wiped. Otherwise 1 is
returned.<BR>In any case Mptr is set equal to any inputted decimal.</SMALL>
<DT>MPMATI *FINPUTMATI(FILE *infile): i6I.c
<DD><SMALL>Inputs a matrix of MPI's from infile.</SMALL>
<DT>MPR *FINPUTR(FILE *f, unsigned int *uptr): i5R.c
<DD><SMALL>Converts the ratio of two decimal inputs from stream into an
MPR.<BR>uptr = 0 if input fails, 1 if successful.</SMALL>
<DT>void FPRINTI(FILE *outfile, MPI *Mptr): i5I.c
<DD><SMALL>The MPI Mptr is printed in decimal notation to outfile.<BR>No
new-line is incorporated.</SMALL>
<DT>void FPRINTMATI(FILE *outfile, USI i1, USI i2, USI j1, USI j2, MPMATI
*Mptr): i6I.c
<DD><SMALL>Printing an MPMATI to outfile.</SMALL>
<DT>void FPRINTMATR(FILE *outfile, USI i1, USI i2, USI j1, USI j2, MPMATR
*Mptr): i6I.c
<DD><SMALL>Printing an MPMATR to outfile.</SMALL>
<DT>void FPRINTR(FILE *outfile, MPR *Aptr): i5R.c
<DD><SMALL>prints the MPR Aptr as (Aptr->N)/(Aptr->D).</SMALL>
<DT>MPR *FRAC_PARTI(MPI *Aptr, MPI *Bptr): i5R.c
<DD><SMALL>Returns the fractional part of Aptr/Bptr.</SMALL>
<DT>MPR *FRAC_PARTR(MPR *Aptr): i5R.c
<DD><SMALL>Returns the fractional part of Aptr.</SMALL>
<DT>void FREEMATI(MPMATI *Mptr): i6I.c
<DD><SMALL>Frees the storage allocated to the 2-dimensional array
Mptr->V.</SMALL>
<DT>void FREEMATR(MPMATR *Mptr): i6R.c
<DD><SMALL>Frees the storage allocated to the 2-dimensional array
Mptr->V.</SMALL>
<DT>void FREEMPI(MPI *Mptr): i5I.c
<DD><SMALL>Deallocates the space alloted for the MPI Mptr.<BR></SMALL>
<DT>void FREEMPIA(MPI *Mptr): i5I.c
<DD><SMALL>Frees an MPIA previously returned by BUILDMPIA. It will free all
the the MPI's in the MPIA.</SMALL>
<DT>void FREEMPR(MPR *Mptr): i5R.c
<DD><SMALL>Deallocates the space alloted for the MPR Mptr.<BR></SMALL>
<DT>MPI *FUND_UNIT(MPI *D, MPI **Xptr, MPI **Yptr): nfunc.c
<DD><SMALL>This is a program for finding the fundamental unit of
Q(sqrt(D)).<BR>The algorithm is based on:<BR>K. Rosen, <EM>Elementary number
theory and its applications</EM>, p382,<BR>B.A. Venkov, <EM>Elementary Number
theory</EM>, p.62 <BR>D. Knuth, <EM>Art of computer programming</EM>, Vol.2,
p359,<BR>with Pohst's trick of using half the period.<BR>w=(1+sqrt(D))/2 if
D=1 (mod 4), w=sqrt(D) otherwise.<BR>The norm of the fundamental unit Xptr +
Yptr·w is returned.</SMALL>
<DT>MPI *GCD(MPI *Aptr, MPI *Bptr): i5I.c
<DD><SMALL>Returns GCD(|Aptr|, |Bptr|).</SMALL>
<DT>MPI *GCD_ARRAY(MPI *M[ ], unsigned int n): i5I.c
<DD><SMALL>Returns GCD(M[0], ..., M[n - 1]).</SMALL>
<DT>MPI *GCD_ARRAYV(MPI *M[ ], MPI **Y[ ], USI n): nfunc.c
<DD><SMALL>Returns d=gcd(M[0],...,M[n-1]) and an array Y[ ] of MPI's<BR>such
that d = M[0]Y[0]+···+M[n-1]Y[n-1]. Here n > 1.</SMALL>
<DT>unsigned long GCDm(USL m, USL n): i5m.c
<DD><SMALL>Returns gcd(m,n)></SMALL>
<DT>void GetReturn( ): menu.c
<DD><SMALL>Waits for a return to be entered from the keyboard.</SMALL>
<DT>unsigned int GetYN( ): menu.c
<DD><SMALL>Gets a character from the keyboard, making sure it's a<BR>y or an n
(either case). If at first the user doesn't succeed,<BR>he/she tries, tries
again. 0 is returned if n, 1 if y.</SMALL>
<DT>MPI *HALFMOD(MPI *A, MPI *B): i2.c
<DD><SMALL>Here B > 0. Returns R=A(mod B) if R ≤ B/2, otherwise R-B.
</SMALL>
<DT>MPMATI *HERMITE1(MPMATI *Aptr, USI *T, USI nz): i6I.c
<DD><SMALL>(Kannan-Bachem) Returns the Hermite normal form of Aptr.</SMALL>
<DT>MPMATI *HERMITE1P(MPMATI *Aptr, MPMATI *Pptr, MPMATI **Qptr, USI *T, USI
nz): i6I.c
<DD><SMALL>(Kannan-Bachem) Returns the Hermite normal form of Aptr<BT> and a
transforming unimodular matrix Pptr.</SMALL>
<DT>MPMATI *IDENTITYI(USI n): i6I.c
<DD><SMALL>Returns the identity matrix of size n.</SMALL>
<DT>MPI *INPUTI(unsigned int *uptr): i5I.c
<DD><SMALL>Inputs an MPI from the keyboard.<BR></SMALL>
<DT>MPR *INPUTR(unsigned int *uptr): i5I.c
<DD><SMALL>Inputs an MPR from the keyboard.<BR>uptr=1 if no corruption takes
place, else 0.</SMALL>
<DT>MPMATI *INPUTMATI( ): i6I.c
<DD><SMALL>Inputs a matrix of MPI's from stdin.</SMALL>
<DT>MPI *INT0(MPI *Aptr, MPI *Bptr): i2.c
<DD><SMALL>Returns the integer part of Aptr/Bptr,<BR>where Aptr,Bptr >
0.</SMALL>
<DT>MPI *INT0_(MPI *Aptr, unsigned long b): i2.c
<DD><SMALL>Returns the integer part of Aptr/b,<BR>where Aptr > 0 and 0 <
b < R0.</SMALL>
<DT>MPI *INT(MPI *Aptr, MPI *Bptr): i2.c
<DD><SMALL>Returns the integer part of Aptr/Bptr,<BR>where Bptr >
0.</SMALL>
<DT>MPI *INT_(MPI *Aptr, USL b): i2.c
<DD><SMALL>Returns the integer part of Aptr/b, 0 < b < R0.</SMALL>
<DT>MPI *INTI(MPI *Aptr, MPI *Bptr): i2.c
<DD><SMALL>Returns the integer part of Aptr/Bptr.</SMALL>
<DT>MPR *INTR(MPR *Aptr): i5R.c
<DD><SMALL>Returns the integer part of Aptr.</SMALL>
<DT>MPI *INVERSEM(MPI *Nptr, MPI *Mptr): i5m.c
<DD><SMALL>Returns the inverse of Nptr (mod Mptr).<BR>Here gcd(Nptr,Mptr) = 1,
1 ≤ Nptr < Mptr. <BR>(See Knuth, p. 325.)</SMALL>
<DT>MPR *INVERSER(MPR *Aptr): i5R.c
<DD><SMALL>Returns 1/ Aptr.</SMALL>
<DT>unsigned long INVERSEm(USL n, USL m): i5m.c
<DD><SMALL>Returns the inverse of n (mod m).<BR>Here 1 ≤ n < m <
2<SUP>32</SUP>, gcd(n, m) = 1.</SMALL>
<DT>MPI *JACOB(MPI *M, MPI *N): func.c
<DD><SMALL>Returns the Jacobi symbol (M/N), N odd, N > 0.</SMALL>
<DT>int JACOBI(USL n, USL m): qres.c
<DD><SMALL>Returns the Jacobi symbol (n/m), m odd, 0 < n < m.</SMALL>
<DT>MPMATI *JACOBIGCD(MPMATI *DD, MPI **Aptr, USI m): LLLGCD.c
<DD><SMALL>Input: an m x 1 vector DD of positive MPI's.<BR>Output: Aptr = gcd
of the DD[i]. Also we return a set of<BR>multipliers using a version of a
method of Jacobi<BR>A unimodular transforming matrix B is returned.</SMALL>
<DT>void LAGRANGE(POLY P, **AA[], MPI *M): i5I.c
<DD><SMALL>f(x)=a[n]x<SUP>n</SUP>+···+a[0], a[n] > 0, is a polynomial with
integer coefficients, having no rational roots and having exactly one real
positive root x, this being > 1. The method of Lagrange (1769) is used to
find the the first m+1 partial quotients aa[0],···aa[m] of x. WARNING: the
array a[] will be changed after <TT>lagrange </TT>is called.<BR>Then a further
call to <TT>lagrange</TT> will produce subsequent partial quotients. (See
Knuth, Art of computer programming, volume 2, problem 13, 4.5.3.<BR>Also S.
Lang and H. Trotter,<EM>Continued fractions for some algebraic numbers</EM> J.
für Math. 255 (1972) 112-134; Addendum 267 (1974) ibid. 219-220.<BR>E.
Bombieri and A. van der Poorten, <EM>Continued fractions of algebraic
numbers</EM>, Computational algebra and number theory (Sydney, 1992), 137-152,
Math. Appl., 325, Kluwer Acad. Publ.<BR>P. Shiu, <EM>Computation of continued
fractions without input values</EM>, Math. Comp. 64 (1995), no. 211,
1307-1317.</SMALL>
<DT>MPI *LCM(MPI *Aptr, MPI *Bptr): i5I.c
<DD><SMALL>Returns lcm(Aptr,Bptr).</SMALL>
<DT>MPI *LCM_ARRAY(MPIA M): i5I.c
<DD><SMALL>Returns lcm(M[0],...,M[n - 1]).</SMALL>
<DT>MPI *LEASTQNR(MPI *P): qres.c
<DD><SMALL>Returns the least quadratic non-residue mod P.</SMALL>
<DT>unsigned long LENGTHI(MPI *Mptr): i5I.c
<DD><SMALL>Returns the number of decimal digits in the MPI Mptr<BR>increased
by 1 if Mptr is negative.</SMALL>
<DT>unsigned int LENGTHm(USL n): i5m.c
<DD><SMALL>Returns the number of decimal digits in the unsigned int n.</SMALL>
<DT>MPI *LENGTHSQRI(MPMATI *Mptr, USI i): LLL.c
<DD><SMALL>Returns the square of the length of row i of matrix Mptr.</SMALL>
<DT>MPMATI *LLLGCD(MPMATI *DD, MPI **Aptr, USI m, USI m1, USI n1): LLLGCD.c
<DD><SMALL>Input: an m x 1 vector of MPI's.<BR>Output: gcd of the vector of
DD[i]. We return a small set of<BR>multipliers using the LLL method of Havas,
Majewski and Matthews.<BR>matrix B of the algorithm is returned.<BR>(m1, n1)
is usually taken to be (3, 4) for a quick answer,<BR>but (1,1), while slower,
usually provides a shorter basis vectors.</SMALL>
<DT>void LOG(MPI *A, MPI *B, MPI *D, MPI *R, MPIA *M, MPI **L): log.c
<DD><SMALL>Returns an array M[] of L positive integers that are hopefully
partial quotients of log(A)/log(B), using C=D<SUP>R</SUP>.<BR>Here A > B
> 1, D > 1, R ≥ 1.<BR>Uses an algorithm in <A
href="http://www.numbertheory.org/pdfs/log.pdf">manuscript</A></SMALL>
<DT>MPI *LPRIMROOT(MPI *P): primes1.c
<DD><SMALL>Returns the least primitive root mod P, an odd prime;<BR>returns
NULL if factorization of P - 1 is unsuccessful.</SMALL>
<DT>MPI *LUCAS(MPI *N)
<DD><SMALL>Here N is odd, N > 1.<BR>If LUCAS(N) returns 1, then N is a
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -