Author: Vytautas Šaltenis
Description: Runs a Collatz sequence calculation for a given number, outputs the number of steps it took to reach 1 (a.k.a. orbit length) and the upper 16 bits of the highest number of the sequence.
Clock: 0 Hz
The module takes a (large) integer number
N as an input and computes the
Collatz sequence until it reaches 1. When it does, it allows reading
back two numbers:
The latter number is an indicator for good candidates for computing path
records. The non-zero upper bits indicate that the highest iterator
Mx(N) is in the range of the previous path records and should be
recomputed in the full offline. (Holding on to the entire 144 bits of
Mx(N) number would be more obvious, but this almost doubles the footprint
of the design, hence, this optimisation).
The module can be in 2 states: IO and COMPUTE. After reset, the chip will be in IO mode. Since the input is intended to be much larger that the available pins, the input number is uploaded one byte at a time, increasing the address of where in the internal 144-bit-wide register that byte should be stored.
Same for reading the output, except that the output numbers are limited to 16-bits each, so it takes much fewer operations to read them.
The full loop of computations works like this:
start compute pin to high. The chip will start computations and
compute busy indicator pin to high
compute busy indicator pin until it gets low again
write enable pin to low
write enable pin to high
orbit/max select pin to low
address0-4 to 0
address0-4 to 1
orbit/max select pin to high
|write enable or compute busy indicator