𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Efficient Rational Number Reconstruction

✍ Scribed by George E. Collins; Mark J. Encarnación

Book ID
102603437
Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
384 KB
Volume
20
Category
Article
ISSN
0747-7171

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

On an Efficient Algorithm for Big Ration
On an Efficient Algorithm for Big Rational Number Computations by Parallel p-adics
✍ Carla Limongelli 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 451 KB

This paper presents an algorithm for evaluating an arithmetic expression over "big" rational numbers. The method exploits \(p\)-adic arithmetic and parallelism to achieve efficiency. Roughly, the algorithm begins by mapping the input rational numbers to the related p-adic codes for several prime ba

Which rational numbers are binding numbe
Which rational numbers are binding numbers?
✍ V. G. Kane; S. P. Mohanty; E. G. Straus 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 246 KB

## Abstract The concept of the binding number of a graph was introduced by Woodall in 1973. in this paper we characterize the set __F~n~__ of all pairs (__a, b__) of integers such that there is a graph __G__ with __n__ vertices and binding number __a/b__ that has a realizing set of __b__ vertices.

From Ratio to Rational Number
From Ratio to Rational Number
✍ James King Bidwell 📂 Article 📅 1966 🏛 School Science and Mathematics Association 🌐 English ⚖ 264 KB