/src/gmp-6.2.1/mpn/toom_eval_pm1.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* mpn_toom_eval_pm1 -- Evaluate a polynomial in +1 and -1 |
2 | | |
3 | | Contributed to the GNU project by Niels Möller |
4 | | |
5 | | THE FUNCTION IN THIS FILE IS INTERNAL WITH A MUTABLE INTERFACE. IT IS ONLY |
6 | | SAFE TO REACH IT THROUGH DOCUMENTED INTERFACES. IN FACT, IT IS ALMOST |
7 | | GUARANTEED THAT IT WILL CHANGE OR DISAPPEAR IN A FUTURE GNU MP RELEASE. |
8 | | |
9 | | Copyright 2009 Free Software Foundation, Inc. |
10 | | |
11 | | This file is part of the GNU MP Library. |
12 | | |
13 | | The GNU MP Library is free software; you can redistribute it and/or modify |
14 | | it under the terms of either: |
15 | | |
16 | | * the GNU Lesser General Public License as published by the Free |
17 | | Software Foundation; either version 3 of the License, or (at your |
18 | | option) any later version. |
19 | | |
20 | | or |
21 | | |
22 | | * the GNU General Public License as published by the Free Software |
23 | | Foundation; either version 2 of the License, or (at your option) any |
24 | | later version. |
25 | | |
26 | | or both in parallel, as here. |
27 | | |
28 | | The GNU MP Library is distributed in the hope that it will be useful, but |
29 | | WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY |
30 | | or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
31 | | for more details. |
32 | | |
33 | | You should have received copies of the GNU General Public License and the |
34 | | GNU Lesser General Public License along with the GNU MP Library. If not, |
35 | | see https://www.gnu.org/licenses/. */ |
36 | | |
37 | | |
38 | | #include "gmp-impl.h" |
39 | | |
40 | | /* Evaluates a polynomial of degree k > 3, in the points +1 and -1. */ |
41 | | int |
42 | | mpn_toom_eval_pm1 (mp_ptr xp1, mp_ptr xm1, unsigned k, |
43 | | mp_srcptr xp, mp_size_t n, mp_size_t hn, mp_ptr tp) |
44 | 0 | { |
45 | 0 | unsigned i; |
46 | 0 | int neg; |
47 | |
|
48 | 0 | ASSERT (k >= 4); |
49 | | |
50 | 0 | ASSERT (hn > 0); |
51 | 0 | ASSERT (hn <= n); |
52 | | |
53 | | /* The degree k is also the number of full-size coefficients, so |
54 | | * that last coefficient, of size hn, starts at xp + k*n. */ |
55 | | |
56 | 0 | xp1[n] = mpn_add_n (xp1, xp, xp + 2*n, n); |
57 | 0 | for (i = 4; i < k; i += 2) |
58 | 0 | ASSERT_NOCARRY (mpn_add (xp1, xp1, n+1, xp+i*n, n)); |
59 | | |
60 | 0 | tp[n] = mpn_add_n (tp, xp + n, xp + 3*n, n); |
61 | 0 | for (i = 5; i < k; i += 2) |
62 | 0 | ASSERT_NOCARRY (mpn_add (tp, tp, n+1, xp+i*n, n)); |
63 | | |
64 | 0 | if (k & 1) |
65 | 0 | ASSERT_NOCARRY (mpn_add (tp, tp, n+1, xp+k*n, hn)); |
66 | 0 | else |
67 | 0 | ASSERT_NOCARRY (mpn_add (xp1, xp1, n+1, xp+k*n, hn)); |
68 | | |
69 | 0 | neg = (mpn_cmp (xp1, tp, n + 1) < 0) ? ~0 : 0; |
70 | |
|
71 | | #if HAVE_NATIVE_mpn_add_n_sub_n |
72 | | if (neg) |
73 | | mpn_add_n_sub_n (xp1, xm1, tp, xp1, n + 1); |
74 | | else |
75 | | mpn_add_n_sub_n (xp1, xm1, xp1, tp, n + 1); |
76 | | #else |
77 | 0 | if (neg) |
78 | 0 | mpn_sub_n (xm1, tp, xp1, n + 1); |
79 | 0 | else |
80 | 0 | mpn_sub_n (xm1, xp1, tp, n + 1); |
81 | |
|
82 | 0 | mpn_add_n (xp1, xp1, tp, n + 1); |
83 | 0 | #endif |
84 | |
|
85 | 0 | ASSERT (xp1[n] <= k); |
86 | 0 | ASSERT (xm1[n] <= k/2 + 1); |
87 | | |
88 | 0 | return neg; |
89 | 0 | } |