up previous next
|
RatReconstructByContFrac --
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]
|