diff options
Diffstat (limited to 'collatz/collatz.v')
-rw-r--r-- | collatz/collatz.v | 79 |
1 files changed, 79 insertions, 0 deletions
diff --git a/collatz/collatz.v b/collatz/collatz.v new file mode 100644 index 0000000..e046815 --- /dev/null +++ b/collatz/collatz.v @@ -0,0 +1,79 @@ +/** + * Collatz Conjecture module. + * + * Takes a start integer and calculates the number of steps + * required for that number to get down to 1 using the collatz + * conjecture. + */ +module collatz #( + parameter integer WIDTH = 16 +) ( + /* Input clock and reset pin. */ + input clk, + input rst, + + /* The number to calculate. */ + input wire [WIDTH-1:0] in_start, + /* Pulsing the start_int pin will start the calculation. */ + input wire start_int, + + /* Output count. */ + output reg [WIDTH-1:0] o_count, + + /* Set to high when the module is idle and ready to start. + * While computing, this output is set to low. + * + * A positive edge of this will indicate the output is ready + * to be consumed. */ + output idle +); + + // Define some state parameters. + localparam integer IDLE = 0; + localparam integer SPINNING = 1; + + reg state = 0; + reg [WIDTH-1:0] count = 0; + reg [WIDTH-1:0] n = 0; + + wire is_even = ~n[0]; // Is the current value even. + assign idle = state == IDLE; + + // When the start_int input is set to high, copy the in_start to the current + // number and set the state to SPINNING. + always @(posedge start_int) begin + if (state == IDLE) begin + state <= SPINNING; + n <= in_start; + end + end + + // Each clock cycle, determine what needs to happen. + always @(posedge clk or posedge rst) begin + // On reset, reset the state. + if (rst == 1'b1) begin + count = 0; + state <= IDLE; + n <= 0; + + // If the state is idle, reset the count to 0. + end else if (state == SPINNING) begin + // If n is 1, then set the output and go back to the IDLE state. + if (n <= 1) begin + o_count = count; + n <= 0; + state = IDLE; + end else begin + // If is_even, divide by two, otherwise multiply by 3 and add 1. + if (is_even) begin + n <= n >> 1; + end else begin + n <= n * 3 + 1; + end + // Increment the count. + count <= count + 1; + end + end + end + +endmodule |