ginac/polynomial/eval_point_finder.h

   1 #ifndef GINAC_PGCD_EVAL_POINT_FINDER_H
   2 #define GINAC_PGCD_EVAL_POINT_FINDER_H
   3 #include "operators.h"
   4 #include <set>
   5
   6 namespace GiNaC
   7 {
   8
   9 /// Find a `good' evaluation point b \in Z_p for a pair of multivariate
  10 /// polynomials A, B \in Z_p[x_n][x_0, \ldots, x_n]. Here `good' means
  11 /// that b is not a root of GCD of contents of A and B. N.B. content
  12 /// is univariate polynomial \in Z_p[x_n]
  13 struct eval_point_finder
  14 {
  15         typedef long value_type;
  16         const value_type p;
  17         std::set<value_type> points;
  18         const random_modint modint_generator;
  19         bool operator()(value_type& b, const ex& g, const ex& x);
  20         eval_point_finder(const value_type& p_) : p(p_), modint_generator(p)
  21         { }
  22 };
  23
  24 bool eval_point_finder::operator()(value_type& b, const ex& lc, const ex& x)
  25 {
  26         random_modint modint_generator(p);
  27         // Search for a new element of field
  28         while (points.size() < p - 1) {
  29                 value_type b_ = modint_generator();
  30                 // check if this evaluation point was already used
  31                 if (points.find(b_) != points.end())
  32                         continue;
  33
  34                 // mark found value as used, even if it's a root of lc
  35                 // (so we don't need to do the check once more)
  36                 points.insert(b_);
  37                 // Now make sure it's NOT the root of GCD's leading coeffient
  38                 if (lc.subs(x == numeric(b_)).smod(numeric(p)).is_zero())
  39                         continue;
  40                 // Nice, it's our next evaluation point
  41                 b = b_;
  42                 return true;
  43         }
  44         // All possible evaluation points were used.
  45         return false;
  46 }
  47
  48 }
  49
  50 #endif /* GINAC_PGCD_EVAL_POINT_FINDER_H */
  51