src/integer.cpp

Go to the documentation of this file.

/******************************************************************************
* MODULE     : integer.cpp
* DESCRIPTION: Routines for integer numbers
* COPYRIGHT  : (C) 2012  Gregoire Lecerf
*******************************************************************************
* This software falls under the GNU general public license and comes WITHOUT
* ANY WARRANTY WHATSOEVER. See the file $TEXMACS_PATH/LICENSE for more details.
* If you don't have this file, write to the Free Software Foundation, Inc.,
* 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
******************************************************************************/

#include <numerix/integer.hpp>

namespace mmx {

/*****************************************************************************
* Rational reconstruction
*****************************************************************************/

bool
reconstruct (integer& n, integer& d,
             const integer& u, const integer& m,
             const integer& N, const integer& D) {
  /* Return in r = n / d such that abs (n) <= N, 0 < d <= D, gcd (n, d) = 1,
     and n / d = u mod m. If such a rational exists then the function returns
     true and false otherwise. */
  ASSERT (u >= 0, "invalid input");
  ASSERT (m > u, "invalid input");
  ASSERT (N > 0, "invalid input");
  ASSERT (D > 0, "invalid input");
  ASSERT (2 * N * D < m, "invalid input");
  integer r0= m, t0= 0;
  integer r1= u, t1= 1;
  integer q;
  while (r1 > N) {
    integer aux= rem (r0, r1, q);
    r0= r1; r1= aux;
    aux= t0;
    t0= t1; t1= aux - q * t1;
  }
  n= r1; d= t1;
  if (d < 0) { n= -n; d= -d; }
  if (d > D) return false;
  return abs (gcd (n, d)) == 1; }

bool
reconstruct (integer& n, integer& d,
             const integer& u, const integer& m) {
  ASSERT (u >= 0, "invalid input");
  ASSERT (m > u, "invalid input");
  integer N= floor_sqrt (m >> 1);
  return reconstruct (n, d, u, m, N, N); }

} // namespace mmx

---