请输入您要查询的字词:

 

单词 FastEuclideanAlgorithm
释义

fast Euclidean algorithm


Given two polynomials of degree n with coefficients from a field K, the straightforward Eucliean AlgorithmMathworldPlanetmath uses O(n2) field operationsMathworldPlanetmath to compute their greatest common divisorMathworldPlanetmathPlanetmath. The Fast Euclidean Algorithm computes the same GCD in O(𝖬(n)log(n)) field operations, where 𝖬(n) is the time to multiply two n-degree polynomials; with FFT multiplicationPlanetmathPlanetmath the GCD can thus be computed in time O(nlog2(n)log(log(n))). The algorithm can also be used to compute any particular pair of coefficients from the Extended Euclidean AlgorithmMathworldPlanetmath, although computing every pair of coefficients would involve O(n2) outputs and so the efficiency is not as helpful when all are needed.

The algorithm can be made to work over but it is very tricky. A newer version that is easier to understand was published by Damien Stehlé and Paul Zimmerman, “A Binary Recursive Gcd Algorithm.”

Here we sketch the algorithm over K[x]. The basic idea is that the quotients qi computed by the Euclidean Algorithm can usually be computed by looking at only the first few coefficients of the polynomial; for example, if

A(x)=anxn+an-1xn-1++a0,B(x)=bn-1xn-1++b0

then

quo(A(x),B(x))=anbn-1x+bn-1an-1-anbn-2bn-12

With more detailed analysis, we can show that in fact a divide-and-conquer approach can be used to calculate the GCD. First, we remove the terms whose degree is n/2 or less from both polynomials A and B. Then, we recursively compute their GCD and Euclidean coefficients. We then apply the Euclidean coefficients to A and B, and recursively completePlanetmathPlanetmathPlanetmathPlanetmath the Euclidean Algorithm.

The full algorithm, and a comprehensive runtime analysis is given in “Modern Computer Algebra” by von zur Gathen and Gerhard.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/5 1:28:10