up previous next
RatReconstructByContFrac, RatReconstructByLattice

rational reconstruction from modular image

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

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.

/**/  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]

See Also