FORM  4.1
polygcd.h
1 #pragma once
2 /* #[ License : */
3 /*
4  * Copyright (C) 1984-2013 J.A.M. Vermaseren
5  * When using this file you are requested to refer to the publication
6  * J.A.M.Vermaseren "New features of FORM" math-ph/0010025
7  * This is considered a matter of courtesy as the development was paid
8  * for by FOM the Dutch physics granting agency and we would like to
9  * be able to track its scientific use to convince FOM of its value
10  * for the community.
11  *
12  * This file is part of FORM.
13  *
14  * FORM is free software: you can redistribute it and/or modify it under the
15  * terms of the GNU General Public License as published by the Free Software
16  * Foundation, either version 3 of the License, or (at your option) any later
17  * version.
18  *
19  * FORM is distributed in the hope that it will be useful, but WITHOUT ANY
20  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
21  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
22  * details.
23  *
24  * You should have received a copy of the GNU General Public License along
25  * with FORM. If not, see <http://www.gnu.org/licenses/>.
26  */
27 /* #] License : */
28 
29 #include <vector>
30 
31 class poly; // polynomial class
32 class gcd_heuristic_failed {}; // class for throwing exceptions
33 
34 // whether or not to use the heuristic before Zippel's algorithm
35 #define POLYGCD_USE_HEURISTIC
36 
37 // maximum number of words in a coefficient for gcd_heuristic to continue
38 const int POLYGCD_HEURISTIC_MAX_DIGITS = 1000;
39 
40 // maximum number of retries after the heuristic has failed
41 const int POLYGCD_HEURISTIC_MAX_TRIES = 10;
42 
43 // a fudge factor, which improves efficiency
44 const int POLYGCD_HEURISTIC_MAX_ADD_RANDOM = 10;
45 
46 // maximum cached power in substitute_last and sparse_interpolation_get_mul_list
47 const int POLYGCD_RAISPOWMOD_CACHE_SIZE = 1000;
48 
49 namespace polygcd {
50 
51  // functions to call the gcd routines
52  const poly integer_gcd (const poly &a, const poly &b);
53  const poly integer_content (const poly &a);
54 
55  const poly gcd (const poly &a, const poly &b);
56  const poly content_univar (const poly &a, int x);
57  const poly content_multivar (const poly &a, int x);
58 
59  const std::vector<WORD> coefficient_list_gcd (const std::vector<WORD> &a, const std::vector<WORD> &b, WORD p);
60 
61  // internal functions
62  const poly gcd_heuristic (const poly &a, const poly &b, const std::vector<int> &x, int max_tries=POLYGCD_HEURISTIC_MAX_TRIES);
63  const poly gcd_Euclidean (const poly &a, const poly &b);
64  const poly gcd_modular (const poly &a, const poly &b, const std::vector<int> &x);
65  const poly gcd_modular_dense_interpolation (const poly &a, const poly &b, const std::vector<int> &x, const poly &lc, const poly &s);
66  const poly gcd_modular_sparse_interpolation (const poly &a, const poly &b, const std::vector<int> &x, const poly &lc, const poly &s);
67 
68  const std::vector<int> sparse_interpolation_get_mul_list (const poly &a, const std::vector<int> &x, const std::vector<int> &c);
69  void sparse_interpolation_mul_poly (poly &a, const std::vector<int> &m);
70  const poly sparse_interpolation_reduce_poly (const poly &a, const std::vector<int> &x);
71  const poly sparse_interpolation_fix_poly (const poly &a, int x);
72 
73  const poly chinese_remainder (const poly &a1, const poly &m1, const poly &a2, const poly &m2);
74  const poly substitute_last(const poly &a, int x, int c);
75 }
Definition: poly.h:49