Tiny Tapeout > Tiny Tapeout Chips > Tiny Tapeout 5 > 462 Collatz conjecture brute-forcer

462 Collatz conjecture brute-forcer

462 : Collatz conjecture brute-forcer

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.
GitHub repository
GDS submitted
HDL project
Extra docs
Clock: 0 Hz
External hardware:

How it works

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 orbit length (i.e. the number of steps it took to reach 1)
The highest recorded value of the upper 16 bits of the 144-bit internal iterator

The latter number is an indicator for good candidates for computing path records. The non-zero upper bits indicate that the highest iterator value 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).

How to test

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:

Set input (see below)
Pull start compute pin to high. The chip will start computations and will pull compute busy indicator pin to high
Keep reading compute busy indicator pin until it gets low again
Read the output (see below)

Writing input:

Set write enable pin to low
Wait at least one cycle
Expose your input byte to input0-7
Expose the target address for that byte to address0-4
Wait at least one cycle
Set write enable pin to high

Reading output:

Set orbit/max select pin to low
Set address0-4 to 0
Read low byte of orbit length from output0-7
Set address0-4 to 1
Read high byte of orbit length from output0-7
Set orbit/max select pin to high
Repeat steps 2-5 to read the upper Mx(N) bits

IO

#	Input	Output	Bidirectional
0	input0	output0	address0
1	input1	output1	address1
2	input2	output2	address2
3	input3	output3	address3
4	input4	output4	address4
5	input5	output5	orbit/max select
6	input6	output6	start compute
7	input7	output7	write enable or compute busy indicator

462 Collatz conjecture brute-forcer