00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013 #include <numerix/integer.hpp>
00014
00015 namespace mmx {
00016
00017
00018
00019
00020
00021 bool
00022 reconstruct (integer& n, integer& d,
00023 const integer& u, const integer& m,
00024 const integer& N, const integer& D) {
00025
00026
00027
00028 ASSERT (u >= 0, "invalid input");
00029 ASSERT (m > u, "invalid input");
00030 ASSERT (N > 0, "invalid input");
00031 ASSERT (D > 0, "invalid input");
00032 ASSERT (2 * N * D < m, "invalid input");
00033 integer r0= m, t0= 0;
00034 integer r1= u, t1= 1;
00035 integer q;
00036 while (r1 > N) {
00037 integer aux= rem (r0, r1, q);
00038 r0= r1; r1= aux;
00039 aux= t0;
00040 t0= t1; t1= aux - q * t1;
00041 }
00042 n= r1; d= t1;
00043 if (d < 0) { n= -n; d= -d; }
00044 if (d > D) return false;
00045 return abs (gcd (n, d)) == 1; }
00046
00047 bool
00048 reconstruct (integer& n, integer& d,
00049 const integer& u, const integer& m) {
00050 ASSERT (u >= 0, "invalid input");
00051 ASSERT (m > u, "invalid input");
00052 integer N= floor_sqrt (m >> 1);
00053 return reconstruct (n, d, u, m, N, N); }
00054
00055 }