Bradley G. H.  Algorithm and bound for the greatest common divisor of n integers
Скачать

Название: 
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 447448 of this issue . i 
Файл: 
154.1 КБ 
Скачать

