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
  • Clock: 0 Hz

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:

  1. The orbit length (i.e. the number of steps it took to reach 1)
  2. 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:

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

Writing input:

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

Reading output:

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

IO

#InputOutputBidirectional
0input0output0address0
1input1output1address1
2input2output2address2
3input3output3address3
4input4output4address4
5input5output5orbit/max select
6input6output6start compute
7input7output7write enable or compute busy indicator

Chip location

Controller Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux Mux tt_um_chip_rom (Chip ROM) tt_um_factory_test (TinyTapeout 05 Factory Test) tt_um_loopback (TinyTapeout 05 Loopback Test Module) tt_um_Leaky_Integrate_Fire_nfjesifb (Leaky Integrate and Fire Neuron Model) tt_um_topModuleKA (Time Multiplexed Neuron Ckt) tt_um_sap_1 (SAP-1 Computer) tt_um_lif (Leaky Integrate-and-Fire Neuron (Verilog Demo)) tt_um_jleugeri_ticktocktokens (TickTockTokens) tt_um_LSNN (Spiking LSTM Network) tt_um_if (Integrate-and-Fire Neuron. (Verilog Demo)) tt_um_mihailocode_neural_network (Neural network on chip) tt_um_hls_lfi (Simple Leaky Integrate and Fire (LIF) Neuron) tt_um_diadatp_spigot_e (e Spigot) tt_um_kskyou (Continued Fraction Calculator) tt_um_wokwi_380005495431181313 (Water Pump Controller) tt_um_EventFilter (Event Denoising Circuit) tt_um_wokwi_380416099936681985 (7 segment seconds (Verilog Demo)) tt_um_freq_hcohensa (Frequency Encoder/Decoder) tt_um_wokwi_380410498092232705 (UART Greeter with RNN Module) tt_um_wokwi_380120751165092865 (WS2812B LED strip driver) tt_um_wokwi_380408486941145089 (Tiny Tapeout 5 Workshop) tt_um_wokwi_380409169798008833 (Tiny Tapeout 1) tt_um_wokwi_380409488188706817 (Supercon Workshop) tt_um_matrix_multiplier (Matrix Multiplier) tt_um_wokwi_380408594272345089 (Clock Divider) tt_um_wokwi_380408784463076353 (Binary Counter) tt_um_wokwi_380408396356749313 (ring osc test) tt_um_7segx4_clock_abhishek_top (7 segment clock with 4 digits) tt_um_wokwi_380409481852161025 (test001) tt_um_hodgkin_huxley (Hodgkin-Huxley Chip Design) tt_um_wokwi_380408823952452609 (Character Selector) tt_um_wokwi_380409904919056385 (Intructouction to PRBS) tt_um_wokwi_380409081067502593 (tto5 Supercon Project) tt_um_jmadden173_delta_modulation (Delta Modulation Spike Encoding) tt_um_wokwi_380409086743445505 (GameOfLife) tt_um_reflex_game (Reflex Game) tt_um_wokwi_380409019830656001 (Logic Gates Tapeout) tt_um_Fiona_CMU (Stream Cipher w/ LSR) tt_um_wokwi_380409532780455937 (tt5modifyd) tt_um_alu_chip (ALU Chip) tt_um_wokwi_380408936929183745 (Tapeout Test) tt_um_rjmorgan11_calculator_chip (Calculator chip) tt_um_wokwi_380409369220404225 (Shifty Snakey) tt_um_synth_GyanepsaaS (Synth) tt_um_wokwi_380408774591779841 (Sawtooth Generator) tt_um_wokwi_380197591775930369 (Blinking A) tt_um_wokwi_380409393770716161 (Supercon 2023) tt_um_mvm (Sparsity Aware Matrix Vector Multiplication) tt_um_wokwi_380408455148316673 (Ring Oscillator and Clock Source Switch) tt_um_mv_mult_alrdelcr (Matrix Vector Multiplication (Verilog Demo)) tt_um_wokwi_380416361853146113 (IDK WHAT TO DO) tt_um_wokwi_379319062779062273 (7-segment display logic system ) tt_um_wokwi_380409568391147521 (Hardware Trojan Example) tt_um_wokwi_379824923824476161 (Analog Clock) tt_um_wokwi_380145600224164865 (7 segment display) tt_um_wokwi_379889284755158017 (W_Li_10/28) tt_um_wokwi_380408409844584449 (Supecon Gate Play) tt_um_manjushettar (ECE 183 - Integrate and Fire Network Chip Design) tt_um_wokwi_380409236812508161 (tto5) tt_um_rebel2_balanced_ternary_ALU (REBEL-2 Balanced Ternary ALU) tt_um_wokwi_380229599886002177 (Stochastic Multiplier) tt_um_jeffdi_seven_segment_seconds (7 segment seconds - count down) tt_um_wokwi_380416616536542209 (TT05 Submission) tt_um_lif_n (Leaky Integrate-and-Fire Neuron) tt_um_wokwi_379764885531576321 (Count via LFSR) tt_um_dlmiles_tt05_i2c_bert (I2C BERT) tt_um_loopback_ericsmi (tt05-loopback tile with input skew measurement) tt_um_flappy_vga_cutout1 (Flappy VGA) tt_um_async_proc_paulschulz (Asynchronous Parallel Processor Demonstrator) tt_um_wokwi_380055891603379201 (Hex Countdown) tt_um_nickjhay_processor (Matrix multiply coprocessor (8x8 1bit)) tt_um_htfab_cell_tester (Standard cell generator and tester) tt_um_wta (Winner-Take-All Network (Verilog Demo)) tt_um_muncherkin_lioncage (Lion cage) tt_um_seven_segment_seconds_ksandov4 (Brain Inspired Random Dropout Circuit) tt_um_seanvenadas (Event-Based Denoising Circuit) tt_um_wokwi_378231665807713281 (RAM cell test) tt_um_rejunity_ay8913 (Classic 8-bit era Programmable Sound Generator AY-3-8913) tt_um_rnn (RNN (Demo)) tt_um_gharenthi_top (STDP Neuron) tt_um_SNN (Basic Spiking Neural Network) tt_um_btflv_8bit_fp_adder (8 bit floating point adder) tt_um_perceptron (Perceptron Hardcoded) tt_um_jkprz (Cheap and quick STDP) tt_um_topLevel_derekabarca (Brain-Inspired Oscillatory Network) tt_um_uwuifier (UART uwuifier) tt_um_perceptron_connorguzi (Perceptron and basic binary neural network) tt_um_hadirkhan10_lif_neuron (Leaky Integrate-and-Fire Neuron) tt_um_wokwi_380119282165535745 (7 segment seconds) tt_um_uabc_electronica_2023 (UABC-ELECTRONICA) tt_um_proppy_bytebeat (bytebeat) tt_um_meriac_play_tune (Super Mario Tune on A Piezo Speaker) tt_um_wrapper_inputblackboxoutput (Byte Computer) tt_um_vhdl_seven_segment_seconds (7 segment seconds (VHDL Demo)) tt_um_cejmu (4-Bit ALU) tt_um_rejunity_sn76489 (Classic 8-bit era Programmable Sound Generator SN76489) tt_um_minipit_stevej (Miniature Programmable Interrupt Timer) tt_um_gchenfc_seven_segment_gerry (7-segment Name Display) tt_um_supertails_tetris (Tetris) tt_um_mabhari_seven_segment_seconds (Simple_Timer-MBA) tt_um_njzhu_uart (UART Receiver) tt_um_wokwi_376553022662786049 (AGL CorticoNeuro-1) tt_um_adaptive_lif (Leaky-Integrated Fire Neuron) tt_um_myuart (MyUART) tt_um_wokwi_380438365946734593 (UART test) tt_um_tkmheart (Heart Rhythm Analyzer) tt_um_stdp (Spike-timing dependent plasticity (Verilog Demo)) tt_um_wokwi_380465686251921409 (Tiny Tapeout 5 TM project1) tt_um_thermocouple (Thermocouple-to-temperature converter (digital backend)) tt_um_wokwi_380412382001715201 (Naive 8-bit Binary Counter) tt_um_asinghani_tinyscanchain_tt05 (tinyscanchain Test Design) tt_um_carlosgs99_cro_udg (6 digit chronometer.) tt_um_suhrojo (Convolutional Network Circuit Chip Design) tt_um_mvm_ (Matrix Vector Multiplication Accelerator) tt_um_perceptron_neuromeme (Perceptron (Neuromeme)) tt_um_czlucius_alu (4 Bit ALU) tt_um_BNNNeuron (Binary Neural Network (Verilog Demo)) tt_um_urish_skullfet (SkullFET) tt_um_ja1tye_sound_generator (Wavetable Sound Generator) tt_um_jaylennee_wta_pwm (PWM signal generation with Winner-Take-All selection) tt_um_joerdsonsilva_top (Multimode Modem) tt_um_toivoh_synth (Analog emulation monosynth) tt_um_tiny_game_of_life (Tiny Game of Life) tt_um_mingkaic1_stack_machine (Stack Machine) tt_um_morningjava_top (ChipTune) tt_um_urish_silife (Game of Life 8x8 (siLife)) tt_um_tt05_analog_test (TT05 Analog Testmacro (Ringo, DAC)) tt_um_wokwi_380409528895479809 (RBUART) tt_um_mattngaw_fp8 (8-bit Floating-Point Adder) tt_um_chip_inventor_music__6_bit_count (6 bit Counter and Piano Music created by Chip Inventor) tt_um_4_bit_pipeline_multiplier (4 Bit Pipelined Multiplier) tt_um_wokwi_380477805171811329 (2-Bit ALU + Dice) tt_um_wokwi_380490286828784641 (TT02 Wokwi 7seg remake) tt_um_wokwi_380361576213660673 (ping pong asic) tt_um_prg (A Boolean function based pseudo random number generator (PRNG)) tt_um_digital_clock_sellicott (Digital Desk Clock) tt_um_haozhezhu_top (4-bit FIFO/LIFO) tt_um_top_mole99 (One Sprite Pony) tt_um_GrayCounter_ariz207 (4 bit Sync Gray Code Counter) tt_um_clkdiv (Clock and Random Number Gen) tt_um_matt_divider_test (TT05 Analog Test) tt_um_tomkeddie_a (VGA Experiments) tt_um_rejunity_rule110 (Rule110 cell automata) tt_um_no_time_for_squares_tommythorn (No Time for Squares) tt_um_urish_silife_max (Game of Life 8x32 (siLife)) tt_um_gfg_development_tros (TROS) tt_um_chatgpt_snn_mtomlin5 (ChatGPT designed Spiking Neural Network) tt_um_ks_pyamnihc (Karplus-Strong String Synthesis) tt_um_dinogame (VGA Dino Game) tt_um_himanshu5_prog_chipTop (Dual Compute Unit) tt_um_rtfb_collatz (Collatz conjecture brute-forcer) tt_um_retospect_neurochip (Field Programmable Neural Array) tt_um_urish_dffram (DFFRAM Example (128 bytes)) tt_um_rejunity_snn (Chonky SNN) tt_um_hh (Hodgkin-Huxley Neuron) tt_um_wokwi_377426511818305537 (PRBS Generator) tt_um_devinatkin_stopwatch (Stop Watch) tt_um_algofoogle_vga_spi_rom (vga_spi_rom) tt_um_blink (RO and counter) tt_um_ttl74hc595_v2 (8-Bit Shift Register with Output Latches 74HC595) tt_um_psychogenic_neptuneproportional (Neptune guitar tuner (proportional window, version b, debug output on bidir pins, larger set of frequencies)) tt_um_urish_simon (Simon Says game) tt_um_kianV_rv32ima_uLinux_SoC (KianV uLinux SoC) tt_um_urish_ringosc_cnt (Ring oscillator with counter) tt_um_sunaofurukawa_cpu_8bit (cpu_8bit) tt_um_vga_clock (VGA clock) tt_um_seven_segment_seconds (7 segment seconds (Verilog Demo)) tt_um_frequency_counter (Frequency counter) tt_um_rgb_mixer (RGB Mixer) tt_um_MichaelBell_spi_peri (SPI Peripheral) tt_um_multiplexed_clock (Multiplexed clock) tt_um_psychogenic_shaman (Shaman: SHA-256 hasher) tt_um_yubex_metastability_experiment (metastability experiment) Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available Available