1 /* bernoulli -- internal function to compute Bernoulli numbers.
3 Copyright 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013 Free Software Foundation, Inc.
4 Contributed by the AriC and Caramel projects, INRIA.
6 This file is part of the GNU MPFR Library.
8 The GNU MPFR Library is free software; you can redistribute it and/or modify
9 it under the terms of the GNU Lesser General Public License as published by
10 the Free Software Foundation; either version 3 of the License, or (at your
11 option) any later version.
13 The GNU MPFR Library is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
16 License for more details.
18 You should have received a copy of the GNU Lesser General Public License
19 along with the GNU MPFR Library; see the file COPYING.LESSER. If not, see
20 http://www.gnu.org/licenses/ or write to the Free Software Foundation, Inc.,
21 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA. */
23 #include "mpfr-impl.h"
25 /* assuming b[0]...b[2(n-1)] are computed, computes and stores B[2n]*(2n+1)!
27 t/(exp(t)-1) = sum(B[j]*t^j/j!, j=0..infinity)
28 thus t = (exp(t)-1) * sum(B[j]*t^j/j!, n=0..infinity).
29 Taking the coefficient of degree n+1 > 1, we get:
30 0 = sum(1/(n+1-k)!*B[k]/k!, k=0..n)
32 B[n] = -sum(binomial(n+1,k)*B[k], k=0..n-1)/(n+1).
34 Let C[n] = B[n]*(n+1)!.
35 Then C[n] = -sum(binomial(n+1,k)*C[k]*n!/(k+1)!, k=0..n-1),
36 which proves that the C[n] are integers.
39 mpfr_bernoulli_internal (mpz_t
*b
, unsigned long n
)
43 b
= (mpz_t
*) (*__gmp_allocate_func
) (sizeof (mpz_t
));
44 mpz_init_set_ui (b
[0], 1);
51 b
= (mpz_t
*) (*__gmp_reallocate_func
)
52 (b
, n
* sizeof (mpz_t
), (n
+ 1) * sizeof (mpz_t
));
54 /* b[n] = -sum(binomial(2n+1,2k)*C[k]*(2n)!/(2k+1)!, k=0..n-1) */
55 mpz_init_set_ui (t
, 2 * n
+ 1);
56 mpz_mul_ui (t
, t
, 2 * n
- 1);
57 mpz_mul_ui (t
, t
, 2 * n
);
59 mpz_fdiv_q_ui (t
, t
, 3); /* exact: t=binomial(2*n+1,2*k)*(2*n)!/(2*k+1)!
61 mpz_mul (b
[n
], t
, b
[n
-1]);
62 for (k
= n
- 1; k
-- > 0;)
64 mpz_mul_ui (t
, t
, 2 * k
+ 1);
65 mpz_mul_ui (t
, t
, 2 * k
+ 2);
66 mpz_mul_ui (t
, t
, 2 * k
+ 2);
67 mpz_mul_ui (t
, t
, 2 * k
+ 3);
68 mpz_fdiv_q_ui (t
, t
, 2 * (n
- k
) + 1);
69 mpz_fdiv_q_ui (t
, t
, 2 * (n
- k
));
70 mpz_addmul (b
[n
], t
, b
[k
]);
72 /* take into account C[1] */
73 mpz_mul_ui (t
, t
, 2 * n
+ 1);
74 mpz_fdiv_q_2exp (t
, t
, 1);
75 mpz_sub (b
[n
], b
[n
], t
);