Efficient rational number reconstruction

被引：19

作者：

Collins, GE

Encarnacion, MJ

机构：

[1] Research Institute for Symbolic Computation, Johannes Kepler University

[2] Department of Computer Science, University of the Philippines

来源：

JOURNAL OF SYMBOLIC COMPUTATION | 1995年 / 20卷 / 03期

关键词：

D O I：

10.1006/jsco.1995.1051

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

An efficient algorithm is presented for reconstructing a rational number from its residue module a given integer. The algorithm is based on a double-digit version of Lehmer's multiprecision extended Euclidean algorithm. While asymptotic complexity remains quadratic in the length of the input, experiments with an implementation show that for small inputs the new algorithm is more than 3 times faster than the algorithm in common use, and is more than 7 times faster for inputs that are 100 words long.

引用

页码：287 / 297

页数：11

共 19 条

[1]

[Anonymous], P INT S SYMB ALG COM

[2]

COLLINS GE, 1980, LECTURE NOTES ARITHM

[3]

COLLINS GE, 1993, 9319 RISC J KEPL U

[4]

COLLINS GE, 1995, 9519 RISC J KEPL U

[5]

ENCARNACION MJ, 1994, P 1994 INT S SYMB AL, P58

[6]

Jebelean T., 1993, Proceedings of the 1993 International Symposium on Symbolic and Algebraic Computation. ISSAC '93, P111, DOI 10.1145/164081.164102

[7]

JEBELEAN T, 1993, LECTURE NOTES COMPUT, V722, P45

[8] COMPUTING GREATEST COMMON DIVISORS AND FACTORIZATIONS IN QUADRATIC NUMBER-FIELDS [J].

KALTOFEN, E ;

ROLLETSCHEK, H .

MATHEMATICS OF COMPUTATION, 1989, 53 (188) :697-720

[9]

KNUTH DE, 1981, SEMINUMERICAL ALGORI, V2

[10]

Lehmer D. H., 1938, AM MATH MON, V45, P227

← 1 2 →