[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+