iratrecon - Maple Programming Help

Home : Support : Online Help : Mathematics : Numbers : Integer Functions : iratrecon

iratrecon

rational reconstruction

 Calling Sequence iratrecon(u, m) iratrecon(u, m, scaled) iratrecon(u, m, N, D) iratrecon(u, m, maxquo, Q) iratrecon(u, m, N, D, num, den) iratrecon(u, m, maxquo, Q, num, den)

Parameters

 u - integer or polynomial with integer coefficients (or a list or Vector or Matrix of these) m - positive integer (the modulus) scaled - (optional) literal name, must be the last argument N, D - (optional) positive integer bounds satisfying $2\mathrm{ND} maxquo - literal name Q - (optional) positive integer bound num, den - (optional) names assigned the numerator and denominator

Description

 • If u is an integer, the iratrecon routine reconstructs a signed rational number from its image u modulo m.  The routine applies recursively to the coefficients of polynomials, and to the entries of lists, vectors, and matrices. It returns FAIL if reconstruction does not succeed.
 • The optional last argument scaled reconstructs all rationals over a common denominator.  This is faster and appropriate for modular algorithms.
 • There are two algorithms for recovering rational numbers.  Wang's algorithm (the default) uses bounds N and D on the numerator and denominator. If these are not specified, both bounds default to the largest integer $i$ satisfying $2{i}^{2}.  The condition $2\mathrm{ND} implies a unique answer.
 • The optional third argument maxquo specifies that Monagan's maximal quotient algorithm should be used.  This algorithm reconstructs $\frac{n}{d}$ with high probability when the modulus $m$ is only a modest number of bits longer than $2\left|n\right|d$, the minimum possible.  The algorithm returns the rational corresponding to the largest quotient in the Euclidean algorithm, provided that quotient is larger than a bound Q.  If Q is not specified it defaults to $2{\mathrm{ilog2}\left(m\right)}^{3}$, which yields a probability of error that is approximately $\frac{1}{{\mathrm{ilog2}\left(m\right)}^{2}}$.  If $9{n}^{2}{d}^{2} then the algorithm always returns $\frac{n}{d}$.
 • An optional six argument syntax specifies all bounds and iratrecon returns true or false to indicate whether reconstruction was successful. On success, the numerator and common denominator are assigned to the 5th and 6th arguments.  This syntax implies the scaled option and offers the best performance.

Examples

 > $m≔13$
 ${m}{≔}{13}$ (1)
 > $u≔\frac{1}{2}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}m$
 ${u}{≔}{7}$ (2)
 > $\mathrm{iratrecon}\left(u,m\right)$
 $\frac{{1}}{{2}}$ (3)
 > $\mathrm{iratrecon}\left(u,m,2,2\right)$
 $\frac{{1}}{{2}}$ (4)
 > $u≔\frac{1}{3}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}m$
 ${u}{≔}{9}$ (5)
 > $\mathrm{iratrecon}\left(u,m\right)$
 ${\mathrm{FAIL}}$ (6)
 > $\mathrm{iratrecon}\left(u,m,\mathrm{maxquo}\right)$
 ${\mathrm{FAIL}}$ (7)
 > $\mathrm{iratrecon}\left(u,m,\mathrm{maxquo},1\right)$
 $\frac{{1}}{{3}}$ (8)
 > $U≔\left[0,1,2,3,4,5,6,7,8,9,10,11,12\right]$
 ${U}{≔}\left[{0}{,}{1}{,}{2}{,}{3}{,}{4}{,}{5}{,}{6}{,}{7}{,}{8}{,}{9}{,}{10}{,}{11}{,}{12}\right]$ (9)
 > $\mathrm{map}\left(\mathrm{iratrecon},U,m\right)$
 $\left[{0}{,}{1}{,}{2}{,}{\mathrm{FAIL}}{,}{\mathrm{FAIL}}{,}{\mathrm{FAIL}}{,}{-}\frac{{1}}{{2}}{,}\frac{{1}}{{2}}{,}{\mathrm{FAIL}}{,}{\mathrm{FAIL}}{,}{\mathrm{FAIL}}{,}{-2}{,}{-1}\right]$ (10)
 > $\mathrm{map}\left(\mathrm{iratrecon},U,m,2,3\right)$
 $\left[{0}{,}{1}{,}{2}{,}{\mathrm{FAIL}}{,}{-}\frac{{1}}{{3}}{,}\frac{{2}}{{3}}{,}{-}\frac{{1}}{{2}}{,}\frac{{1}}{{2}}{,}{-}\frac{{2}}{{3}}{,}\frac{{1}}{{3}}{,}{\mathrm{FAIL}}{,}{-2}{,}{-1}\right]$ (11)
 > $\mathrm{map}\left(\mathrm{iratrecon},U,m,3,2\right)$
 $\left[{0}{,}{1}{,}{2}{,}{3}{,}{\mathrm{FAIL}}{,}{-}\frac{{3}}{{2}}{,}{-}\frac{{1}}{{2}}{,}\frac{{1}}{{2}}{,}\frac{{3}}{{2}}{,}{\mathrm{FAIL}}{,}{-3}{,}{-2}{,}{-1}\right]$ (12)
 > $m≔19$
 ${m}{≔}{19}$ (13)
 > $a≔\frac{1}{2}x-\frac{2}{3}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}m$
 ${a}{≔}{10}{}{x}{+}{12}$ (14)
 > $\mathrm{iratrecon}\left(a,m\right)$
 $\frac{{x}}{{2}}{-}\frac{{2}}{{3}}$ (15)

This example illustrates the improvement (fewer primes needed) of the maximal quotient rational reconstruction algorithm when the rationals being reconstructed when the size of the numerators and denominators are not uniform.  The first modulus used is 89*97*101*103*107 which is sufficiently large so that the three rationals appearing in the polynomial do arise in the Euclidean algorithm.

 > $m≔89\cdot 97\cdot 101\cdot 103$
 ${m}{≔}{89809099}$ (16)
 > $f≔1234567891+\frac{1}{987654321}x+\frac{97531}{8642}y$
 ${f}{≔}{1234567891}{+}\frac{{x}}{{987654321}}{+}\frac{{97531}{}{y}}{{8642}}$ (17)
 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}p\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{in}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\left[107,109,113,127,131,139,151\right]\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}m≔mp;\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}u≔f\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}m;\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathrm{print}\left(p,\mathrm{iratrecon}\left(u,m\right),\mathrm{iratrecon}\left(u,m,\mathrm{maxquo}\right)\right)\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}:$
 ${107}{,}{\mathrm{FAIL}}{,}{\mathrm{FAIL}}$
 ${109}{,}{\mathrm{FAIL}}{,}{\mathrm{FAIL}}$
 ${113}{,}{-}\frac{{107651}}{{7573928}}{-}\frac{{2276972}{}{x}}{{6358627}}{+}\frac{{97531}{}{y}}{{8642}}{,}{\mathrm{FAIL}}$
 ${127}{,}{\mathrm{FAIL}}{,}{1234567891}{+}\frac{{x}}{{987654321}}{+}\frac{{97531}{}{y}}{{8642}}$
 ${131}{,}{\mathrm{FAIL}}{,}{1234567891}{+}\frac{{x}}{{987654321}}{+}\frac{{97531}{}{y}}{{8642}}$
 ${139}{,}{1234567891}{+}\frac{{x}}{{987654321}}{+}\frac{{97531}{}{y}}{{8642}}{,}{1234567891}{+}\frac{{x}}{{987654321}}{+}\frac{{97531}{}{y}}{{8642}}$
 ${151}{,}{1234567891}{+}\frac{{x}}{{987654321}}{+}\frac{{97531}{}{y}}{{8642}}{,}{1234567891}{+}\frac{{x}}{{987654321}}{+}\frac{{97531}{}{y}}{{8642}}$ (18)

As mentioned, $N,D$ not satisfying $2\mathrm{ND} may be used, but a solution, if returned, is not necessarily unique.

 > $\mathrm{iratrecon}\left(9,13,3,3\right)$
 $\frac{{1}}{{3}}$ (19)
 > $\mathrm{iratrecon}\left(9,13,4,4\right)$
 ${-4}$ (20)

Note that the $\frac{1}{3}$ is also a viable solution for the second query, but $-4$ is returned instead. This final example is a vector of rationals using the scaled option.

 > $v≔\mathrm{Vector}\left(\left[\frac{12345}{41},-\frac{3457}{82},\frac{457}{123}\right]\right)$
 ${v}{≔}\left[\begin{array}{c}\frac{{12345}}{{41}}\\ {-}\frac{{3457}}{{82}}\\ \frac{{457}}{{123}}\end{array}\right]$ (21)
 > $m≔46327\cdot 46309$
 ${m}{≔}{2145357043}$ (22)
 > $u≔v\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}m$
 ${u}{≔}\left[\begin{array}{c}{575583898}\\ {2014542547}\\ {2075589338}\end{array}\right]$ (23)
 > $\mathrm{iratrecon}\left(u,m,\mathrm{scaled}\right)$
 $\left[\begin{array}{c}\frac{{12345}}{{41}}\\ {-}\frac{{3457}}{{82}}\\ \frac{{457}}{{123}}\end{array}\right]$ (24)
 > $\mathrm{iratrecon}\left(u,m,32000,32000,'\mathrm{num}','\mathrm{den}'\right)$
 ${\mathrm{true}}$ (25)

The common denominator can make it appear as though some numerators exceed the bound, but this is not so when rationals are reduced to lowest terms.

 > $\mathrm{num}$
 $\left[\begin{array}{c}{74070}\\ {-10371}\\ {914}\end{array}\right]$ (26)
 > $\mathrm{den}$
 ${246}$ (27)
 > $\frac{\mathrm{num}}{\mathrm{den}}$
 $\left[\begin{array}{c}\frac{{12345}}{{41}}\\ {-}\frac{{3457}}{{82}}\\ \frac{{457}}{{123}}\end{array}\right]$ (28)

References

 Monagan, M. B. "Maximal Quotient Rational Reconstruction: An Almost Optimal Algorithm for Rational Reconstruction." In Proceedings of ISSAC '04, pp. 243-249. Edited by Jaime Gutierrez. New York: ACM Press, 2004.
 Wang, P. S. "Early Detection of True Factors in Univariate Polynomial Factorization." In Proceedings of EUROCAL '83, pp. 225-235. Edited by J. A. van Hulzen. Springer-Verlag, 1983.