1 /*
2 Copyright (C) 2011 Fredrik Johansson
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 "arith.h"
13
14 void
arith_bell_number_nmod_vec_recursive(mp_ptr b,slong n,nmod_t mod)15 arith_bell_number_nmod_vec_recursive(mp_ptr b, slong n, nmod_t mod)
16 {
17 slong i, k;
18 mp_ptr t;
19
20 if (n < BELL_NUMBER_TAB_SIZE)
21 {
22 for (i = 0; i < n; i++)
23 b[i] = n_mod2_preinv(bell_number_tab[i], mod.n, mod.ninv);
24 return;
25 }
26
27 n -= 1;
28 t = _nmod_vec_init(n);
29
30 t[0] = b[0] = b[1] = 1;
31
32 for (i = 1; i < n; i++)
33 {
34 t[i] = t[0];
35 for (k = i; k > 0; k--)
36 t[k - 1] = n_addmod(t[k - 1], t[k], mod.n);
37
38 b[i + 1] = t[0];
39 }
40
41 _nmod_vec_clear(t);
42 }
43