?? detailed description of the major calc functions.htm
字號:
strong base 2 pseudoprime<BR>and a Lucas probable prime; if it returns 0, then
N is composite.<BR>(See <EM>The Pseudoprimes to
25·10<SUP>9</SUP></EM>,<BR>Mathematics of computation, 35 (1980)
1003-1026.<BR>At the end of this paper it is conjectured that if N is a
strong<BR>base 2 pseudoprime and a Lucas probable prime, then N is in fact a
prime.</SMALL>
<DT>int MAX(int i, int j): i1.c
<DT>int MIN(int i, int j): i1.c
<DT>MPI *MAXMPI(MPI *I, MPI *J): i1.c
<DT>MPI *MINMPI(MPI *I, MPI *J): i1.c
<DT>MPI *MINUSI(MPI *Aptr): i5I.c
<DD><SMALL>Returns -Aptr.</SMALL>
<DT>MPR *MINUSI(MPR *Aptr): i5R.c
<DD><SMALL>Returns -Aptr.</SMALL>
<DT>MPI *MINUSM(MPI *Aptr, MPI *Mptr): i5m.c
<DD><SMALL>Returns -Aptr (mod Mptr). <BR>Here 0 ≤ Aptr < Mptr.</SMALL>
<DT>unsigned long MINUSm(USL a, USL m): i5m.c
<DD><SMALL>Returns -a (mod m) if m > 0.<BR>Here 0 ≤ a < m <
2<SUP>32</SUP>.</SMALL>
<DT>MPI *MINUS_ONEI( ): i5I.c
<DD><SMALL>Returns -1 as an MPI.</SMALL>
<DT>MPR *MINUS_ONER( ): i5R.c
<DD><SMALL>Returns -1 as an MPR.</SMALL>
<DT>MPI *MOBIUS(MPI *N): primes1.c
<DD><SMALL>Returns the Mobius function mu(N),<BR>returns NULL if factorization
unsuccessful.</SMALL>
<DT>MPI *MOD(MPI *Aptr, MPI *Bptr): i2.c
<DD><SMALL>Returns Aptr (mod Bptr), Bptr > 0.</SMALL>
<DT>MPI *MOD0(MPI *Aptr, MPI *Bptr): i2.c
<DD><SMALL>Returns Aptr (mod Bptr), Aptr ≥, Bptr > 0.</SMALL>
<DT>unsigned long MOD0_(MPI *Aptr, unsigned long b): i2.c
<DD><SMALL>Returns Aptr (mod b), Aptr ≥, 0 < b < R0.</SMALL>
<DT>unsigned long MOD_(MPI *Aptr, unsigned long b): i2.c
<DD><SMALL>Returns Aptr (mod b), 0 < b < R0.</SMALL>
<DT>unsigned long MODINT0_(MPI *Aptr, unsigned long b, MPI **Qptr): i2.c
<DD><SMALL>Returns Aptr (mod b) and Qptr = int(Aptr/b).<BR>Here Aptr ≥ 0, b is
a positive integer, b < R0.</SMALL>
<DT>MPI *MPOWER(MPI *Aptr, MPI *Bptr, MPI *Cptr): i5m.c
<DD><SMALL>Returns (Aptr)<SUP>Bptr</SUP> (mod Cptr).<BR>Here Cptr > 0, Bptr
≥ 0.<BR>We use an analogue of the Russian Peasant Multiplication algorithm and
conserve the quantity w=zx<SUP>y</SUP>(mod c).<BR>Initially z=1,x=1,y=b.<BR>If
y is odd, y → y-1, z → z*x(mod c);<BR>if y is even, y → y/2, x →
x<SUP>2</SUP>(mod c).<BR>Eventually y=0. Then w=zx<SUP>0</SUP>(mod c)=z and
the final value of z gives a<SUP>b</SUP>(mod c). </SMALL>
<DT>MPI *MPOWER_(long a, MPI *Bptr, MPI *Cptr) i5m.c
<DD><SMALL>Returns a<SUP>Bptr</SUP> (mod Cptr). <BR>Here 0 < |a| < R0,
Cptr > 0, Bptr ≥ 0.</SMALL>
<DT>MPI *MPOWER_M(MPI *Aptr, USL b, MPI *Cptr): i5m.c
<DD><SMALL>Returns (Aptr)<SUP>b</SUP> (mod Cptr). <BR>Here Cptr > 0, 0 ≤ b
< RO.</SMALL>
<DT>void MTHROOT(MPI *Aptr, MPI *Bptr, unsigned int m, unsigned int r): i8.c
<DD><SMALL>Aptr and Bptr are positive MPI'S. 0 < mr <
R0<SUP>2</SUP>.<BR>The mthroot of Aptr/Bptr is computed to r decimal places, r
≥ 0. </SMALL>
<DT>MPR *MTHROOTR(MPR *Nptr, unsigned int m, unsigned int r): i8.c
<DD><SMALL>The m-throot of the positive MPR Nptr is computed to r decimal
places,<BR>m, r are integers, r ≥ 0, 0 < mr < R0<SUP>2</SUP>.</SMALL>
<DT>void MULT_PADIC(MPIA A, MPIA B, MPI *P, MPIA *PROD, USI m, USI n, USI *l):
p-adic.c
<DD><SMALL>MULT_PADIC forms the product of
a=a[0]+a[1]p+...+a[m]p<SUP>m</SUP><BR>and b=b[0]+b[1]p+...+b[n]p<SUP>n</SUP>,
where a[m] and b[n] are nonzero.<BR>The output is
PROD[0]+PROD[1]p+...+PROD[l]p<SUP>l</SUP>, where PROD[l] is nonzero.<BR>If a
or b is zero, we return 0 at the start, otherwise return l.<BR>The program is
an adaption of one in i1.c from http://www.numbertheory.org/calc/</SMALL>
<DT>MPI *MULTABC(MPI *A, MPI *B, MPI *C): i1.c
<DD><SMALL>Returns A + BC.</SMALL>
<DT>MPR *MULTABCR(MPR *A, MPR *B, MPR *C): i1.c
<DD><SMALL>Returns A + BC.</SMALL>
<DT>MPI *MULTI(MPI *Aptr, MPI *Bptr): i1.c
<DD><SMALL>Returns Aptr·Bptr;.</SMALL>
<DT>MPI *MULTR(MPR *Aptr, MPR *Bptr): i5R.c
<DD><SMALL>Returns Aptr·Bptr;.</SMALL>
<DT>MPI *MULTI3(MPI *A, MPI *B, MPI *C): i1.c
<DD><SMALL>Returns ABC.</SMALL>
<DT>MPR *MULTR3(MPR *A, MPR *B, MPR *C): cubicr.c
<DD><SMALL>Returns ABC.</SMALL> Here 0 ≤ Aptr, Bptr < Mptr.</SMALL>
<DT>MPMATI *MULTMATI(MPMATI *Mptr, MPMATI *Nptr): i6I.c
<DD><SMALL>Returns Mptr·Bptr.</SMALL>
<DT>MPMATR *MULTMATR(MPMATR *Mptr, MPMATR *Nptr): i6R.c
<DD><SMALL>Returns Mptr·Bptr.</SMALL>
<DT>MPI *MULT_I(MPI *Aptr, long b): i1.c
<DD><SMALL>Returns Aptr·b, where |b| < R0.</SMALL>
<DT>MPI *MULT_II(MPI *Aptr, USL b): i1.c
<DD><SMALL>Returns Aptr·b, where b is an USL.</SMALL>
<DT>MPI *MULTM(MPI *Aptr, MPI *Bptr, MPI *Mptr): i5m.c
<DD><SMALL>Returns Aptr·Bptr (mod Mptr).<BR></SMALL>
<DT>unsigned long MULTm(USL a, USL b, USL m): i5m.c
<DD><SMALL>Returns ab (mod m) if m > 0; here 0 ≤ a,b < m <
2<SUP>32</SUP>.</SMALL>
<DT>MPI *NEAREST_INTI(MPI *Aptr, MPI *Bptr): i5I.c
<DD><SMALL>Returns the nearest integer to Aptr/Bptr,<BR>choosing downwards if
half an odd integer.</SMALL>
<DT>MPI *NEAREST_INTR(MPR *Aptr): i5R.c
<DD><SMALL>Returns the nearest integer to Aptr,<BR>choosing downwards if half
an odd integer.</SMALL>
<DT>MPI *NEG(MPI *d, MPI *FLAG, MPI *TABLE_FLAG): reductio.c
<DD><SMALL>Here d < 0 and 1 < |d| < 10<SUP>6</SUP> is squarefree and
d=0 or 1(mod 4).<BR>This is Henri Cohen's Algorithm 5.3.5, p. 228, for finding
the class number h(d) of binary quadratic forms of discriminant d, when d <
0.<BR>If FLAG=1, we only the primitive forms.<BR>If TABLE_FLAG=0, we do not
print any form. This flag was introduced for TABLENEG below.<BR>h(d) is
returned in each case.<BR>If d is the discriminant of an imaginary quadratic
field K, then the primitive forms class-number h(d) is also the class number
of K.<BR>Davenport's <EM>Higher Arithmetic</EM> has a table of forms, which
lists the imprimitive ones with an asterisk.<BR></SMALL>
<DT>MPI *NEXTPRIMEAP(MPI *A, MPI *B, MPI *M): utility.c
<DD><SMALL>Finds the first Lucas probable prime P, A | P - B, M ≤ P.<BR>Here A
is even, B is odd, A > 1 , A > B ≥ 1, gcd(A,B) = 1, M > 1.</SMALL>
<DT>MPI *NEXT_PRIME(MPI *M, USI *hptr): utility.c
<DD><SMALL>Returns a probable prime Q with Q = M + hptr.</SMALL>
<DT>MPI *ONEI( ): i5I.c
<DD><SMALL>Returns 1.</SMALL>
<DT>MPR *ONER( ): i5R.c
<DD><SMALL>Returns 1.</SMALL>
<DT>unsigned int ORDERECP(MPI *X, MPI *Z, MPI *P, MPI *Q, MPI *N): elliptic.c
<DD><SMALL>Calculates the order of the point (X,Y,Z) on the elliptic
curve<BR>Y<SUP>2</SUP>Z=X<SUP>3</SUP>+PXZ<SUP>2</SUP>+QZ<SUP>3</SUP> (mod N),
N a prime.</SMALL>
<DT>MPI *ORDERM(MPI *A, MPI *M): primes1.c
<DD><SMALL>Returns the order of A (mod M).</SMALL>
<DT>MPI *ORDERP(MPI *A, MPI *P): primes1.c
<DD><SMALL>Returns the order of A (mod P), P a prime.</SMALL>
<DT>void PADICSQRT(MPI *A, USI n, MPI *P, MPIA *DIGITS): p-adic.c
<DD><SMALL>PADICSQRT() n > 0, A > 0, A a quadratic residue (mod P),
finds a square-root U of A (mod P), 0 < U < P and returns the first n
digits of a p-adic sqroot x of A. Here x=U (mod P). 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/page3.html">solutions</A>.
</SMALL>
<DT>void PATZ(MPI *D, MPI *N): lagrange.c
<DD><SMALL>Returns the fundamental solutions (x,y) (with x > 0) of
x<SUP>2</SUP>-Dy<SUP>2</SUP>=± N, where D > 1 is not a perfect square and N
is non-zero.<BR>The algorithm goes back to Lagrange and has been strangely
forgotten by textbook writers. (See the <A
href="http://www.numbertheory.org/pdfs/patz.pdf">preprint</A> (pdf 173K) of
Keith Matthews.)</SMALL>
<DT>MPI *PEL(MPI *D, MPI*E, MPI **Xptr, MPI **Yptr): nfunc.c
<DD><SMALL>This finds the least solution of Pell's equation x<SUP>2</SUP> -
Dy<SUP>2</SUP> = ±1.<BR>The algorithm is based on K. Rosen,<BR><EM>Elementary
number theory and its applications</EM>, p382,<BR>B.A. Venkov, <EM>Elementary
Number theory</EM>, p.62 <BR>and D. Knuth, <EM>Art of computer
programming</EM>, Vol.2, p359,<BR>with Pohst's trick of using half the
period.<BR>The partial quotients are printed iff E is nonzero.<BR>The norm of
the least solution is returned.</SMALL>
<DT>void PELL(MPI *Dptr, MPI *Eptr): nfunc.c
<DD><SMALL>This finds the period of the regular continued fraction<BR>of
square-root d, as well as the least solution x,y<BR>of the Pellian equation
x<SUP>2</SUP>-dy<SUP>2</SUP>=±1.<BR>The algorithm is from Sierpinski's
<EM>Theory of Numbers</EM>, p.296.<BR>and Davenport's <EM>The Higher
Arithmetic</EM>, p.109.<BR>Here
sqrt(d)=a[0]+1/a[1]+···+1/a[n-1]+1/2*a[0]+1/···.<BR>The partial quotients are
printed iff Eptr is nonzero.<BR>The length n of the period
a[1],···,a[n-1],2*a[0] is printed.</SMALL>
<DT>MPI *PERFECT_POWER(MPI *N): primes1.c
<DD><SMALL>If N > 1, this returns X if N=X<SUP>k</SUP> for some X, k >
1, otherwise NULL.</SMALL>
<DT>MPI *POLLARD(MPI *Nptr): primes1.c
<DD><SMALL>Pollard's p-1 method of factoring Nptr.</SMALL>
<DT>USI POS(MPI *d): reductio.c
<DD><SMALL>This returns the class number h=h(d) of a real quadratic field
Q(√d). Here 2 < d < 10<SUP>6</SUP> is squarefree and D is the field
discriminant. We locate all reduced irrationals of the form
(b+\sqrt(D))/(2|c|), where c is negative and 4*c divides d-b<SUP>2</SUP>. We
use the PQa continued fraction algorithm of Lagrange to break the set into
disjoint cycles, retaining one number from each cycle. Each reduced number
then gives rise to a reduced form (a,b,c) of discriminant D, where
a=(b<SUP>2</SUP>-D)/(4c).<BR>We are able to also determine if the Pell
equation x<SUP>2</SUP>-D*y<SUP>2</SUP>=-4 has a solution, thereby finding the
norm of the fundamental unit.<BR>(See Henri Cohen's <EM>A course in
computational number theory</EM>, page 260, First Edition.)<BR></SMALL>
<DT>USI POS0(MPI *d): reductio.c
<DD><SMALL>We find the number of classes of binary forms of positive
discriminant d. Here 1 < d < 10<SUP>6</SUP>. Also d is not a perfect
square. We locate all reduced irrationals of the form (b+\sqrt(d))/(2|c|),
where c is negative and 4*c divides d-b<SUP>2</SUP>. We use the PQa continued
fraction algorithm of Lagrange to break the set into disjoint cycles,
retaining one number from each cycle. Each reduced number then gives rise to a
reduced form (a,b,c) of discriminant d, where a=(b<SUP>2</SUP>-d)/(4c). We are
able to also determine if the Pell equation x<SUP>2</SUP>-d*y<SUP>2</SUP>=-4
has a solution, by using the fact that the equation is soluble iff at least
one of the above cycles is odd. If there is no solution, the reduced forms
(-a,b,-c) have to be counted as well. (See G.B. Mathews, <EM>Theory of
Numbers</EM>, 80-81.)<BR>(Also see Henri Cohen's <EM>A course in computational
number theory</EM>, page 260, First Edition.) </SMALL>
<DT>USI POS1(MPI *D, *norm): reductio.c
<DD><SMALL>D is squarefree. This function performs Lagrange's method on all
reduced quadratic irrationals (b+\sqrt(Disc))/2|c|, where 4*c divides
Disc-b<SUP>2</SUP>, Disc being the discriminant. The class-number h(D) of
Q(sqrt(D) is calculated, as well as the norm of the fundamental unit. For use
in TABLEPOS(M,N). </SMALL>
<DT>void POWERD(MPI *A, MPI *B, MPI* D, MPI *N, MPI **AA, MPI **BB): i2.c
<DD><SMALL>Returns (A+B√D)<SUP>N</SUP>=AA+BB√D.</SMALL>
<DT>MPI *POWERI(MPI *Aptr, unsigned n): i1.c
<DD><SMALL>Returns (Aptr)<SUP>n</SUP>, where 0 ≤ n <
R0<SUP>2</SUP>.</SMALL>
<DT>MPR *POWERR(MPR *Aptr, unsigned n): i5R.c
<DD><SMALL>Returns (Aptr)<SUP>n</SUP>, where 0 ≤ n <
R0<SUP>2</SUP>.</SMALL>
<DT>void POWER_CUBICR(MPR *X1, MPR *Y1, MPR **Xptr, MPR **Yptr, MPR *A1, MPR
*A2, MPR *A3, MPR *A4, MPR *A6, unsigned int n): cubicr.c
<DD><SMALL>(Xptr,Yptr)= n(X1,Y1), where 0 ≤ n < R0<SUP>2</SUP> and (X1,
Y1)<BR>is 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>MPI *POWER_I(long a, unsigned n): i1.c
<DD><SMALL>Returns a<SUP>n</SUP>, where 0 ≤ n < R0<SUP>2</SUP>.<BR>a is an
integer, |a| < R0.</SMALL>
<DT>unsigned long POWER_m(USL a, USL y, USL m): i5m.c
<DD><SMALL>Returns a<SUP>y</SUP> (mod m).<BR>Here 0 ≤ a < m < R0 and 0 ≤
y.</SMALL>
<DT>unsigned long POWERm(USL a, MPI *Bptr, USL m): i5m.c
<DD><SMALL>Returns a<SUP>Bptr</SUP> (mod m).<BR>Here 0 ≤ a < m < R0 and
0 ≤ Bptr.</SMALL>
<DT>MPI *PRIME_GENERATOR(MPI *M, MPI *N): primes1.c
<DD><SMALL>Returns and prints the the c primes, (c ≥ 0), in the interval
[m,n], where 1 < m,n < 10<SUP>10</SUP>. Output is sent to
primes.out.</SMALL>
<DT>POLYI PRIMITIVEPI(POLYI Pptr): pI.c
<DD><SMALL>Returns the primitive part of the polynomial Pptr.</SMALL>
<DT>void PRINTI(MPI *Mptr): i5I.c
<DD><SMALL>Prints the MPI Mptr.</SMALL>
<DT>void PRINTR(MPR *Mptr): i5R.c
<DD><SMALL>Prints the MPR Mptr.</SMALL>
<DT>void PRINTMATI(USI i1, USI i2, USI j1, USI j2, MPMATI *Mptr): i6I.c
<DD><SMALL>Prints the matrix Mptr, rows i1-i2, cols j1-j2.</SMALL>
<DT>void PRINTMATR(USI i1, USI i2, USI j1, USI j2, MPMATR *Mptr): i5R.c
<DD><SMALL>Prints the matrix Mptr, rows i1-i2, cols j1-j2.</SMALL>
<DT>unsigned long RANDOMm(USL x): i5m.c
<DD><SMALL>input: seed x, output: a "random number" a x + c (mod m).<BR>a =
1001, m = R0 = 65536, c = 65.<BR>From H. Lüneburg, <EM>On the Rational Normal
Form of Endomorphisms</EM>,<BR>B.I. WissenSchaftsverlag, Mannheim/Wien/Zurich,
1987.<BR>See Knuth Vol 2, Theorem A, p. 16.</SMALL>
<DT>USL RANEY1(MPI *P, MPI *Q, MPI *R, MPI *S): davison.c
<DD><SMALL>Input: a non-singular matrix A=[P,Q;R,S], P,Q,R,S ≥ 0,
A!=I<SUB>2</SUB>, A!=[0,1;1,0].<BR>With L=[1,0;1,1] and R=[1,1;0,1], we
express A uniquely as a product of non-negative powers of L and R, (at least
one is positive) followed by a row-balanced B.<BR>B=[a,b;c,d] is row-balanced
if (a < c & b > d) or (c < a & d > b) and a,b,c ≥ 0.
<BR>The number k of powers of L and R is returned. The maximum number of
partial quotients returned is 10<SUP>6</SUP>.</SMALL>
<DT>MPR *RATIOI(MPI *Aptr, MPI *Bptr): i5R.c
<DD><SMALL>Returns Aptr/Bptr.</SMALL>
<DT>MPR *RATIOR(MPR *Aptr, MPR *Bptr): i5R.c
<DD><SMALL>Returns Aptr/Bptr.</SMALL>
<DT>void readme(): readme.c
<DD><SMALL>Contains the readme manual for CALC.</SMALL>
<DT>MPR *RECIPROCAL(unsigned long n): i5R.c
<DD><SMALL>Returns 1/n, where 0 < n < R0.</SMALL>
<DT>unsigned int REDUCE_NEG(MPI *A, MPI *B, MPI *C): reductio.c
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =