up previous next

rational reconstruction from modular image

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

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.

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