A fast Bernoulli Number method for the HP Prime



#18

During HHC2013 I mentioned at the end of my presentation that the HP Prime had a wonderful collection of functions but lacked functions like the Bessel functions, Bernoulli numbers, and Bernoulli polynomial. I commented that calculating the latter two was not easy, and Cyril affirmed my observation.

Well I have been tinkering with calculating the Bernoulli numbers and Bernoulli polynomials. The Bernoulli numbers have the following features:

1. Aside from Bern(1), all Bernoulli numbers for odd values are zero.

2. The Bernoulli numbers for even values are not zero and alternate in signs.

3. Bernoulli numbers start as having small values that increase to very large values. I suspect that this variation in values causes stability problems in calculating Bernoulli numbers using certain algorithms.

Starting with the wealth of equations for the Bernoulli numbers in Wikipedia, I began trying various equations presented there (and I recommend you look at Wikipedia's web pages). After implementing various algorithms, observing the stability of their results, I found the following:

1. The recursive method were dead on in giving accurate results.

2. The series approximation method and the two matrix-based equations gave very good accuracy--not perfect but very good for the computation effort and code involved.

3. The rest of methods, like double summations, the Akiyama–Tanigawa method, and a variant of the Akiyama–Tanigawa method that I stumbled upon on the Internet, worked well for up to Bernoulli(10) and then gave bad results for higher numbers!!!

I implemented one of the matrix methods that give results that are close to the exact values. The code enjoys simplicity compared to implementing other algorithms (which I did in Excel VBA):

EXPORT BernMat(n)
BEGIN
LOCAL i, j, m, fact, mat;

// NOTE: Replace the character # with the proper
// not-equal character for the code to run correctly
IF n#1 AND (n MOD 2) == 1 THEN
RETURN 0;
END;
IF n== 1 THEN
RETURN -0.5;
END;
IF n==2 THEN
RETURN 1.0/6.0;
END;

m:=n+1;
// Create the n+1 by n+1 matrix
mat:=MAKEMAT(0,m,m);

// only non-zero value in column n+1
mat(1, m):=1;

// Calculate elements of the first matrix column
// Fact store the factorials of 2 to n+1
fact:=1;
FOR i from 1 TO m DO
fact:=fact*i;
mat(i, 1):=1/fact;
END;

// copy matrix elements to fill columns 2 to n
FOR j FROM 2 TO n DO
FOR i FROM j TO m DO
mat(i, j):=mat(i-1, j-1);
END;
END;

// divide Fact by m to obtain n!
RETURN fact / m * DET(mat);
END;

Calculating the coefficients of the Bernoulli polynomial is very simple once you have the Bernoulli numbers!!

Enjoy!!

Namir


Edited: 21 Nov 2013, 3:23 p.m. after one or more responses were posted


#19

Hi,
If all that you need is an approximation to B(n), have you considered using Euler's formula relating Zeta(2n) to B(2n)? The Prime has a Zeta and computes its values at the even integers rather fast. They come out as a rational number times a power of pi. I do not know what algorithm is used for this computation.


#20

It computes the Bernoulli number, the command bernoulli is available in Xcas but for some obscure reason it is not on Prime. The code uses the recurrence relation, it stores intermediate result in a list to avoid recursive calls:

gen bernoulli(const gen & x){
if ( (x.type!=_INT_) || (x.val<0))// Should add bernoulli polynomials
return gensizeerr(gettext("bernoulli"));
int n=x.val;
if (!n)
return plus_one;
if (n==1)
return minus_one_half;
if (n%2)
return zero;
gen a(plus_one);
gen b(rdiv(1-n,plus_two,context0));
vecteur bi(makevecteur(plus_one,minus_one_half));
int i=2;
for (; i< n-1; i+=2){
// compute bernoulli(i)
gen A=1;
gen B=gen(1-i)/2;
for (int j=2; j<i-1;j+=2){
A=iquo( A*gen(i+3-j)*gen(i+2-j),(j-1)*j);
B=B+A* bi[j];
}
bi.push_back(-B/gen(i+1));
bi.push_back(0);
a=iquo( (a*gen(n+3-i)*gen(n+2-i)),((i-1)*i));
b=b+a* bi[i];
}
return rdiv(-b,n+1,context0);
}


#21

Quote:
  gen bernoulli(const gen & x){
if ( (x.type!=_INT_) || (x.val<0))// Should add bernoulli polynomials
return gensizeerr(gettext("bernoulli"));
int n=x.val;
if (!n)
return plus_one;
if (n==1)
return minus_one_half;
if (n%2)
return zero;
gen a(plus_one);
gen b(rdiv(1-n,plus_two,context0));
vecteur bi(makevecteur(plus_one,minus_one_half));
int i=2;
for (; i< n-1; i+=2){
// compute bernoulli(i)
gen A=1;
gen B=gen(1-i)/2;
for (int j=2; j<i-1;j+=2){
A=iquo( A*gen(i+3-j)*gen(i+2-j),(j-1)*j);
B=B+A* bi[j];
}
bi.push_back(-B/gen(i+1));
bi.push_back(0);
a=iquo( (a*gen(n+3-i)*gen(n+2-i)),((i-1)*i));
b=b+a* bi[i];
}
return rdiv(-b,n+1,context0);
}

Added formatting to help make it more legible.

#22

If I understand correctly, Zeta(2n) is computed via Euler's identity Zeta(2n)= (+-)B(2n)*(2pi)^2n /2(2n!). How are other values of Zeta computed? Like Apery's Zeta(3). Thanks


#23

There are no known closed form expressions for odd values of the zeta function. Apery was able to prove that zeta(3) was irrational, and that's pretty much as far as people know about zeta(2n+1). According to the wikipedia page, infinite values of zeta(2n+1) are irrational, and at least one of zeta(5), zeta(7), zeta(9), zeta(11) is irrational. But no closed forms!

#24

That's also how I did it on the SandMath - see below.

n * Zeta (1-n) = - Bn

01	LBL "BN2" 
02 X=1?
03 GTO 01
04 X=0?
05 INCX
06 X=1?
07 RTN
08 ODD?
09 CLX
10 X=0?
11 RTN
12 2
13 X<Y?
14 GTO 00
15 6
16 1/X
17 RTN
18 LBL 00
19 ST+ X
20 X<Y?
21 GTO 00
22 -30
23 1/X
24 RTN
25 LBL 00
26 X<>Y
27 LBL 01
28 STO M
29 CHS
30 INCX
31 ZETA
32 RCL M
33 CHS
34 *
35 END

Edited: 21 Nov 2013, 11:48 a.m.


#25

Quote:
That's also how I did it on the SandMath - see below.

n * Zeta (1-n) = - Bn


Cool. So, on Prime, define this in CAS:

Bernoulli(x) := –x*Zeta(1–x)

Cranks out Bernoulli(200), all 224 digits over 7 digits, in about 3.7 seconds on the hardware.

Edit: The above gets the wrong answer for Bernoulli(0). Gotta add that as an exception. It should return 1.

Edit 2: Bernoulli(x) := IFTE(x=0,1,–x*Zeta(1–x))

Edited: 22 Nov 2013, 7:55 a.m.


#26

Great! This works also on my HP 50g with this Riemann's Zeta function implementation:

<< -199 Zeta 200 * NEG >> TEVAL     -->  -3.64707726448E215   (  0.47 s)

<< 200 IBERNOULLI -> NUM >> TEVAL --> -3.64707726452E215 (486.83 s)
The HP-28S version returns -3.64707724956E215 in a couple of seconds.

#27

Joe,

The availability of the Zeta function makes evaluating Bernoulli numbers and polynomials very trivial. The code I presented on this site calculates the Bernoulli numbers using simpler functions (well .. if you can call the matrix determinant simple ... :-)). My second listing uses more basic operations to calculate the Bernoulli numbers. I should be able to post a listing for the HP-41C soon (I am sure J-m Balliard has done that already)!! Even an HP-67 version is doable.

It seems that the HP Prime and the wp34s calculators share this advantage!!
Namir

#28

Alberto,

Check Wikipedia's Bernoulli Number web page and look for the expressions for Bn that use matrices.

Namir

#29

The 34S uses its implementation of the Zeta function to calculate the Bernoulli numbers.


- Pauli

#30

Here is the HP Prime program that calculates Bernoulli number using series approximation:

EXPORT BernSer(n,toler)
BEGIN
LOCAL sum,term,i,chs;

IF n==1 THEN
RETURN -0.5;
END;

IF n Mod 2 == 1 THEN
RETURN 0;
END;

sum:=1;
i:=2;
term:=2*toler;
WHILE term>toler DO
term:=1/i^n;
sum:=sum+term;
i:=i+1;
END;

IF n MOD 4 == 0 THEN
chs:=-1;
ELSE
chs=1;
END;
RETURN chs*(n!)/pi^n/2^(n-1)*sum;
END;

NOTE: I updated the listing tweak it.


Edited: 23 Nov 2013, 10:41 a.m. after one or more responses were posted


#31

Hi all,
Does anyone have a reference to how the HP's (prime, 50, 34s) compute Zeta(s)? Because, paraphrasing Namir, using zeta to compute B(n) is kind of a blind roundabout.

-a

[added] my bad. I just saw some of the code for zeta in the post by Gerson above. Thanks
[/added]

Edited: 22 Nov 2013, 11:20 a.m.


#32

Hi Alberto,

If you've followed the links you may have found another method, Borwein's algorithm as implemented by Thomas Ritschel in message #5 here:

http://www.hpmuseum.org/cgi-sys/cgiwrap/hpmuseum/archv021.cgi?read=235199

That one is better, but I chose the older method because it was easier to follow in the reference I had (message #20 in this thread). I've used fix parameters that grant accuracy in the real domain only. Arguments with absolute imaginary parts greater than 50 or so would require more terms. That was enough for my needs, but it's not a definitive zeta implementation for complex arguments yet.

Gerson.


Edited: 22 Nov 2013, 1:41 p.m.

#33

Hi Namir,

Thanks, nice, just tried it (I don't have a 41 thou). Is there a way to modify the code so as to output the actual number as a fraction?

-a

#34

And here is the HP-41C implementation for Bernoulli numbers using series approximation. It requires no modules or synthetic commands:

LBL "BERSER"
LBL A
CF 22
"TOLER?"
PROMPT
FS? 22
STO 01 # store new tolerance value if user entered it
"N?"
PROMPT
STO 00
1
X<>Y
X=Y? # n=1?
GTO 11
2
MOD
1
X=Y? # is n odd?
GTO 10
1
STO 03 # sum = 1
STO 02 # i = 1
LBL 01 # Start summation loop
1
STO+ 02 # i=i+1
RCL 02
RCL 00
Y^X
1/X # Calculate 1/i^n
STO+ 03 # sum = sum + 1/i^n
RCL 00
X<=Y? # toler <= term?
GTO 01 # resume to the next iteration
CF 00 # start calculating other factor
RCL 00
4
MOD
X=0?
SF 00
RCL 00
FACT # n!
PI
RCL 00
Y^X # pi^n
/
2
RCL 00
1
-
Y^X # 2^(n-1)
/
RCL 03
*
FS?C 00 # change sign?
CHS
RTN
LBL 10
0
RTN
LBL 11
-0.5
RTN

Enjoy!


Edited: 23 Nov 2013, 10:52 a.m.


Possibly Related Threads...
Thread Author Replies Views Last Post
  Complex Number Entry on Prime Jeff O. 19 885 11-16-2013, 12:34 PM
Last Post: Jeff O.
  [HP Prime] Calculating Prandtl Number with Units (bug found in USIMPLIFY) Timothy Roche 1 188 11-13-2013, 04:07 PM
Last Post: cyrille de Brébisson
  HP Prime: Converting number to Sci notation and back BruceTTT 1 191 11-12-2013, 02:11 AM
Last Post: Phil Wipf
  HP PRIME: Fixed 4 number format 0.001000 Joseph Ec 18 865 11-07-2013, 11:51 AM
Last Post: Geoff Quickfall
  HP Prime: Number of external Variables Davi Ribeiro de Oliveira 0 152 11-01-2013, 08:10 PM
Last Post: Davi Ribeiro de Oliveira
  Line number in Prime program listings Harold A Climer 3 285 10-27-2013, 03:37 PM
Last Post: Les Koller
  Prime Program number of set bits kris223 3 273 10-23-2013, 03:05 PM
Last Post: David Hayden
  WP-34S (Prime Number Test) question Barry Mead 3 256 10-20-2013, 05:28 PM
Last Post: Dieter
  Prime emulator number keys kris223 3 280 10-19-2013, 10:57 PM
Last Post: kris223
  A brand new calculator benchmark: "middle square method seed test" Pier Aiello 25 1,007 09-13-2013, 01:58 PM
Last Post: Pier Aiello

Forum Jump: