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

Rambler's Top100
Электронные книги » Информатика. Компьютеры » Fast computation of GCDs using Schoenhage - Moenck R. T.

Fast computation of GCDs using Schoenhage - Moenck R. T.

Название: Fast computation of GCDs using Schoenhage
Автор: Moenck R. T.
Категория: Информатика. Компьютеры
Тип: Книга
Дата: 23.02.2009 10:42:08
Скачано: 36
Описание: An integer greatest common divisor (GCD) algorithm due to Schonhage is generalized to hold in all euclidean domains which possess a fast multiplication algorithm. It is shown that if two N precision elements can be multiplied in 0(N loga N), then their GCD can be com- a+1 puted in 0(N log N). As a consequence, a new faster algorithm for multivariate polynomial GCD's can be derived and with that new bounds for rational function manipulation. INTRODUCTION The problem of computing greatest common divisors has recently received considerable attention. There are several reasons for this: 1) The polynomial GCD routine is one of the most critical in any symbolic mathematical system. 2) The GCD process is intimately connected with many fields of mathematics, including continued fractions, diophantine equations, bigradients, sturm sequences and elimination theory. 3) GCD's are interesting by themselves from an algorithms viewpoint. The multivariate polynomial problem was originally thought to be exponential. But work by Collins [6] and Brown [4] has shown it to be polynomial. Fast integer GCD's were first considered by Knuth [2] and improved by Schonhage [1] to give a 2 0(N log N log log N) algorithm. This paper generalizes the work of Schonhage to euclidean domains with a fast multiplication algorithm- Consequences of this extension in the context of multivariate polynomial GCD's and rational function manipulations are explored. I The Extended Euclidean Algorithm For a euclidean domain D, Euclid's algorithm computes the GCD of two elements А,В by computing the remainder sequence (RS) of A and B,
Файл: 123.9 КБ