Moenck R. T.  Fast computation of GCDs using Schoenhage
Скачать

Название: 
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 КБ 
Скачать

