99 lines
4.2 KiB
Text
99 lines
4.2 KiB
Text
[Calculation of Catalan numbers.
|
|
EDSAC program, Initial Orders 2.]
|
|
|
|
[Define where to store the list of Catalan numbers.]
|
|
T 54 K [store address in location 54, so that values
|
|
are accessed by code letter C (for Catalan)]
|
|
P 200 F [<------ address here]
|
|
|
|
[Modification of library subroutine P7.
|
|
Prints signed integer up to 10 digits, right-justified.
|
|
54 storage locations; working position 4D.
|
|
Must be loaded at an even address.
|
|
Input: Number is at 0D.]
|
|
T 56 K
|
|
GKA3FT42@A47@T31@ADE10@T31@A48@T31@SDTDH44#@NDYFLDT4DS43@TF
|
|
H17@S17@A43@G23@UFS43@T1FV4DAFG50@SFLDUFXFOFFFSFL4FT4DA49@T31@
|
|
A1FA43@G20@XFP1024FP610D@524D!FO46@O26@XFO46@SFL8FT4DE39@
|
|
|
|
[Main routine]
|
|
T 120 K [load at 120]
|
|
G K [set @ (theta) to load address]
|
|
[Variables]
|
|
[0] P F [index of Catalan number]
|
|
[Constants]
|
|
[1] P 7 D [maximum index required]
|
|
[2] P D [single-word 1]
|
|
[3] P 2 F [to change addresses by 2]
|
|
[4] H #C [these 3 are used to manufacture EDSAC orders]
|
|
[5] T #C
|
|
[6] V #C
|
|
[7] K 4096 F [(1) add to change T order into H order
|
|
(2) teleprinter null]
|
|
[8] # F [figures shift]
|
|
[9] ! F [space]
|
|
[10] @ F [carriage return]
|
|
[11] & F [line feed]
|
|
|
|
[Enter with acc = 0]
|
|
[12] O 8 @ [set teleprinter to figures]
|
|
T 4 D [clear 5F and sandwich bit]
|
|
A 2 @ [load single-word 1]
|
|
T 4 F [store as double word at 4D; clear acc]
|
|
[Here with index in acc, Catalan number in 4D]
|
|
[16] U @ [store index]
|
|
L 1 F [times 4 by shifting]
|
|
A 5 @ [make T order to store Catalan number]
|
|
U 27 @ [plant in code]
|
|
A 7 @ [make H order with same address]
|
|
U 45 @ [plant in code]
|
|
S 47 @ [make A order with same address]
|
|
T 34 @ [plant in code]
|
|
A 6 @ [load V order for start of list]
|
|
T 46 @ [plant in code]
|
|
A 4 D [Catalan number from temp store]
|
|
[27] T #C [store in list (manufactured order)]
|
|
T D [clear 1F and sandwich bit]
|
|
A @ [load single-word index]
|
|
T F [store as double word at 0D]
|
|
[31] A 31 @ [for return from print subroutine]
|
|
G 56 F [print index]
|
|
O 9 @ [followed by space]
|
|
[34] A #C [load Catalan number (manufactured order)]
|
|
T D [to 0D for printing]
|
|
[36] A 36 @ [for return from print subroutine]
|
|
G 56 F [print Catalan number]
|
|
O 10 @ [followed by new line]
|
|
O 11 @
|
|
T 4 D [clear partial sum]
|
|
A @ [load index]
|
|
S 1 @ [reached the maximum?]
|
|
E 64 @ [if so, jump to exit]
|
|
[Inner loop to compute sum of products C{i}*C(n-1}]
|
|
[44] T F [clear acc]
|
|
[45] H #C [C{n-i} to mult reg (manufactured order)]
|
|
[46] V #C [acc := C{i}*C{n-i} (manufactiured order)]
|
|
[Multiply product by 2^34 (see preamble). The 'L F' order is
|
|
also exploited above to convert an H order into an A order.]
|
|
[47] L F [shift acc left by 13 (the maximum available)]
|
|
L F [shift 13 more]
|
|
L 64 F [shift 8 more, total 34]
|
|
A 4 D [add partial sum]
|
|
T 4 D [update partial sum]
|
|
A 46 @ [inc i in V order]
|
|
A 3 @
|
|
T 46 @
|
|
A 45 @ [dec (n - i) in H order]
|
|
S 3 @
|
|
U 45 @
|
|
S 4 @ [is (n - i) now negative?]
|
|
E 44 @ [if not, loop back]
|
|
[Here with latest Catalan number in temp store 4D]
|
|
T F [clear acc]
|
|
A @ [load index]
|
|
A 2 @ [add 1]
|
|
E 16 @ [back to start of outer loop]
|
|
[64] O 7 @ [exit; print null to flush teleprinter buffer]
|
|
Z F [stop]
|
|
E 12 Z [define entry point]
|
|
P F [acc = 0 on entry]
|