1 /*
2 Copyright (C) 2021 Matthias Gessinger
3
4 This file is part of Arb.
5
6 Arb is free software: you can redistribute it and/or modify it under
7 the terms of the GNU Lesser General Public License (LGPL) as published
8 by the Free Software Foundation; either version 2.1 of the License, or
9 (at your option) any later version. See <http://www.gnu.org/licenses/>.
10 */
11
12 #include "acb_poly.h"
13
14 void
_acb_poly_graeffe_transform(acb_ptr b,acb_srcptr a,slong len,slong prec)15 _acb_poly_graeffe_transform(acb_ptr b, acb_srcptr a, slong len, slong prec)
16 {
17 slong lo, le, ls, deg, i;
18 acb_ptr pe, po;
19
20 if (len <= 1)
21 {
22 if (len)
23 acb_sqr(b, a, prec);
24 return;
25 }
26
27 deg = len - 1;
28 lo = len / 2;
29 ls = 2 * lo - 1;
30 le = deg / 2 + 1;
31 po = _acb_vec_init(lo);
32 pe = _acb_vec_init(FLINT_MAX(le, ls));
33
34 for (i = deg; i >= 0; i--)
35 {
36 if (i % 2 == 0)
37 acb_set(pe + i / 2, a + i);
38 else
39 acb_set(po + i / 2, a + i);
40 }
41
42 _acb_poly_mul(b, pe, le, pe, le, prec);
43 _acb_poly_mul(pe, po, lo, po, lo, prec);
44 _acb_poly_sub(b + 1, b + 1, ls, pe, ls, prec);
45
46 if (len % 2 == 0)
47 {
48 _acb_vec_neg(b, b, deg);
49 acb_set(b + deg, pe + (deg - 1));
50 }
51
52 _acb_vec_clear(pe, FLINT_MAX(le, ls));
53 _acb_vec_clear(po, lo);
54 }
55
56 void
acb_poly_graeffe_transform(acb_poly_t b,const acb_poly_t a,slong prec)57 acb_poly_graeffe_transform(acb_poly_t b, const acb_poly_t a, slong prec)
58 {
59 acb_poly_fit_length(b, a->length);
60 _acb_poly_graeffe_transform(b->coeffs, a->coeffs, a->length, prec);
61 _acb_poly_set_length(b, a->length);
62 }
63