64d1e9394aa386f3ad8e2ed2faba4c8c7bc06a1f
[ginac.git] / 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-2011 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