ginac/polynomial/eval_point_finder.h

   1 /** @file eval_point_finder.h
   2  *
   3  *  Functions for finding an evaluation point. */
   4
   5 /*
   6  *  GiNaC Copyright (C) 1999-2009 Johannes Gutenberg University Mainz, Germany
   7  *
   8  *  This program is free software; you can redistribute it and/or modify
   9  *  it under the terms of the GNU General Public License as published by
  10  *  the Free Software Foundation; either version 2 of the License, or
  11  *  (at your option) any later version.
  12  *
  13  *  This program is distributed in the hope that it will be useful,
  14  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  *  GNU General Public License for more details.
  17  *
  18  *  You should have received a copy of the GNU General Public License
  19  *  along with this program; if not, write to the Free Software
  20  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  21  */
  22
  23 #ifndef GINAC_PGCD_EVAL_POINT_FINDER_H
  24 #define GINAC_PGCD_EVAL_POINT_FINDER_H
  25
  26 #include "operators.h"
  27
  28 #include <set>
  29
  30 namespace GiNaC {
  31
  32 /// Find a `good' evaluation point b \in Z_p for a pair of multivariate
  33 /// polynomials A, B \in Z_p[x_n][x_0, \ldots, x_n]. Here `good' means
  34 /// that b is not a root of GCD of contents of A and B. N.B. content
  35 /// is univariate polynomial \in Z_p[x_n]
  36 struct eval_point_finder
  37 {
  38         typedef long value_type;
  39         const value_type p;
  40         std::set<value_type> points;
  41         const random_modint modint_generator;
  42         bool operator()(value_type& b, const ex& g, const ex& x);
  43         eval_point_finder(const value_type& p_) : p(p_), modint_generator(p)
  44         { }
  45 };
  46
  47 bool eval_point_finder::operator()(value_type& b, const ex& lc, const ex& x)
  48 {
  49         random_modint modint_generator(p);
  50         // Search for a new element of field
  51         while (points.size() < p - 1) {
  52                 value_type b_ = modint_generator();
  53                 // check if this evaluation point was already used
  54                 if (points.find(b_) != points.end())
  55                         continue;
  56
  57                 // mark found value as used, even if it's a root of lc
  58                 // (so we don't need to do the check once more)
  59                 points.insert(b_);
  60                 // Now make sure it's NOT the root of GCD's leading coeffient
  61                 if (lc.subs(x == numeric(b_)).smod(numeric(p)).is_zero())
  62                         continue;
  63                 // Nice, it's our next evaluation point
  64                 b = b_;
  65                 return true;
  66         }
  67         // All possible evaluation points were used.
  68         return false;
  69 }
  70
  71 } // namespace GiNaC
  72
  73 #endif // ndef GINAC_PGCD_EVAL_POINT_FINDER_H