1 /*
2 Copyright (C) 2009, 2011 William Hart
3
4 This file is part of FLINT.
5
6 FLINT 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 "gmp.h"
13 #include "flint.h"
14 #include "fft.h"
15
fft_adjust(mp_limb_t * r,mp_limb_t * i1,mp_size_t i,mp_size_t limbs,flint_bitcnt_t w)16 void fft_adjust(mp_limb_t * r, mp_limb_t * i1, mp_size_t i, mp_size_t limbs, flint_bitcnt_t w)
17 {
18 flint_bitcnt_t b1;
19 mp_limb_t cy;
20 mp_size_t x;
21
22 b1 = i*w;
23 x = b1/FLINT_BITS;
24 b1 = b1%FLINT_BITS;
25
26 if (x)
27 {
28 flint_mpn_copyi(r + x, i1, limbs - x);
29 r[limbs] = 0;
30 cy = mpn_neg_n(r, i1 + limbs - x, x);
31 mpn_addmod_2expp1_1(r + x, limbs - x, -i1[limbs]);
32 mpn_sub_1(r + x, r + x, limbs - x + 1, cy);
33 mpn_mul_2expmod_2expp1(r, r, limbs, b1);
34 } else
35 mpn_mul_2expmod_2expp1(r, i1, limbs, b1);
36 }
37