The euclidean algorithm for computing the greatest common divisor of two integers is, as D. E. Knuth has remarked, ''the oldest nontrivial algorithm that has survived to the present day.'' Credit for t...
详细信息
The euclidean algorithm for computing the greatest common divisor of two integers is, as D. E. Knuth has remarked, ''the oldest nontrivial algorithm that has survived to the present day.'' Credit for the first analysis of the running time of the algorithm is traditionally assigned to Gabriel Lame, for his 1844 paper. This article explores the historical origins of the analysis of the euclidean algorithm. A weak bound on the running time of this algorithm was given as early as 1811 by Antoine-Andre-Louis Reynaud. Furthermore, Lame's basic result was known to Emile Leger in 1837, and a complete, valid proof along different lines was given by Pierre-Joseph-Etienne Finck in 1841. (C) 1994 Academic Press, Inc.
The article discusses Euclid's lemma on the fundamental theorem of arithmetic. It questions whether Euclid used the euclidean algorithm essentially. It assumes that the Pythagorean proportionality is transitive, f...
详细信息
The article discusses Euclid's lemma on the fundamental theorem of arithmetic. It questions whether Euclid used the euclidean algorithm essentially. It assumes that the Pythagorean proportionality is transitive, filling the gap that uses porism to the euclidean algorithm. Algebraic gcds and prime factorization are significant properties on the transitivity of Pythagorean proportionality. It concludes that Euclid failed to use the porism and that the Pythagorean proportionality is not as the case of Eudoxean proportionality but rather it is specially suited for the study of divisibility.
The length of the continued-fraction expansion of a rational number with odd partial quotients is expressed via the Gauss-Kuz'min statistics for the classical continued fraction. This has made it possible to prove...
详细信息
The length of the continued-fraction expansion of a rational number with odd partial quotients is expressed via the Gauss-Kuz'min statistics for the classical continued fraction. This has made it possible to prove asymptotic formulas, similar to those already known for the classical euclidean algorithm, for the mean length of the euclidean algorithm with odd partial quotients.
Given two polynomials, this paper is devoted to describing the natural relation between the euclidean algorithm and the block LU factorization of the Hankel and Bezout matrices associated to such polynomials.
Given two polynomials, this paper is devoted to describing the natural relation between the euclidean algorithm and the block LU factorization of the Hankel and Bezout matrices associated to such polynomials.
A hardware algorithm for modular division is proposed. It is based on the extended euclidean algorithm (EEA). The procedure for finding the multiplicative inverse in EEA is modified so that it calculates the quotient....
详细信息
A hardware algorithm for modular division is proposed. It is based on the extended euclidean algorithm (EEA). The procedure for finding the multiplicative inverse in EEA is modified so that it calculates the quotient. Modular division is carried out through iteration of simple operations, such as shifts and additions. A redundant binary representation is employed so that additions are performed without carry propa- gation. An n-bit modular division is carried out in O(n) clock cycles. The length of each clock cycle is constant independent of n. A modular divider based on the algorithm has a bit-slice structure and is suitable for VLSI implementation.
The authors show how the euclidean algorithm fits into the behavioral framework of exact modeling and how it computes solutions of the scalar minimal partial realization problem. It turns out that the euclidean algori...
详细信息
The authors show how the euclidean algorithm fits into the behavioral framework of exact modeling and how it computes solutions of the scalar minimal partial realization problem. It turns out that the euclidean algorithm can be considered as a special instance of Wolovich's procedure (1974) to achieve row reducedness for a given polynomial 2 x 2 matrix. The authors show in detail how this approach yields a parameterization of all minimal solutions in terms of polynomials that are sequentially produced by the euclidean algorithm.
We introduce a generalization of the euclidean algorithm for rings equipped with an involution, and completely enumerate all isomorphism classes of orders over definite, rational quaternion algebras equipped with an o...
详细信息
We introduce a generalization of the euclidean algorithm for rings equipped with an involution, and completely enumerate all isomorphism classes of orders over definite, rational quaternion algebras equipped with an orthogonal involution that admit such an algorithm. We give two applications: first, any order that admits such an algorithm has class number 1;second, we show how the existence of such an algorithm relates to the problem of constructing explicit Dirichlet domains for Kleinian subgroups of the isometry group of hyperbolic 4-space. (C) 2020 Elsevier Inc. All rights reserved.
A new version of the euclidean algorithm is developed for computing the greatest common divisor of two Gaussian integers. It uses approximation to obtain a sequence of remainders of decreasing absolute values. The alg...
详细信息
A new version of the euclidean algorithm is developed for computing the greatest common divisor of two Gaussian integers. It uses approximation to obtain a sequence of remainders of decreasing absolute values. The algorithm is compared with the new (1+i)ary algorithm of Weilert and found to be somewhat faster if properly implemented. (C) 2002 Elsevier Science Ltd.
Let K be a number field with unit rank at least four, containing a subfield M such that K/M is Galois of degree at least four. We show that the ring of integers of K is a euclidean domain if and only if it is a princi...
详细信息
Let K be a number field with unit rank at least four, containing a subfield M such that K/M is Galois of degree at least four. We show that the ring of integers of K is a euclidean domain if and only if it is a principal ideal domain. This was previously known under the assumption of the generalized Riemann Hypothesis for Dedekind zeta functions. We prove this unconditionally.
As early as the 16th century. Simon Jacob, a German reckoning master, noticed that the worst case in computing the greatest common divisor of two numbers by the euclidean algorithm occurs if these numbers are equimult...
详细信息
As early as the 16th century. Simon Jacob, a German reckoning master, noticed that the worst case in computing the greatest common divisor of two numbers by the euclidean algorithm occurs if these numbers are equimultiples of two consecutive members of the Fibonacci sequence. (C) 1995 Academic Press, Inc.
暂无评论