iratrecon - Maple Programming Help

iratrecon

rational reconstruction

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

Parameters

 u - integer or polynomial with integer coefficients (or list or Vector or Matrix of these) m - positive integer (the modulus) N, D - (optional) positive integers satisfying $2N\mathrm{D} maxquo - literal name Q - (optional) positive integer scaled - (optional) literal name

Description

 • If u is an integer, the iratrecon routine reconstructs a signed rational number from its image u modulo m.
 • In the first calling sequence, both N (the maximum magnitude of the numerator) and D (the maximum magnitude of the denominator) are chosen to be the largest integer $i$ satisfying $2{i}^{2}.
 The iratrecon command then returns, if it exists, the unique rational number $\frac{n}{d}$ satisfying $\mathrm{gcd}\left(n,d\right)=1$, $\mathrm{gcd}\left(d,m\right)=1$, $\frac{n}{d}=u\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}m$, $|n|<=N$ and $0<=d<=\mathrm{D}$. Otherwise, iratrecon returns FAIL.
 If the rational $\frac{n}{d}$ we are trying to reconstruct satisfies $|n|<=N$ and $d\le \mathrm{D}$ and the modulus m satisfies $\mathrm{gcd}\left(d,m\right)=1$ then this algorithm with the default choice for N and D will output $\frac{n}{d}$ for all moduli $2{\mathrm{max}\left(N,\mathrm{D}\right)}^{2}.
 • The second calling sequence allows specification of N and D. Note that to obtain a unique answer, N and D must satisfy $2N\mathrm{D}, though it is still possible to obtain a (possibly not unique) solution in some cases when $m\le 2N\mathrm{D}$.
 • In the third calling sequence, if the integer Q is specified, iratrecon(u,m,'maxquo',Q) returns, if it exists, a rational number $\frac{n}{d}$ satisfying $\mathrm{gcd}\left(n,d\right)=1=\mathrm{gcd}\left(d,m\right)$, $\frac{n}{d}=u\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}m$ such that the quotient $q$ in the Euclidean algorithm corresponding to the rational $\frac{n}{d}$ is maximal and $Q. Otherwise, iratrecon returns FAIL. If the integer Q is not specified, it defaults to $2{\mathrm{ilog2}\left(m\right)}^{3}$.
 If the rational number we are trying to reconstruct is $\frac{n}{d}$ then one can prove that this algorithm will output $\frac{n}{d}$ for all moduli $m>\left(9{n}^{2}{d}^{2}\right)$.  However, it will output $\frac{n}{d}$ with high probability for moduli a modest number of bits longer than $2|n|d$, the minimum possible.  The default setting of Q means that if iratrecon outputs a rational then the probability that it is wrong is approximately $\frac{1}{{\mathrm{ilog2}\left(m\right)}^{2}}$.
 • To use this routine to reconstruct a rational $r=\frac{n}{d}$ from u satisfying $r=u\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}m$, the modulus m used must be chosen to be relatively prime to d. Otherwise, the reconstruction will never succeed.
 • If the input image u is a polynomial in any number of variables with integer coefficients, iratrecon is applied to the integer coefficients of the polynomial.  If reconstruction fails on a coefficient of a monomial $t$, the implementation remembers this monomial so that next time iratrecon is called on a problem with the same support it will start with the coefficient of the monomial $t$. This means that if iratrecon is being used to reconstruct the rational coefficients of a polynomial using a modular algorithm where the modulus $m$ is increasing, efficiency is not lost on problems with different size of rational coefficients.
 • If the input image u is a list or vector or matrix of (polynomials of) integers, iratrecon is applied to the entries of the list (or vector or matrix).
 • If the optional argument scaled is specified, and the input is not a single integer (it is a list or vector or matrix of (polynomials of) integers), if rational reconstruction succeeds in reconstructing the first rational, $\frac{n}{d}$ say, then it first multiplies the remaining images in $u$ to be reconstructed by $d$ modulo $m$.  This speeds up the reconstruction of the remaining images a lot if the denominators of the remaining rationals are small multiples of $d$ (or vice versa) as is often the case. This option should always be used.

Examples

 > $m≔13$
 ${m}{≔}{13}$ (1)
 > $u≔\frac{1}{2}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.5em}{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.5em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.5em}{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{1x}{2}-\frac{2}{3}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}m$
 ${a}{≔}{10}{}{x}{+}{12}$ (14)
 > $\mathrm{iratrecon}\left(a,m\right)$
 $\frac{{1}}{{2}}{}{x}{-}\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{1x}{987654321}+\frac{97531y}{8642}$
 ${f}{≔}{1234567891}{+}\frac{{1}}{{987654321}}{}{x}{+}\frac{{97531}}{{8642}}{}{y}$ (17)
 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}p\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{in}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\left[107,109,113,127,131,139,151\right]\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}m≔mp;\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}u≔f\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}m;\phantom{\rule[-0.0ex]{0.5em}{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.5em}{0.0ex}}\mathbf{end do}:$
 ${107}{,}{\mathrm{FAIL}}{,}{\mathrm{FAIL}}$
 ${109}{,}{\mathrm{FAIL}}{,}{\mathrm{FAIL}}$
 ${113}{,}{-}\frac{{107651}}{{7573928}}{+}\frac{{97531}}{{8642}}{}{y}{-}\frac{{2276972}}{{6358627}}{}{x}{,}{\mathrm{FAIL}}$
 ${127}{,}{\mathrm{FAIL}}{,}{1234567891}{+}\frac{{1}}{{987654321}}{}{x}{+}\frac{{97531}}{{8642}}{}{y}$
 ${131}{,}{\mathrm{FAIL}}{,}{1234567891}{+}\frac{{1}}{{987654321}}{}{x}{+}\frac{{97531}}{{8642}}{}{y}$
 ${139}{,}{1234567891}{+}\frac{{1}}{{987654321}}{}{x}{+}\frac{{97531}}{{8642}}{}{y}{,}{1234567891}{+}\frac{{1}}{{987654321}}{}{x}{+}\frac{{97531}}{{8642}}{}{y}$
 ${151}{,}{1234567891}{+}\frac{{1}}{{987654321}}{}{x}{+}\frac{{97531}}{{8642}}{}{y}{,}{1234567891}{+}\frac{{1}}{{987654321}}{}{x}{+}\frac{{97531}}{{8642}}{}{y}$ (18)

As mentioned, $N$,$\mathrm{D}$ not satisfying $2N\mathrm{D} 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.5em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}m$
 ${u}{≔}\left[\begin{array}{r}{575583898}\\ {2014542547}\\ {2075589338}\end{array}\right]$ (23)
 > $\mathrm{iratrecon}\left(u,m,\mathrm{scaled}\right)$
 $\left[\begin{array}{c}\frac{{157}}{{173784}}\\ {-}\frac{{3457}}{{82}}\\ \frac{{457}}{{123}}\end{array}\right]$ (24)

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.