Aim: perform binary modular division on an arbitrary length number
(requires more than a standard sized board and pieces).
Input by manually pressing blue and red levers multiple times
Intercept all balls.
Read output from bit settings after last ball gone through
(example below based on CRC-4 and dividing by 10011)
design for the solution
Binary Modular Division
Binary modular division places some constraints on the numbers. Dividing by prime numbers works.
CRC Checks use polynomials that seem to correspond to prime numbers, and so I picked an example of division based on one of the CRC-4 approaches (X^4+X+1, corresponding to something like dividing by 10011. But this is binary modular division, based on tracking 4 bits. Its not the same as integer division).
The approach to this using a Turing Tumble (well, using more pieces and a bigger than standard board) is to consider it in parts:
- Binary bitstream in, generated by a series of pushes on the blue and red lever (intercept all balls). Bitstream can be arbitrarily long (see post of @lennypitt binary input streams
- A shift register. Each bit in the register corresponds to a TT flip flop. As a ball cascades down the register, it sets each bit to what the bit above had been before the ball came through.
- A control-shift. This supports two scenarios. If the control bit is “0”, on the next ball through the bit takes the value the bit above had been. If the control bit is “1”, on the next ball through the ball takes the value opposite. A ball passing through a control shift must leave the control bit as it found it (I suspect there are much more elegant and shorter ways to do this!)
- A master control bit, transmitted to wherever needed. In this case, it’s the value of the bottom register.
The algorithm.
Consider a sequence of 1s and zeros, but as if entered into the machine, MSB first.
Binary Modular division continues similarly to long division.
Suppose the initial string S is 1010110 …. And the divisor D is 10011
The shift register “models” D =(1)0011
If the bottom bit is a 0, the shift register drops down one (all bits unchanged, just shifted down one position)
If the bottom bit is a 1, then SOME bits drop down, and SOME bits are inverted:
- The 2nd and 3rd bits of D are zero , so register bits 2 and 3 drop unchanged (into positions 1 and 2).
- The 4th and 5th bits of D are 1, therefore the register bits coming from register bit 4 and also the incoming ball are inverted.
This is equivalent to a conditional exclusive OR with the last 4 bits of the divisor (conditional upon there being a 1 in the bottom register, setting the master control bit).
When the operator has completed inputting the sequence, the binary modular division output is given by the contents of the 4 register bits. This corresponds to the result as shown in online calculators eg here
Relationship to CRC checksum.
To use as a CRC-4 checksum requires the following behaviour:
At the end of the message S, the operator has to add 4 zeros (ie, key in the message S and then press the red lever 4 more times before taking the result. Then read the 4 bit output and call it the CKSM CKSM.
Append the CKSM bits to the original message S.
If S with CKSM is put through the same configuration (assuming no errors in the process), it will give a 4 bit result of 0000, demonstrating with a degree of confidence that no errors in keying took place. A result different from 0000 proves something went wrong.
Extension to other divisors
Not all divisors work. Prime numbers are OK, and anything corresponding to a CRC-n polynomial is OK.
An extensible and configurable approach would be to make ALL parts of the shift register controllable, but disconnect from the gear drive those that do not need to be controlled (and remembering to ensure any disconnected control bits are set to zero!!)
I haven’t tried using the Excel simulator yet, but none of the others I’ve seen seem big enough to handle a CRC-4. Any suggestions from the community?
I note an earlier post about cryptographic hashes. CRC checks are not a suitable alternative, as they are easy to reverse. The operations required for SHA seem massively more complicated than CRC-n. Perhaps modular exponentiation might be a suitable next step? (Provides an element of being harder to do in reverse)