iratrecon - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

iratrecon

rational reconstruction

 

Calling Sequence

Parameters

Description

Examples

References

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 2ND<m

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 2i2<m.  The condition 2ND<m implies a unique answer.

• 

The optional third argument maxquo specifies that Monagan's maximal quotient algorithm should be used.  This algorithm reconstructs nd with high probability when the modulus m is only a modest number of bits longer than 2nd, 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 2ilog2m3, which yields a probability of error that is approximately 1ilog2m2.  If 9n2d2<m then the algorithm always returns nd.

• 

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

m13

m13

(1)

u12modm

u7

(2)

iratreconu&comma;m

12

(3)

iratreconu&comma;m&comma;2&comma;2

12

(4)

u13modm

u9

(5)

iratreconu&comma;m

FAIL

(6)

iratreconu&comma;m&comma;maxquo

FAIL

(7)

iratreconu&comma;m&comma;maxquo&comma;1

13

(8)

U0&comma;1&comma;2&comma;3&comma;4&comma;5&comma;6&comma;7&comma;8&comma;9&comma;10&comma;11&comma;12

U0&comma;1&comma;2&comma;3&comma;4&comma;5&comma;6&comma;7&comma;8&comma;9&comma;10&comma;11&comma;12

(9)

mapiratrecon&comma;U&comma;m

0&comma;1&comma;2&comma;FAIL&comma;FAIL&comma;FAIL&comma;12&comma;12&comma;FAIL&comma;FAIL&comma;FAIL&comma;−2&comma;−1

(10)

mapiratrecon&comma;U&comma;m&comma;2&comma;3

0&comma;1&comma;2&comma;FAIL&comma;13&comma;23&comma;12&comma;12&comma;23&comma;13&comma;FAIL&comma;−2&comma;−1

(11)

mapiratrecon&comma;U&comma;m&comma;3&comma;2

0&comma;1&comma;2&comma;3&comma;FAIL&comma;32&comma;12&comma;12&comma;32&comma;FAIL&comma;−3&comma;−2&comma;−1

(12)

m19

m19

(13)

a1x223modm

a10x+12

(14)

iratrecona&comma;m

x223

(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.

m8997101103

m89809099

(16)

f1234567891&plus;1x987654321&plus;97531y8642

f1234567891+x987654321+97531y8642

(17)

forpin107&comma;109&comma;113&comma;127&comma;131&comma;139&comma;151dommp&semi;ufmodm&semi;printp&comma;iratreconu&comma;m&comma;iratreconu&comma;m&comma;maxquoend do&colon;

107,FAIL,FAIL

109,FAIL,FAIL

113,10765175739282276972x6358627+97531y8642,FAIL

127,FAIL,1234567891+x987654321+97531y8642

131,FAIL,1234567891+x987654321+97531y8642

139,1234567891+x987654321+97531y8642,1234567891+x987654321+97531y8642

151,1234567891+x987654321+97531y8642,1234567891+x987654321+97531y8642

(18)

As mentioned, N&comma;D not satisfying 2ND<m may be used, but a solution, if returned, is not necessarily unique.

iratrecon9&comma;13&comma;3&comma;3

13

(19)

iratrecon9&comma;13&comma;4&comma;4

−4

(20)

Note that the 13 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.

vVector1234541&comma;345782&comma;457123

v1234541345782457123

(21)

m4632746309

m2145357043

(22)

uvmodm

u57558389820145425472075589338

(23)

iratreconu&comma;m&comma;scaled

1234541345782457123

(24)

iratreconu&comma;m&comma;32000&comma;32000&comma;&apos;num&apos;&comma;&apos;den&apos;

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.

num

74070−10371914

(26)

den

246

(27)

numden

1234541345782457123

(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.

See Also

map

mod

ratrecon