📄 description of calc.htm
字号:
Here 1 < r is an integer. Also d > 1. We do not guarantee the correctness of the output. d=2 is fastest, but bigger d give more partial quotients.<br>Roughly r partial quotients are outputted. If e=1, the convergents, the integers A[i] and decimal expansion of log<sub>b</sub>a are printed, the latter truncated correct to as many decimal places as possible: the r-1th convergent is compared with the rth convergent and the decimal expansions are truncated from where they differ. e=0 prints only the partial quotients, Output is sent to log.out. (See Algorithm 1 of [<a href="#[mat_log]">Mat_log</a>]<hr WIDTH="100%"> --><A
name=sqroot></A><TT>z=sqroot(a,n,&s[],&m)</TT><BR>This solves
x<SUP>2</SUP> ≡ a (mod n). The number z of solutions mod n is returned. The
solutions have the form ±s[0],...,±s[r] (mod m).<BR>If there is no solution, z=0
and s[0]=NULL are returned.
<HR width="100%">
<A name=cornacchia></A><TT>cornacchia(a,b,m)</TT><BR>See <EM>L'algorithme de
Cornacchia</EM>, A. Nitaj, Expositiones Mathematicae, 358-365. This returns the
positive primitive solutions (x,y) of ax<SUP>2</SUP>+by<SUP>2</SUP>=m, x ≥ y,
where a,b,m are positive integers, with m ≥ a+b, gcd(a,m)=1=gcd(a,b). (Actually
Nitaj also requires gcd(b,m)=1, but this does not seem to be necessary.)
<HR width="100%">
<A name=patz></A><TT>patz(d,n)</TT><BR>This returns the positive primitive
fundamental solutions of the diophantine equation
x<SUP>2</SUP>-d*y<SUP>2</SUP>=±N, where d > 1 is not a perfect square. The
algorithm is from a recent <A
href="http://www.numbertheory.org/pdfs/patz.pdf">paper</A> of the author and is
in essence due to Lagrange 1770.
<HR width="100%">
<A name=congq></A><TT>z=congq(a,b,c,n,&s[])</TT><BR>This solves the
quadratic congruence ax<SUP>2</SUP>+bx+c ≡ 0 (mod n), where gcd(a,n)=1, n >
0. The solutions are s[0],...,s[z-1].
<HR width="100%">
<A name=binform></A><TT>z=binform(a,b,c,n,e)</TT><BR>This solves the diophantine
equation ax<SUP>2</SUP>+bxy+cy<SUP>2</SUP>=N, N non-zero, where
D=b<SUP>2</SUP>-4ac > 0 and is not a perfect square. One solution from each
equivalence class is printed, along with the corresponding solution n of the
congruence n<SUP>2</SUP> ≡ D (mod 4|N|), -|N| < n ≤ |N|.<BR>e=1 is verbose,
e=0 is terse. Output is sent to binform.out. The algorithm goes back to Lagrange
(1770) and described in a paper to be submitted by the author.
<HR width="100%">
<A name=absmod></A><TT>z=absmod(a,b)</TT><BR>z=r=a(mod b) if r ≤ b/2, otherwise
z=r-b.
<HR width="100%">
<A name=ceil></A><TT>z=ceil(a,b)</TT><BR>This finds the least integer z not less
than a/b, where a and b are integers, b nonzero.
<HR width="100%">
<A name=log></A><TT>log(a,b,d,r,&m[],&l)</TT><BR>This delivers with a
high degree of certainty, partial quotients a[s] of log<SUB>b</SUB>a, where a
> b > 1, d> 1, r > 0. l is the number of partial quotients returned.
Output is sent to log.out. (See <A
href="http://www.math.uwaterloo.ca/JIS/VOL5/Jackson/matthews3.html">paper</A>.)
<HR width="100%">
<A name=testlog></A><TT>testlog(a,b,d,m,n)</TT><BR>This runs the
<TT>testlog1(a,b,d,r)</TT> program for r=m,...,n and is recommended in order to
get a good idea of the correct partial quotients of log<SUB>b</SUB>a. Output is
sent to testlog.out. (See <A
href="http://www.math.uwaterloo.ca/JIS/VOL5/Jackson/matthews3.html">paper</A>.)
<HR width="100%">
<A name=resultant></A><TT>r=resultant(p,q)</TT><BR>This returns the resultant of
non-constant polynomials p and q.
<HR width="100%">
<A name=discriminant></A><TT>r=discriminant(p)</TT><BR>This returns the
discriminant of a non-linear polynomial p.
<HR width="100%">
<A name=deriv></A><TT>q=deriv(p)</TT><BR>This returns the derivative of
polynomial p.
<HR width="100%">
<A name=primes></A><TT>c=primes(m,n)</TT><BR>This prints the c primes, (c ≥ 0),
in the interval [m,n], where 1 < m,n < 10<SUP>10</SUP>. Output is sent to
primes.out.
<HR width="100%">
<A name=sturmsequence></A><TT>c=sturmsequence(f,b,e)</TT><BR>This produces the
Sturm sequence for the polynomial f, evaluates the sequence at x=b and
calculates the number c of sign-changes. No output if e=0, output if e=1. f is
checked to see if it is squarefree and nonlinear and that f(b) is nonzero.
<HR width="100%">
<A name=cyclotomic></A><TT>p=cyclotomic(n)</TT><BR>This returns the nth
cyclotomic polynomial, n < 65536. See H. Lüneburg <EM>Galoisfelder,
Kreisteilungskörper und Schieberegisterfolgen</EM>, BI Mannheim 1979 or <A
href="http://www.numbertheory.org/courses/MP473/lectures/lecture7/">MP473
notes</A>.
<HR width="100%">
<A name=classnop></A><TT>h=classnop(d)</TT><BR>This returns the class number
h=h(d) of a real quadratic field Q(√d). Here 1 < d < 10<SUP>6</SUP> is
squarefree and D is the field discriminant.<BR>We locate all reduced irrationals
of the form (b+√D)/(2|c|), where c is negative and 4c 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>-Dy<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>
<HR width="100%">
<A name=classnon></A><TT>h=classnon(d,e)</TT><BR>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>h(d) is returned in each case.<BR>If
e=1, we print only the primitive forms.<BR>If e=0, we print primitive and
imprimitive forms.<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>
<HR width="100%">
<A name=nearint></A><TT>z=nearint(a,b)</TT><BR>Here b > 0. Then z is the
nearest integer to a/b and where z=t, if a/b=1/2+t, t an integer. In fact
nearint(a,b)=(a-absmod(a,b))/b.<BR>
<HR width="100%">
<A name=reduceneg></A><TT>h=reduceneg(a,b,c)</TT><BR>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 h of
steps taken in the reduction is returned.
<HR width="100%">
<A name=reducepos></A><TT>h=reducepos(a,b,c)</TT><BR>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. A unimodular matrix is constructed which converts (a,b,c) to reduced
form. The output is sent to reducepos.out.<BR>Note: d=b<SUP>2</SUP>-4ac > 0,
d is not a perfect square and we assume d < 10<SUP>6</SUP>.<BR><SMALL>(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>
<HR width="100%">
<A name=classnop0></A><TT>h=classnop0(d)</TT><BR>Here 1 < d <
10<SUP>6</SUP> is not a perfect square and d is 0 or 1 (mod 4). Returns the
number h of classes of binary quadratic forms of discriminant d A complete set
of reduced binary forms is given. We locate all reduced irrationals of the form
(b+√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.)
<HR width="100%">
<A name=tableneg></A><TT>h=tableneg(m,n)</TT><BR>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.
<HR width="100%">
<A name=tablepos></A><TT>h=tablepos(m,n)</TT><BR>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.
<HR width="100%">
<A name=davison></A><TT>h=davison(l,m,n)</TT><BR>Here l,m > 0, 10<SUP>5</SUP>
≥ n ≥ 0. We find h partial quotients a[i] of e<SUP>l/m</SUP>. We cannot predict
the value of h. The a[i] are also sent to davison.out. The program stops if
10<SUP>6</SUP> partial quotients a[i] are found.
<HR width="100%">
<A name=raney></A><TT>h=raney(p,q,r,s)</TT><BR>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 h of powers of L and R is returned.<BR>The maximum
number of partial quotients returned is 10<SUP>6</SUP>.<BR>Also <A
href="http://www.numbertheory.org/php/raney.html">BCMATH version</A>.<BR>(See
G.N. Raney, <EM>On continued fractions and finite automata</EM>, Math, Annalen
206 (1973) 265-283.)
<HR width="100%">
<A name=unimodular></A><TT>h=unimodular(p,q,r,s)</TT><BR>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>.)
<HR width="100%">
<A name=twoadicsqrt></A><TT>twoadicsqrt(b,n,&a[])</TT><BR>Here b > 0,
b=8k+1.<BR>Finds n terms a[0]...a[n-1]of the 2-adic square root x of b, x ≡ 1
(mod 4).<BR>Output also sent to 2-adic.out.
<HR width="100%">
<A name=padicsqrt></A><TT>padicsqrt(b,n,p,&a[])</TT><BR>Here b > 0, b a
quadratic residue (mod p), p an odd prime.<BR>First finds a square root u of b
(mod p), 0 < u < p, and finds n terms a[0]...a[n-1]of the p-adic square
root x of b, x ≡ u (mod p).<BR>Output also sent to p-adic.out.<BR>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>.
<HR width="100%">
<A name=ramanujan></A><TT>u=ramanujan(n)</TT><BR>Returns the value of
Ramanujan's tau function, 0 < n < 2<SUP>16</SUP>.
<HR width="100%">
<A name=repdefinite></A><TT>z=repdefinite(a,b,c,m,print_flag)</TT><BR>This
solves the diophantine equation m=ax<SUP>2</SUP>+bxy+cy<SUP>2</SUP>, where
d=b<SUP>2</SUP>-4ac < 0, a > 0, c > 0. See BCMATH version for the <A
href="http://www.numbertheory.org/php/rep_reduceneg.html">algorithm</A> due to
Gauss. print_flag = 1 lists solutions and unimodular transformations, while
print_flag = 0 lists only the solutions. The output is sent to repdefinite.out.
<HR width="100%">
<A name=powerd></A><TT>powerd(a,b,d,n,&aa,&bb)</TT>.<BR>Here (a +
b√d)<SUP>n</SUP> = aa + bb√d.<BR>
<HR width="100%">
<A name=euclid1></A><TT>z=euclid1(a,b)</TT>.<BR>z is the length of Euclid's
algorithm. Here a and b are positive integers.
<HR width="100%">
<A name=cfracperiod></A><TT>z=cfracperiod(d)</TT>.<BR>z is the length of the
period of the continued fraction expansion of √d.
<HR width="100%">
The author is grateful to Peter Adams for help in understanding the mysteries of
Yacc. <BR>Sean Vickery helped in getting the PC version up and running.
<BR>1999/2000 vacation scholar Sean Seefried vastly improved the error handling,
added polynomials to the parser and coded <TT>sturm(), rootexp()</TT> and a much
improved <TT>lagrange()</TT>.
<P><A name=bibliography></A>
<H3>BIBLIOGRAPHY</H3>
<UL>
<LI><A name=akritas></A>[Akr] A. <A
href="http://www.inf.uth.gr/~akritas/index.html">Akritas</A>, <A
href="http://www.wiley.com/WileyCDA/WileyTitle/productCd-0471611638.html"><EM>Elements
of Computer Algebra with Applications</EM></A>, Wiley 1989.
<LI><A name=cantor></A>[Can] D.G. Cantor, P.H. Galyean, H.G. Zimmer,
<EM>Continued Fraction Algorithm for Real Algebraic Numbers</EM>, Math. Comp.
119, 785-791,
<LI><A name=[Dav]></A>[Dav] H. Davenport, <A
href="http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=0521419980"><I>The
Higher Arithmetic</I></A>, Cambridge University Press, 1992.
<LI><A name=[Hav]></A>[Hav] G. Havas, B. Majewski, K.R. Matthews, <A
href="http://www.numbertheory.org/lll.html"><EM>Extended gcd and Hermite
normal form algorithms via lattice basis reduction</EM></A>, Experimental
Mathematics 7 No.2 (1998) 125-136.
<LI><A name=[Knu]></A>[Knu] D.E. Knuth, <I>The Art of Computer Programming,
Volume 2.</I> Addison-Wesley, 1981.
<LI><A name=[Lag]></A>[Lag] J. Lagarias, <I>The 3x+1 problem and its
generalizations,</I> American Math. Monthly, 92 (1985) 3-23. Also see <A
href="http://www.cecm.sfu.ca/organics/papers/lagarias/">Jeff Lagarias' Organic
Mathematics Article on the 3x+1 Problem and its Generalizations</A> and <A
href="http://www.numbertheory.org/3x+1/">The Generalized 3x+1 Mapping</A> by
Keith Matthews.
<LI><A name=[Mat]></A>[Mat] K.R. Matthews, <A
href="http://www.numbertheory.org/keith/mthroot.html"><EM>Computing mth
roots</EM></A>, College Mathematics Journal 19 (1988) 174-176.
<LI><A name=[mat_log]></A>[Mat_log] K.R. Matthews <EM>On a version of Shanks'
algorithm for computing the continued fraction of log<SUB>b</SUB>a</EM> (<A
href="http://www.math.uwaterloo.ca/JIS/VOL5/Jackson/matthews3.html">see
published article</A>)
<LI><A name=[Per]></A>[Per] R. Peralta, <I>A simple and fast probabilistic
algorithm for computing square roots modulo a prime number,</I> I.E.E.E.
Trans. Inform. Theory, IT-32, (1986) 846-847.
<LI><A name=[Po1]></A>[Po1] M. Pohst and H. Zassenhaus,<I> On unit computation
in real quadratic fields,</I> <EM>EUROSAM '79</EM>, Lecture Notes in Computer
Science Vol. 79, (1972) 140-152.
<LI><A name=[Po2]></A>[Po2] M. Pohst and H. Zassenhaus,<I> Algorithmic
Algebraic Number Theory,</I> Cambridge University Press, 1989.
<LI><A name=[Pom]></A>[Pom] C. Pomerance, J.L. Selfridge and S.S. Wagstaff
Jr.,<I> The Pseudoprimes to 25x10<SUP>9</SUP>,</I> Mathematics of Computation,
35 (1980) 1003-1026.
<LI><A name=[Ros]></A>[Ros] K.H. Rosen <A
href="http://www.aw-bc.com/rosen/"><EM>Elementary Number Theory and Its
Applications</EM></A>, (4th edition) Addison-Wesley 2000
<LI><A name=shallit></A>[Rosen-Shallit] D. Rosen, J. Shallit, <EM>A continued
fraction algorithm for approximating all real polynomial roots</EM>, Math.
Magazine, 51 (1978) 112-116.
<LI><A name=[Sie]></A>[Sie] W. Sierpinski,<I> Theory of numbers,</I> PWN,
1964.
<LI><A name=[Sil]></A>[Sil] R.D. Silverman, <I>The multiple polynomial
quadratic sieve,</I> Mathematics of Computation, 48 (1987) 329-339.
<LI><A name=[Sim]></A>[Sim] C.C. Sims, <I>Computing with finitely presented
groups,</I> Cambridge University Press, 1994.
<LI><A name=[Ven]></A>[Ven] B.A. Venkov, <I>Elementary number theory</I>,
Wolters-Noordhoff, 1970.
<LI><A name=[Wag]></A>[Wag] S. Wagon, <I>The Euclidean algorithm strikes
again,</I> American Math. Monthly, 97 (1990) 125-134. </LI></UL>CALC is
maintained by Keith Matthews. <BR>The software is intended as a service to the
number theory community, but the author cannot be held responsible for any
consequences, either direct or indirect, which the use of this package may have.
It can be freely copied for non-commercial purposes.
<P><I><A href="mailto:webmaster@numbertheory.org">Email</A></I> <BR><I><A
href="http://www.numbertheory.org/keith.html">http://www.numbertheory.org/keith.html</A></I>
<P><EM>Last modified 28th September 2007</EM> </P></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -