Calkin-Wilf sequence: Difference between revisions
no edit summary
(Added 3rd algorithm for calculating terms, and put all 3 algorithms into one program.) |
No edit summary |
||
Line 390:
20: 3/8
83116/51639 is the 123456789th term of the sequence.
</pre>
=={{header|EDSAC order code}}==
===Find first n terms===
{{trans|Pascal}}
<lang edsac>
[For Rosetta Code. EDSAC program, Initial Orders 2.
Prints the first 20 terms of the Calkin-Wilf sequence.
Uses term{n} to calculate term{n + 1}.]
[Print subroutine for non-negative 17-bit integers.
Parameters: 0F = integer to be printed (not preserved)
1F = character for leading zero (preserved)
Workspace: 4F, 5F. Even address; 40 locations]
T 56 K [define load address]
GKA3FT34@A1FT35@S37@T36@AFT5FT4FH38#@V4DH30@
R32FR16FYFE23@O35@A2FT36@T5FV4DYFL8FT4DA5FL1024F
UFA36@G16@OFTFT35@A36@G17@ZFPFPFP4FT1714FZ219D
[Main routine]
T 100 K [define load address]
G K [set up relative addressing via @ (theta)]
[Constants]
[0] P 10 F [maximum index = 20, edit ad lib.]
[1] P D [constant 1]
[Teleprinter characters]
[2] # F [set figures mode]
[3] C F [colon (in figures mode)]
[4] X F [slash (in figures mode)]
[5] ! F [space]
[6] @ F [carriage return]
[7] & F [line feed]
[8] K 4096 F [null]
[Variables]
[9] P F [index]
[10] P F [a (where term = a/b)]
[11] P F [b]
[Enter with acc = 0]
[12] O 2 @ [set teleprinter to figures]
A 1 @ [acc := 1]
U 9 @ [index := 1]
U 10 @ [a := 1]
T 11 @ [b := 1 (and clear acc)]
E 34 @ [jump to print first term]
[Loop back here if not yet printed enough terms]
[18] A @ [restore index after test]
A 1 @ [add 1]
T 9 @ [update index]
[Calculate next term. New b := a + b - 2(a mod b).
Code below calculates c := (a mod b) - b, then new b := a - b - 2*c]
A 10 @ [acc := a]
[22] S 11 @ [subtract b]
E 22 @ [if acc >= 0, subtract again]
T F [result c < 0, store in 0F]
A 10 @ [acc := a]
S 11 @ [subtract b]
S F [subtract c]
S F [subtract c]
T F [new b = a - b - 2*c; store in 0F]
A 11 @ [acc := old b]
T 10 @ [copy to a]
A F [acc := new b]
T 11 @ [copy to b]
[Print index and a/b. Assume acc = 0 here.]
[34] A 5 @ [space to replace leading 0's]
T 1 F [pass to print subroutine]
A 9 @ [acc := index]
T F [pass to print subroutine]
[38] A 38 @ [for return from subroutine]
G 56 F [call subroutine, clears acc]
O 3 @ [print colon]
O 5 @ [print space]
A 8 @ [null to replace leading 0's]
T 1 F [pass to print subroutine]
A10@ TF A46@ G56F O4@ [print a followed by slash]
A11@ TF A51@ G56F O6@ O7@ [print b followed by CR LF]
[Test whether enough terms have been printed]
A 9 @ [acc := index]
S @ [subtract maximum index]
G 18 @ [loop back if acc < 0]
[Exit]
O 8 @ [print null to flush teleprinter buffer]
Z F [stop]
E 12 Z [relative address of entry point]
P F [enter with acc = 0]
[end]
</lang>
{{out}}
<pre>
1: 1/1
2: 1/2
3: 2/1
4: 1/3
5: 3/2
6: 2/3
7: 3/1
8: 1/4
9: 4/3
10: 3/5
11: 5/2
12: 2/5
13: 5/3
14: 3/4
15: 4/1
16: 1/5
17: 5/4
18: 4/7
19: 7/3
20: 3/8
</pre>
===Find index of a given term===
{{trans|Pascal}}
<lang edsac>
[For Rosetta Code. EDSAC program, Initial Orders 2.]
[Finds the index of a given rational in the Calkin-Wilf series.]
[Library subroutine R2: input of positive integers.
Runs during input of the program, and is then overwritten.
Allows integers to be written in decimal, rather than as "pseudo-orders".
See Wilkes, Williams & Gill, 1951 edn, pp. 96-97, 148.]
T 54 K [to access integers via C parameter]
P 110 F [where to load integers]
GKT20FVDL8FA40DUDTFI40FA40FS39FG@S2FG23FA5@T5@E4@E13Z
T #C [tell R2 where to load integers]
[F after each integer except the last, and # after the last.]
83116F51639#
[Modified library subroutine P7.
Prints signed integer up to 10 digits, left-justified.
Input: Number to be printed is at 0D.
54 locations. Load at even address. Workspace 4D.]
T 56 K
GKA3FT42@A49@T31@ADE10@T31@A48@T31@SDTDH44#@NDYFLDT4DS43@
TFH17@S17@A43@G23@UFS43@T1FV4DAFG50@SFLDUFXFOFFFSFL4FT4DA49@
T31@A1FA43@G20@XFP1024FP610D@524D!FO46@O26@XFSFL8FT4DE39@
[Main routine.]
T 120 K [define load address (must be even)]
G K [set up relative addressing via @ (theta)]
[Put 35-bit values first, to ensure each is at an even address]
[Variables]
[0] P F P F [a]
[2] P F P F [b]
[4] P F P F [power of 2]
[6] P F P F [calculated index]
[Constants]
T8#Z PF T8Z [clears sandwich digit between 8 and 9]
[8] P D P F [35-bit constant 1]
[Teleprinter characters]
[10] # F [set figures mode]
[11] X F [slash (in figures mode)]
[12] K 2048 F [set letters mode]
[13] I F [letter I]
[14] R F [letter R]
[15] ! F [space]
[16] @ F [carriage return]
[17] & F [line feed]
[18] K 4096 F [null char]
[Enter with acc = 0]
[19] A #C [acc := initial a]
T #@ [copy to variable]
A 2#C [acc := initial b]
T 2#@ [copy to variable]
[23] A 8#@ [acc := 1]
[24] T 4#@ [initialize power of 2]
T 6#@ [initialize index to 0]
[Loop]
[26] A #@ [acc := a]
[27] S 2#@ [subtract b]
[28] E 33 @ [jump if a >= b]
[Here if a < b]
T D [store a - b in 0D]
S D [negate]
T 2#@ [b := b - a]
E 40 @ [join common code]
[Here if a >= b]
[33] S 8#@ [acc = a - b; test for a = b]
G 45 @ [jump out of loop if so]
A 8#@ [restore a - b]
T #@ [a := a - b]
A 6#@ [acc := index]
A 4#@ [inc index by power of 2]
T 6#@
[Code common to both cases]
[40] A 4#@ [acc := power of 2]
L D [shift left]
G 76 @
T 4#@ [update power of 2]
E 26 @ [loop back]
[Exit from loop.]
[45] T D [dump acc to clear it]
A 6#@ [acc := index]
A 4#@ [add power of 2 ]
T 6#@ [store final value of index]
[Finished calcualting index, now do printing]
O 10 @ [set teleprinter to figures]
A #C [acc := initial a]
T D [to 0D for printing]
[52] A 52 @ [for return from subroutine]
G 56 F [call print subroutine, clears acc]
O 11 @ [print slash]
A 2#C [print initial b similarly]
T D
[57] A 57 @
G 56 F
O 12 @ [set teleprinter to letters and print ' IS AT ']
O15@ O13@ O27@ O15@ O23@ O24@ O15@
O 10 @ [set teleprinter to figures]
A 6#@ [acc := calculated index]
T D [send to print subroutine]
[70] A 70 @
G 56 F
[72] O16@ O17@ [print CR, LF]
O 18 @ [print null to flush teleprinter buffer]
Z F [stop]
[Here if power of 2 goes negative (accumulator overflow)]
[76] O 12 @ [set teleprinter to letters]
O28@ O14@ O14@ O76@ O14@ [print'ERROR']
G 72 @ [jump to common exit]
E 19 Z [relative address of entry point]
P F [enter with acc = 0]
</lang>
{{out}}
<pre>
83116/51639 IS AT 123456789
</pre>
| |||