110 lines
4.9 KiB
Plaintext
110 lines
4.9 KiB
Plaintext
[Jospehus problem - Rosetta Code
|
|
EDSAC program (Initial Orders 2)]
|
|
|
|
[Arrange the storage]
|
|
T45K P56F [H parameter: library subroutine R4 to read integer]
|
|
T46K P80F [N parameter: subroutine to print 17-bit non-neg integer]
|
|
T47K P160F [M parameter: main routine]
|
|
T51K P128F [G parameter: subroutine to find last survivor]
|
|
|
|
[Library subroutine M3, runs at load time and is then overwritten.
|
|
Prints header; here, last character sets teleprinter to figures.]
|
|
PF GK IF AF RD LF UF OF E@ A6F G@ E8F EZ PF
|
|
*!!!!N!!!!!K!!!!SURVIVOR@&#..PZ
|
|
|
|
[============== G parameter: Subroutine to find last survivor ==============
|
|
Input: 4F = n = number of prisoners
|
|
5F = k = executioner's step
|
|
Output: 0F = 0-based index of last survivor]
|
|
|
|
[Pascal equivalent:
|
|
z := 0; // solution when n = 1
|
|
for j := 2 to n do z := (z + k) mod j;
|
|
result := z;]
|
|
E25K TG GK
|
|
A3F T22@ [plant return link as usual]
|
|
T23@ [z := 0]
|
|
A2F T24@ [j := 2]
|
|
E16@ [jump to middle of loop]
|
|
[6] TF [clear acc]
|
|
A23@ A5F [acc := z + k]
|
|
[Get residue modulo j by repeatedly subtracting j.
|
|
The number of subtractions is usually small.]
|
|
[9] S24@ E9@ [subtract j till result < 0]
|
|
A24@ [add back the last j]
|
|
T23@ [update z]
|
|
A24@ A25@ T24@ [inc(j)]
|
|
[16] A4F S24@ [acc := n - j]
|
|
E6@ [loop back if j <= n]
|
|
TF [done: clear acc]
|
|
A23@ TF [return z (last survivor) to caller in 0F]
|
|
[22] ZF [(planted) jump back to caller]
|
|
[Storage]
|
|
[23] PF [Pascal z]
|
|
[24] PF [Pascal j]
|
|
[25] PD [constant 1]
|
|
|
|
[====================== M parameter: Main routine ======================]
|
|
E25K TM GK
|
|
[0] PF [negative data count]
|
|
[1] PF [number of prisoners]
|
|
[2] PF [executioner's step]
|
|
[3] !F [space]
|
|
[4] @F [carriage return]
|
|
[5] &F [line feed]
|
|
[6] K4096F [null character]
|
|
[Enter with acc = 0]
|
|
[7] A7@ GH [call subroutine R4, sets 0D := count of (n,k) pairs]
|
|
SF [acc := count negated; it's assumed that count < 2^16]
|
|
E46@ [exit if count = 0]
|
|
LD [shift count into address field]
|
|
[12] T@ [update negative loop counter]
|
|
A13@ GH [call library subroutine R4, 0D := number of prisoners]
|
|
AF T1@ [store number of prisoners, assumed < 2^16]
|
|
A17@ GH [call library subroutine R4, 0D := executioner's step]
|
|
AF T2@ [store executioner's step, assumed < 2^16]
|
|
A3@ T1F [to print leading 0's as spaces]
|
|
A1@ TF [pass number of prisoners to print subroutine]
|
|
A25@ GN O3@ [print number of prisoners, plus space]
|
|
A2@ TF [same for executioner's step]
|
|
A30@ GN O3@
|
|
A1@ T4F [pass number of prisoners to "last survivor" subroutine]
|
|
A2@ T5F [same for executioner's step]
|
|
A37@ GG [call subroutine, 0F := 0-based index of last survivor]
|
|
A39@ GN O4@ O5@ [print last survivor, plus CR,LF]
|
|
A@ A2F [increment negative counter]
|
|
G12@ [loop back if still negative]
|
|
[46] O6@ [print null to flush printer buffer]
|
|
ZF [halt the machine]
|
|
|
|
[The next 3 lines put the entry address into location 50,
|
|
so that it can be accessed via the X parameter (see end of program).]
|
|
T50K
|
|
P7@
|
|
T7Z
|
|
|
|
[================== H parameter: Library subroutine R4 ==================
|
|
Input of one signed integer, returned in 0D.
|
|
22 locations.]
|
|
E25K TH GK
|
|
GKA3FT21@T4DH6@E11@P5DJFT6FVDL4FA4DTDI4FA4FS5@G7@S5@G20@SDTDT6FEF
|
|
|
|
[============================= N parameter ==============================
|
|
Subroutine to print non-negative 17-bit integer.
|
|
Input: 0F = integer to be printed (not preserved)
|
|
1F = character for leading zero (preserved)
|
|
Workspace: 4F..7F, 38 locations]
|
|
E25K TN
|
|
GKA3FT34@A1FT7FS35@T6FT4#FAFT4FH36@V4FRDA4#FR1024FH37@E23@O7FA2F
|
|
T6FT5FV4#FYFL8FT4#FA5FL1024FUFA6FG16@OFTFT7FA6FG17@ZFP4FZ219DTF
|
|
|
|
[==========================================================================
|
|
On the original EDSAC, the following (without the whitespace and comments)
|
|
might have been input on a separate tape.]
|
|
E25K TX GK
|
|
EZ [define entry point]
|
|
PF [acc = 0 on entry]
|
|
[Count of (n,k) pairs, then the pairs, to be read by library subroutine R4.
|
|
Note that sign comes *after* value.]
|
|
10+5+2+12+4+41+3+50+2+60+3+71+47+123+3+123+47+10201+17+23482+3343+
|