Acceleration of Euclidean Algorithm and Rational Number Reconstruction
Acceleration of Euclidean Algorithm and Rational Number Reconstruction
复制标题
欧氏算法的加速与有理数重构
DOI：
10.1137/s0097539702408636
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
V. Pan
中科院分区：
文献类型：
--
作者：
Xinmao Wang;V. Pan
我们加速了已知的算法，用于计算整数的扩展欧几里得算法的一个选择条目，因此，用于模和数值有理数重构问题。加速度从二次时间到近线性时间，与已知的整数gcd的复杂度界相匹配，我们的算法将其作为特殊情况计算。
We accelerate the known algorithms for computing a selected entry of the extended Euclidean algorithm for integers and, consequently, for the modular and numerical rational number reconstruction problems. The acceleration is from quadratic to nearly linear time, matching the known complexity bound for the integer gcd, which our algorithm computes as a special case.