up previous next
 RatReconstructByContFrac

rational reconstruction from modular image

 Syntax
 ```RatReconstructByContFrac(X: INT, M: INT): RECORD RatReconstructByContFrac(X: INT, M: INT, LogToler: INT): RECORD```

 Description
These functions attempt to reconstruct rational numbers from a modular image X mod M . The result is a record: the boolean field failed is true if no convincing result was found; otherwise that field is false , and a second field, called ReconstructedRat , contains the value reconstructed.

The algorithms are fault-tolerant: they will succeed provided that X is correct modulo a sufficiently large factor of M .

An optional third argument determines what convincing means: a higher value gives a more reliable answer, but may need a larger modulus before the answer is found.

There are two different underlying heuristic algorithms: a faster one based on continued fractions, and a slower one based on 2-dimensional lattice reduction ( RatReconstructByLattice ). See the JSC paper by John Abbott: "Fault-tolerant modular reconstruction of rational numbers", http://www.sciencedirect.com/science/article/pii/S0747717116300773 ; a near-final version is at http://arxiv.org/abs/1303.2965 .

NOTE: so that the heuristic can work, the modulus must be a bit larger than strictly necessary; indeed, reconstruction will always fail if M is too small.

 Example
 ```/**/ X := 3333333333; /**/ M := 10^10; /**/ RatReconstructByContFrac(X,M); record[ReconstructedRat := -1/3, failed := false] /**/ X := 3141592654; /**/ M := 10^10; /**/ RatReconstructByContFrac(X,M); record[failed := true] ```