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"
-On the other hand, "BELL2" is much faster than "BELL1" for large n
values.
Reference:
[1] "The Book of Numbers" by John H. Conway & Richard
K. Guy