FORM 4.3
polygcd.h
1#pragma once
2/* #[ License : */
3/*
4 * Copyright (C) 1984-2022 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#include <map>
31
32class poly; // polynomial class
33class gcd_heuristic_failed {}; // class for throwing exceptions
34
35// whether or not to use the heuristic before Zippel's algorithm
36#define POLYGCD_USE_HEURISTIC
37
38// maximum number of words in a coefficient for gcd_heuristic to continue
39const int POLYGCD_HEURISTIC_MAX_DIGITS = 1000;
40
41// maximum number of retries after the heuristic has failed
42const int POLYGCD_HEURISTIC_MAX_TRIES = 10;
43
44// a fudge factor, which improves efficiency
45const int POLYGCD_HEURISTIC_MAX_ADD_RANDOM = 10;
46
47// maximum cached power in substitute_last and sparse_interpolation_get_mul_list
48const int POLYGCD_RAISPOWMOD_CACHE_SIZE = 1000;
49
50namespace polygcd {
51
52 // functions to call the gcd routines
53 const poly integer_gcd (const poly &a, const poly &b);
54 const poly integer_content (const poly &a);
55
56 const poly gcd (const poly &a, const poly &b);
57 const poly content_univar (const poly &a, int x);
58 const poly content_multivar (const poly &a, int x);
59
60 const std::vector<WORD> coefficient_list_gcd (const std::vector<WORD> &a, const std::vector<WORD> &b, WORD p);
61
62 // internal functions
63 const poly gcd_heuristic (const poly &a, const poly &b, const std::vector<int> &x, int max_tries=POLYGCD_HEURISTIC_MAX_TRIES);
64 const poly gcd_Euclidean (const poly &a, const poly &b);
65 const poly gcd_modular (const poly &a, const poly &b, const std::vector<int> &x);
66 const poly gcd_modular_dense_interpolation (const poly &a, const poly &b, const std::vector<int> &x, const poly &s);
67 const poly gcd_modular_sparse_interpolation (const poly &a, const poly &b, const std::vector<int> &x, const poly &s);
68
69 const std::vector<int> sparse_interpolation_get_mul_list (const poly &a, const std::vector<int> &x, const std::vector<int> &c);
70 void sparse_interpolation_mul_poly (poly &a, const std::vector<int> &m);
71 const poly sparse_interpolation_reduce_poly (const poly &a, const std::vector<int> &x);
72 const poly sparse_interpolation_fix_poly (const poly &a, int x);
73
74 const poly chinese_remainder (const poly &a1, const poly &m1, const poly &a2, const poly &m2);
75 const poly substitute(const poly &a, int x, int c);
76 const std::map<std::vector<int>,poly> full_bracket(const poly &a, const std::vector<int>& filter);
77 const poly bracket(const poly &a, const std::vector<int>& pattern, const std::vector<int>& filter);
78 const std::map<std::vector<int>,int> bracket_count(const poly &a, const std::vector<int>& filter);
79 const poly gcd_linear (const poly &a, const poly &b);
80}
Definition poly.h:49