The Museum of HP Calculators

Bell Numbers for the HP-41

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) = C_n-1⁰ B(0) + C_n-1¹ B(1) + ........ + C_n-1^n-1 B(n-1) if n > 1
where C_n^k = 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 10⁴⁶ is obtained in 8mn32s.
-Execution time is approximately proportional to n²

2°) A Series Expansion

-Bell numbers may also be computed by the series: B(n) = e^-1 ( 1ⁿ/1! + 2ⁿ/2! + ...... + kⁿ/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 10⁹⁹ ( 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

Go back to the HP-41 software library
Go back to the general software library
Go back to the main exhibit hall