Efficient Rational Number Reconstruction
β
George E. Collins; Mark J. EncarnaciΓ³n
π
Article
π
1995
π
Elsevier Science
π
English
β 384 KB
An efficient algorithm is presented for reconstructing a rational number from its residue modulo 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, experi