Turing Trains

Multiply AxB

This layout multiplies two binary numbers, held in input registers A and B, and outputs the result in register S. The calculation is performed by a series of additions.

Two functions are used:

1. Count Down function to decrement A.
2. Accumulator function, to add B into S.

Operation

Clear register S. Enter binary values for A and B (eg 3x5) and start the train from the station. When the train returns and halts, the result of AxB can be read from the output register S.

Layout to calculate AxB

	Lazy points switch between upper 0 or lower 1 branch lines Trains arriving on a branch line switch the point to that line
	Sprung points allow branch line trains to join the main line All main line trains go straight ahead and never 'branch off'

Notes

1. If the result of A x B exceeds 31, register S overflows and the train returns to the lower station platform as an error. This should not happen unless dividing by zero. This can be prevented, see 'with swop' below.
2. Register A is checked first. If it is 0, the train returns to the station and the calculation halts.
3. The original value of A is 'lost' as the register counts down. A Copy function can be added to preserve the initial value of A.
4. Multiplication is commutative, so AxB = BxA. A quicker calculation is obtained if the shorter number is entered into the A register. Calculating 1x15 is quick but 15x1 is slow.

Multiply AxB (with swop)

When multiplying say 7x2, the above layout performs seven additions of 2 to the Accumulator. With larger registers this can be very slow. To improve efficiency, the value of A and B is first compared. If A is less than B, the two values are swopped.

Two additional functions are used:

1. Comparator function to compare A and B.
2. Exchange function, to swop A and B.

The Decrementor counts down the value of A. By swopping A and B so that A is the smaller value improves efficiency. The maximum number of loop iterations is limited to the square root of the length of S. So for this layout it is 5. A sixth iteration will cause S to overflow.

Layout to calculate AxB

	Lazy points switch between upper 0 or lower 1 branch lines Trains arriving on a branch line switch the point to that line
	Sprung points allow branch line trains to join the main line All main line trains go straight ahead and never 'branch off'

Here is a non-interactive image of a possible computer layout of the above circuit.

Also see Multiplier using a shift register.