A fast Bernoulli Number method for the HP Prime « Next Oldest | Next Newest »

 ▼ Namir Posting Freak Posts: 2,247 Threads: 200 Joined: Jun 2005 11-21-2013, 09:48 AM 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 ▼ Alberto Candel Member Posts: 72 Threads: 16 Joined: Sep 2013 11-21-2013, 11:12 AM 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. ▼ parisse Junior Member Posts: 38 Threads: 0 Joined: Aug 2013 11-21-2013, 11:16 AM 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; jY 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. ▼ Joe Horn Member Posts: 153 Threads: 7 Joined: Jun 2008 11-22-2013, 07:12 AM 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. ▼ Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 11-22-2013, 08:29 AM 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. Namir Posting Freak Posts: 2,247 Threads: 200 Joined: Jun 2005 11-22-2013, 09:37 AM 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 Namir Posting Freak Posts: 2,247 Threads: 200 Joined: Jun 2005 11-21-2013, 03:32 PM Alberto, Check Wikipedia's Bernoulli Number web page and look for the expressions for Bn that use matrices. Namir Paul Dale Posting Freak Posts: 3,229 Threads: 42 Joined: Jul 2006 11-21-2013, 07:47 PM The 34S uses its implementation of the Zeta function to calculate the Bernoulli numbers. - Pauli Namir Posting Freak Posts: 2,247 Threads: 200 Joined: Jun 2005 11-21-2013, 08:32 PM 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 ▼ Alberto Candel Member Posts: 72 Threads: 16 Joined: Sep 2013 11-22-2013, 11:08 AM 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. ▼ Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 11-22-2013, 01:41 PM 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: 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. Alberto Candel Member Posts: 72 Threads: 16 Joined: Sep 2013 11-22-2013, 10:06 PM 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 Namir Posting Freak Posts: 2,247 Threads: 200 Joined: Jun 2005 11-22-2013, 04:46 PM 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 3,814 11-16-2013, 12:34 PM Last Post: Jeff O. [HP Prime] Calculating Prandtl Number with Units (bug found in USIMPLIFY) Timothy Roche 1 1,013 11-13-2013, 04:07 PM Last Post: cyrille de Brébisson HP Prime: Converting number to Sci notation and back BruceTTT 1 1,074 11-12-2013, 02:11 AM Last Post: Phil Wipf HP PRIME: Fixed 4 number format 0.001000 Joseph Ec 18 4,157 11-07-2013, 11:51 AM Last Post: Geoff Quickfall HP Prime: Number of external Variables Davi Ribeiro de Oliveira 0 749 11-01-2013, 08:10 PM Last Post: Davi Ribeiro de Oliveira Line number in Prime program listings Harold A Climer 3 1,439 10-27-2013, 03:37 PM Last Post: Les Koller Prime Program number of set bits kris223 3 1,507 10-23-2013, 03:05 PM Last Post: David Hayden WP-34S (Prime Number Test) question Barry Mead 3 1,353 10-20-2013, 05:28 PM Last Post: Dieter Prime emulator number keys kris223 3 1,389 10-19-2013, 10:57 PM Last Post: kris223 A brand new calculator benchmark: "middle square method seed test" Pier Aiello 25 5,429 09-13-2013, 01:58 PM Last Post: Pier Aiello

Forum Jump: 