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 119, lines 2022 contain some control flow values, lines 23 and 24 contain 2^18 and the current factor to test, and lines 2527 are working memory. Click for a larger version of the original image from The National Archive for the History of Computing.
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
Tags: C#, geek, math, programming

You are cool!
1 comment
Comments feed for this article
Trackback link: http://www.thefrankes.com/wp/wptrackback.php?p=2374