up previous next
 RatReconstructByContFrac, RatReconstructByLattice

rational reconstruction from modular image

 Syntax
 ```RatReconstructByContFrac(X: INT, M: INT): RECORD RatReconstructByContFrac(X: INT, M: INT, threshold: INT): RECORD RatReconstructByLattice(X: INT, M: INT): RECORD RatReconstructByLattice(X: INT, M: INT, threshold: INT): RECORD```

 Description
These functions attempt to reconstruct rational numbers from a modular image X mod M .

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

The result is a record: the boolean field failed is true if no convincing result was found; otherwise it is false , and a second field, called ReconstructedRat , contains the value reconstructed.

An optional third argument, threshold , 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. See JSC paper by John Abbott, "Fault-tolerant modular reconstruction of rational numbers", http://www.sciencedirect.com/science/article/pii/S0747717116300773 .

NOTE: so that the heuristic can work, the modulus must be a bit larger than strictly necessary; indeed, reconstruction always fails if M is 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] ```