up previous next
RatReconstructWithBounds

deterministic rational reconstruction from modular image

Syntax 
RatReconstructWithBounds(e: INT, P: INT, Q: INT, res: LIST of INT, mod: LIST of INT): RECORD

Description
This function attempts to reconstruct a rational number from a collection of residue-modulus pairs (res[i],mod[i]) . The function also requires the input of three bounds: e is an upper bound on the number of bad moduli, and P and Q are upper bounds for (respectively the numerator and denominator of) the rational to be reconstructed.

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

Example 
/**/  moduli := [11,13,15,17,19];
/**/  residues := [-2, -5, 0, 7, 4];
/**/  RatReconstructWithBounds(1,10,10,residues,moduli);
record[ReconstructedRat := 1/5, failed := false]

/**/  RatReconstructWithBounds(0,10,10,residues,moduli);
record[failed := true]

See Also