1 /*
2 Copyright (C) 2010 Sebastian Pancratz
3 Copyright (C) 2010, 2020 William Hart
4
5 This file is part of FLINT.
6
7 FLINT is free software: you can redistribute it and/or modify it under
8 the terms of the GNU Lesser General Public License (LGPL) as published
9 by the Free Software Foundation; either version 2.1 of the License, or
10 (at your option) any later version. See <http://www.gnu.org/licenses/>.
11 */
12
13 #ifdef T
14
15 #include "templates.h"
16
17 void
_TEMPLATE(T,poly_pow_trunc_binexp)18 _TEMPLATE(T, poly_pow_trunc_binexp) (TEMPLATE(T, struct) * res,
19 const TEMPLATE(T, struct) * poly, ulong e,
20 slong trunc, const TEMPLATE(T, ctx_t) ctx)
21 {
22 ulong bit = ~((~UWORD(0)) >> 1);
23 TEMPLATE(T, struct) * v = _TEMPLATE(T, vec_init) (trunc, ctx);
24 TEMPLATE(T, struct) * R, * S, * T;
25
26 /*
27 Set bits to the bitmask with a 1 one place `lower than the msb of e
28 */
29
30 while ((bit & e) == UWORD(0))
31 bit >>= 1;
32
33 bit >>= 1;
34
35 /*
36 Trial run without any polynomial arithmetic to determine the parity
37 of the number of swaps; then set R and S accordingly
38 */
39
40 {
41 unsigned int swaps = 0U;
42 ulong bit2 = bit;
43 if ((bit2 & e))
44 swaps = ~swaps;
45 while (bit2 >>= 1)
46 if ((bit2 & e) == UWORD(0))
47 swaps = ~swaps;
48
49 if (swaps == 0U)
50 {
51 R = res;
52 S = v;
53 }
54 else
55 {
56 R = v;
57 S = res;
58 }
59 }
60
61 /*
62 We unroll the first step of the loop, referring to {poly, len}
63 */
64
65 _TEMPLATE(T, poly_mullow) (R, poly, trunc, poly, trunc, trunc, ctx);
66 if ((bit & e))
67 {
68 _TEMPLATE(T, poly_mullow) (S, R, trunc, poly, trunc, trunc, ctx);
69 T = R;
70 R = S;
71 S = T;
72 }
73
74 while ((bit >>= 1))
75 {
76 if ((bit & e))
77 {
78 _TEMPLATE(T, poly_mullow) (S, R, trunc, R, trunc, trunc, ctx);
79 _TEMPLATE(T, poly_mullow) (R, S, trunc, poly, trunc, trunc, ctx);
80 }
81 else
82 {
83 _TEMPLATE(T, poly_mullow) (S, R, trunc, R, trunc, trunc, ctx);
84 T = R;
85 R = S;
86 S = T;
87 }
88 }
89
90 _TEMPLATE(T, vec_clear) (v, trunc, ctx);
91 }
92
93 void
TEMPLATE(T,poly_pow_trunc_binexp)94 TEMPLATE(T, poly_pow_trunc_binexp) (TEMPLATE(T, poly_t) res,
95 const TEMPLATE(T, poly_t) poly, ulong e,
96 slong trunc, const TEMPLATE(T, ctx_t) ctx)
97 {
98 const slong len = poly->length;
99 TEMPLATE(T, struct) * p;
100 int pcopy = 0;
101
102 if (len < 2 || e < UWORD(3) || trunc == 0)
103 {
104 if (len == 0 || trunc == 0)
105 TEMPLATE(T, poly_zero) (res, ctx);
106 else if (len == 1)
107 {
108 TEMPLATE(T, poly_fit_length) (res, 1, ctx);
109 TEMPLATE(T, pow_ui) (res->coeffs + 0, poly->coeffs + 0, e, ctx);
110 _TEMPLATE(T, poly_set_length) (res, 1, ctx);
111 _TEMPLATE(T, poly_normalise) (res, ctx);
112 }
113 else if (e == UWORD(0))
114 {
115 TEMPLATE(T, t) c;
116 TEMPLATE(T, init) (c, ctx);
117 TEMPLATE(T, set_ui) (c, 1, ctx);
118 TEMPLATE(T, poly_set_coeff) (res, 0, c, ctx);
119 _TEMPLATE(T, poly_set_length) (res, 1, ctx);
120 _TEMPLATE(T, poly_normalise) (res, ctx);
121 TEMPLATE(T, clear) (c, ctx);
122 }
123 else if (e == UWORD(1))
124 {
125 TEMPLATE(T, poly_set) (res, poly, ctx);
126 TEMPLATE(T, poly_truncate) (res, trunc, ctx);
127 }
128 else /* e == UWORD(2) */
129 TEMPLATE(T, poly_mullow) (res, poly, poly, trunc, ctx);
130
131 return;
132 }
133
134 if (poly->length < trunc)
135 {
136 p = _TEMPLATE(T, vec_init) (trunc, ctx);
137 _TEMPLATE(T, vec_set) (p, poly->coeffs, poly->length, ctx);
138 _TEMPLATE(T, vec_zero) (p + poly->length, trunc - poly->length, ctx);
139 pcopy = 1;
140 } else
141 p = poly->coeffs;
142
143 if (res != poly || pcopy)
144 {
145 TEMPLATE(T, poly_fit_length) (res, trunc, ctx);
146 _TEMPLATE(T, poly_pow_trunc_binexp) (res->coeffs, p, e, trunc, ctx);
147 }
148 else
149 {
150 TEMPLATE(T, poly_t) t;
151 TEMPLATE(T, poly_init2) (t, trunc, ctx);
152 _TEMPLATE(T, poly_pow_trunc_binexp) (t->coeffs, p, e, trunc, ctx);
153 TEMPLATE(T, poly_swap) (res, t, ctx);
154 TEMPLATE(T, poly_clear) (t, ctx);
155 }
156
157 if (pcopy)
158 _TEMPLATE(T, vec_clear) (p, trunc, ctx);
159
160 res->length = trunc;
161 _TEMPLATE(T, poly_normalise) (res, ctx);
162 }
163
164 #endif
165