To mark the 63rd anniversary of the first stored computer program to run (June 21), I rewrote the original code in C# last night, both using the original algorithm (that was never intended to be efficient) and using a more modern structure. The Kilburn Highest Factor Routine finds the highest factor of 2^18, and completed with the correct answer in 52 minutes with 3.5 million operations. It was written by the late computer pioneer Tom Kilburn and run on the Machester SSEM (“Baby”).
The code is written in lines 1-19, lines 20-22 contain some control flow values, lines 23 and 24 contain 2^18 and the current factor to test, and lines 25-27 are working memory. Click for a larger version of the original image from The National Archive for the History of Computing.
Kilburn Highest Factor Routine
The last three columns (labelled 13, 14, and 15) are the instructions, and there are only a few of them. They are:
- 100 – Jump forward or backward in code by the amount at the address given.
- 010 – Load the negative of the value at the given address into the accumulator.
- 110 – Store the value in the accumulator to the given address.
- 001 – Subtract the value at the given address from the value in the accumulator, and keep the result in the accumulator.
- 011 – Skip the next line if the value in the accumulator is greater than zero.
- 111 – Halt
The first version in the listing below follows the original algorithm (and yes, you can use “goto” in C#). There’s a lot of subtraction involved because if you’re short on space and only want to implement one arithmetic operator, you’re better off implementing subtraction, because you can so addition with it, too. “S” is used here to indicate the Storage tube, which stored both the program and the working memory. The accumulator (represented by the variable “acc”) and the program counter used different tubes. The program counter is what kept track of where the computer was in the program during execution.
The only slightly optimized C# version at the bottom takes less than a millisecond today.
Stopwatch sw = new Stopwatch();
sw.Start();
int s20_jump_rel = -3; // unused in code, provided for completeness
int s21_const_1 = 1; // the amount to decrement the number being tested
int s22_jump_addy = 4; // unused in code, provided for completeness
int s23_number_neg = -262144; // the number to solve (find the factor of)
int s24_div_init = 262143; // the initial number to test
int acc = 0;
acc = -s24_div_init; // S01 - Load and negate the initial number to test
int s26_div_neg = acc; // S02 - Store that number into S26
S03:
acc = -s26_div_neg; // S03 - Load and negate the negated current number to test
int s27_div_pos = acc; // S04 - Store that number into S27
acc = -s23_number_neg; // S05 - Load and negate the number to solve
S06:
acc -= s27_div_pos; // S06 - Subtract the current number to test
if( acc >= 0 ) // S07 - If the accumulator is > 0...
goto S06; // S08 - ...go back to S06
acc -= s26_div_neg; // S09 - Subtract the negated current number to test
int s25 = acc; // S10 - Store that number into S25
acc = -s25; // S11 - Load and negate the number in S25
if( acc >= 0 ) // S12 - If the accumulator is > 0...
goto HALT; // S13 - ...End
acc = -s26_div_neg; // S14 - Load and negate the negated current number to test
acc -= s21_const_1; // S15 - Subtract 1
s27_div_pos = acc; // S16 - Store that number into S27
acc = -s27_div_pos; // S17 - Load and negate the number in S27
s26_div_neg = acc; // S18 - Store that number into S26
goto S03; // S19 - Go back to S03
HALT:
sw.Stop();
Console.WriteLine( "Elapsed={0}", sw.Elapsed ); // Write the elapsed time
Console.WriteLine( s27_div_pos ); // Write the result
sw.Restart(); // Restart the stopwatch for a more modern version
int i = 262143; // Set the initial number to test
while( 262144 % i-- != 0 ) ; // Decrement until the number to solve modulus zero is zero
sw.Stop();
Console.WriteLine( "Elapsed={0}", sw.Elapsed ); // Write the elapsed time
Console.WriteLine( i + 1 ); // Write the result
