Поиcк по сайту by Google

Rambler's Top100
Образование Крыму » Информатика. Компьютеры » Algorithm and bound for the greatest common divisor of n integers - Bradley G. H.

Algorithm and bound for the greatest common divisor of n integers - Bradley G. H.

Название: Algorithm and bound for the greatest common divisor of n integers
Автор: Bradley G. H.
Категория: Информатика. Компьютеры
Тип: Книга
Дата: 22.02.2009 12:42:46
Скачано: 31
Описание: A new version of the Euclidean algorithm for finding the greatest common divisor of n integers a,- and multipliers x,- such that gcd = Щ a-\ -j- • • • + x„ an is presented. The number of arithmetic operations and the number of storage locations are linear in n. A theorem of Lame that gives a bound for the number of iterations of the Euclidean algorithm for two integers is extended to the case of n integers. An algorithm to construct a minimal set of multipliers is presented. A Fortran program for the algorithm appears as Comm. ACM Algorithm 386. KEY WORDS AND PHRASES: greatest common divisor, Euclidean algorithm, number theory, diophantine equations CR CATEGORIES: 3.15, 5.10 1. Introduction The greatest common divisor, gcd, of two positive integers can be determined by the Euclidean algorithm. < Euclid noted that the algorithm could be used to find the i gcd of n positive integers; this follows since gcd(ai, a2, «з) = gcd (gcd (at, a2), a3). If the steps of the algorithm are * traced back, it is possible to determine integers x,- such i that i с gcd(cti, • ■ ■ , a„) = xxai + • • • + xnan . (1) The Xi will be called "multipliers." Many applications require the multipliers, for instance, the Chinese problem of remainders [1], calculations on polynomial rings [1], solving linear diophantine equations [2], and computing , the Hermite or Smith normal form of an integer matrix [2]. Blankinship [1] has proposed a new version of the s Euclidean algorithm that eliminates the necessity of г backtracking to determine the multipliers. An (n) X (n) 1 matrix is carried along to keep track of the calculations. * Administrative Sciences Department. This research was supported in part by funds from the Yale Computer Center. This paper gives the theoretical background of Algorithm 386, Greatest Common Divisor of n Integers and Multipliers, by the ' same author, appearing on pages 447-448 of this issue . i
Файл: 154.1 КБ