The Museum of HP Calculators

Bell Numbers for the HP-41

This program is Copyright © 2004 by Jean-Marc Baillard and is used here by permission.

This program is supplied without representation or warranty of any kind. Jean-Marc Baillard and The Museum of HP Calculators therefore assume no responsibility and shall have no liability, consequential or otherwise, of any kind arising from the use of this program material or any part thereof.

Overview

-Two programs are listed hereafter:
-"BELL1" uses a recurrence formula and calculates and stores   B(0) , B(1) , ...... , B(n)   in registers   R00 , R01 , ...... , Rnn
whereas "BELL2" uses a series expansion and yields B(n) only , but without any data register.

1°) A Recurrence Relation

-Bell numbers are defined by    B(0) = 1  and  B(n) = Cn-10 B(0) + Cn-11 B(1) + ........ + Cn-1n-1 B(n-1)     if  n > 1
where Cnk = n!/(k!(n-k)!) are the binomial coefficients.

Data Registers:             R00 = B(0) ; R01 = B(1) ; ....... ; Rnn = B(n)
Flags: /
Subroutines: /

-Synthetic registers M , N , O are used by this program and may be replaced by any unused data registers.

01  LBL "BELL1"
02  STO O
03  SIGN
04  STO 00
05  STO 01
06  STO N
07  LBL 01
08  RCL 00
09  STO M
10  ST+ N
11  LBL 02
12  RCL IND Y
13  RCL M
14  *
15  +
16  RCL N
17  R^
18  ST* M
19  -
20  ST/ M
21  RDN
22  DSE Y
23  GTO 02
24  STO IND N
25  RCL O
26  RCL N
27  X<Y?
28  GTO 01
29  X<>Y
30  SIGN
31  RCL IND L
32  CLA
33  END

( 59 bytes / SIZE nnn+1 ; but at least 003 )

 STACK INPUTS OUTPUTS X n B(n) L / n

Example:     Calculate  B(10)

10  XEQ "BELL1"  >>>  B(10) = 115975   ( in 20 seconds )   We also have the following results in registers R00 thru R10:

 n 0 1 2 3 4 5 6 7 8 9 10 B(n) 1 1 2 5 15 52 203 877 4140 21147 115975

-If  n > 89 there is an "OUT OF RANGE"
-B(49) = 1.072613714 1046  is obtained in 8mn32s.
-Execution time is approximately proportional to n2

2°) A Series Expansion

-Bell numbers may also be computed by the series:  B(n) = e-1 ( 1n/1! + 2n/2! + ...... + kn/k! + ..... )

Data Registers: /
Flags: /
Subroutines: /

-Synthetic registers M & N are used by this program and may be replaced by any data registers.

01  LBL "BELL2"
02  STO N
03  2
04  STO M
05  SIGN
06  CHS
07  E^X
08  STO L
09  LBL 01
10  LASTX
11  RCL M
12  1/X
13  *
14  1
15  ST+ M
16  LASTX
17  -
18  RCL N
19  Y^X
20  /
21  +
22  X#Y?
23  GTO 01
24  RCL N
25  SIGN
26  X<Y?
27  X<>Y
28  CLA
29  END

( 47 bytes / SIZE 000 )

 STACK INPUTS OUTPUTS X n B(n) L / n

Example:     Evaluate  B(89)

89  XEQ "BELL2"  >>>  B(89) = 5.225728472 1099  ( in 44 seconds )    ( the last 3 digits should be 505 instead of 472 )

-Roundoff errors are often greater than with "BELL1"
-"BELL2" is much faster than "BELL1" for large n values.

Reference:     "The Book of Numbers"  by John H. Conway  & Richard K. Guy