“Euclidean Algorithm”的概念、定义、习题解题方法及翻译-数学辞典

单词

Euclidean Algorithm

释义

Euclidean Algorithm

An Algorithm for finding the Greatest Common Divisor of two numbers and , also called Euclid'salgorithm. It is an example of a P-Problem whose time complexity is bounded by a quadratic function of thelength of the input values (Banach and Shallit). Let , then find a number which Dividesboth and (so that and ), then also Divides since

(1)

Similarly, find a number

which Divides

and

(so that

and

), then

Divides

since

(2)

Therefore, every common Divisor of

and

is a common Divisor of

and

, so the procedure can be iteratedas follows

			(3)
			(4)
			(5)
			(6)
			(7)

where

. Lamé showed that the number of steps needed to arrive at the GreatestCommon Divisor for two numbers less than

(8)

where

is the Golden Mean, or

times the number of digits in the smaller number. Numerically, Lamé's expression evaluates to

(9)

As shown by Lamé's Theorem, the worst case occurs when the Algorithm is applied to twoconsecutive Fibonacci Numbers. Heilbronn showed that the average number of steps is

for all pairs

with

. Kronecker

showed that the shortestapplication of the Algorithm uses least absolute remainders. The Quotients obtained aredistributed as shown in the following table (Wagon 1991).

Quotient
1	41.5
2	17.0
3	9.3

For details, see Uspensky and Heaslet (1939) or Knuth (1973). Let be the number of divisions required tocompute using the Euclidean algorithm, and define if . Then

(10)

Define the functions

			(11)
			(12)
			(13)

where

is the Totient Function,

is the average number of divisions when

is fixed and

chosen atrandom,

is the average number of divisions when

is fixed and

is a random number coprime to

, and

is the average number of divisions when

and

are both chosen at random in

. Norton (1990)showed that

(14)

where

is the von Mangoldt Function and

is Porter's Constant. Porter (1975) showed that

(15)

and Norton (1990) proved that

(16)

There exist 22 Quadratic Fields in which there is a Euclidean algorithm (Inkeri 1947).

See also Ferguson-Forcade Algorithm

References

Bach, E. and Shallit, J. Algorithmic Number Theory, Vol. 1: Efficient Algorithms. Cambridge, MA: MIT Press, 1996.

Courant, R. and Robbins, H. ``The Euclidean Algorithm.'' §2.4 in Supplement to Ch. 1 in What is Mathematics?: An Elementary Approach to Ideas and Methods, 2nd ed. Oxford, England: Oxford University Press, pp. 42-51, 1996.

Dunham, W. Journey Through Genius: The Great Theorems of Mathematics. New York: Wiley, pp. 69-70, 1990.

Finch, S. ``Favorite Mathematical Constants.'' http://www.mathsoft.com/asolve/constant/porter/porter.html

Inkeri, K. ``Über den Euklidischen Algorithmus in quadratischen Zahlkörpern.'' Ann. Acad. Sci. Fennicae. Ser. A. I. Math.-Phys. 1947, 1-35, 1947.

Knuth, D. E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 2nd ed. Reading, MA: Addison-Wesley, 1973.

Knuth, D. E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 2nd ed. Reading, MA: Addison-Wesley, 1981.

Norton, G. H. ``On the Asymptotic Analysis of the Euclidean Algorithm.'' J. Symb. Comput. 10, 53-58, 1990.

Porter, J. W. ``On a Theorem of Heilbronn.'' Mathematika 22, 20-28, 1975.

Uspensky, J. V. and Heaslet, M. A. Elementary Number Theory. New York: McGraw-Hill, 1939.

Wagon, S. ``The Ancient and Modern Euclidean Algorithm'' and ``The Extended Euclidean Algorithm.'' §8.1 and 8.2 in Mathematica in Action. New York: W. H. Freeman, pp. 247-252 and 252-256, 1991.

随便看

数学辞典收录了8975条数学词条，基本涵盖了常用数学知识及数学英语单词词组的翻译及用法，是数学学习的有利工具。