Efficient Rational Number Reconstruction

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, 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.