bernoulli.c revision 1.1.1.1
1/* bernoulli -- internal function to compute Bernoulli numbers. 2 3Copyright 2005, 2006, 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc. 4Contributed by the Arenaire and Cacao projects, INRIA. 5 6This file is part of the GNU MPFR Library. 7 8The GNU MPFR Library is free software; you can redistribute it and/or modify 9it under the terms of the GNU Lesser General Public License as published by 10the Free Software Foundation; either version 3 of the License, or (at your 11option) any later version. 12 13The GNU MPFR Library is distributed in the hope that it will be useful, but 14WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 15or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 16License for more details. 17 18You should have received a copy of the GNU Lesser General Public License 19along with the GNU MPFR Library; see the file COPYING.LESSER. If not, see 20http://www.gnu.org/licenses/ or write to the Free Software Foundation, Inc., 2151 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA. */ 22 23#include "mpfr-impl.h" 24 25/* assuming b[0]...b[2(n-1)] are computed, computes and stores B[2n]*(2n+1)! 26 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) 31 which gives: 32 B[n] = -sum(binomial(n+1,k)*B[k], k=0..n-1)/(n+1). 33 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. 37*/ 38mpz_t* 39mpfr_bernoulli_internal (mpz_t *b, unsigned long n) 40{ 41 if (n == 0) 42 { 43 b = (mpz_t *) (*__gmp_allocate_func) (sizeof (mpz_t)); 44 mpz_init_set_ui (b[0], 1); 45 } 46 else 47 { 48 mpz_t t; 49 unsigned long k; 50 51 b = (mpz_t *) (*__gmp_reallocate_func) 52 (b, n * sizeof (mpz_t), (n + 1) * sizeof (mpz_t)); 53 mpz_init (b[n]); 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); 58 mpz_mul_ui (t, t, n); 59 mpz_fdiv_q_ui (t, t, 3); /* exact: t=binomial(2*n+1,2*k)*(2*n)!/(2*k+1)! 60 for k=n-1 */ 61 mpz_mul (b[n], t, b[n-1]); 62 for (k = n - 1; k-- > 0;) 63 { 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]); 71 } 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); 76 mpz_neg (b[n], b[n]); 77 mpz_clear (t); 78 } 79 return b; 80} 81