Skip to content

Instantly share code, notes, and snippets.

@gasin

gasin/collatz.c

Created January 15, 2018 05:16
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save gasin/f8ba048d3334e6d74691eea9894a1b62 to your computer and use it in GitHub Desktop.
Save gasin/f8ba048d3334e6d74691eea9894a1b62 to your computer and use it in GitHub Desktop.
Download ZIP
HW report
Raw
collatz.c
#include <stdio.h>
#include <time.h>
#include <unistd.h>
#include <stdint.h>
#include <intrin.h>
uint64_t rdtsc(){
return __rdtsc();
}
int name[4], a1[4], a2[4];
uint64_t start, end;
int main()
{
start = rdtsc();
for (int i = 512; i <= 1023; i++) {
int x = i;
int h = i, l = 0;
while (x != 1) {
l++;
if (x&1) {
x = x*3+1;
h = (h<x?x:h);
} else {
x /= 2;
}
}
if (a1[0] <= h) {
if (a1[0] == h) {
if (a2[0] < l) {
name[0] = i;
a2[0] = l;
}
} else {
name[3] = name[2]; a1[3] = a1[2]; a2[3] = a2[2];
name[2] = name[1]; a1[2] = a1[1]; a2[2] = a2[1];
name[1] = name[0]; a1[1] = a1[0]; a2[1] = a2[0];
name[0] = i; a1[0] = h; a2[0] = l;
}
} else if (a1[1] <= h) {
if (a1[1] == h) {
if (a2[1] < l) {
name[1] = i;
a2[1] = l;
}
} else {
name[3] = name[2]; a1[3] = a1[2]; a2[3] = a2[2];
name[2] = name[1]; a1[2] = a1[1]; a2[2] = a2[1];
name[1] = i; a1[1] = h; a2[1] = l;
}
} else if (a1[2] <= h) {
if (a1[2] == h) {
if (a2[2] < l) {
name[2] = i;
a2[2] = l;
}
} else {
name[3] = name[2]; a1[3] = a1[2]; a2[3] = a2[2];
name[2] = i; a1[2] = h; a2[2] = l;
}
} else if (a1[3] <= h) {
if (a1[3] == h) {
if (a2[3] < l) {
name[3] = i;
a2[3] = l;
}
} else {
name[3] = i; a1[3] = h; a2[3] = l;
}
}
}
end = rdtsc();
for (int i = 0; i < 4; i++) {
printf("No.%d : %d %d\n", i, name[i], a2[i]);
}
printf("clock : %ulld\n", end-start);
}
Raw
collatz.v
module COLLATZ (clk, r1, r2, r3, r4, l1, l2, l3, l4, fin);
input clk;
output reg [9:0] r1, r2, r3, r4;
output reg [7:0] l1, l2, l3, l4;
output reg fin;
reg [25:0] hilen [512:1023];
reg [25:0] posi [512:1023];
reg [9:0] index [0:4*512-1];
reg [1023:512] flag;
reg [1023:512] dead;
reg [12:0] i;
reg [9:0] mode;
always @(posedge clk) begin
if (mode == 0) begin
if (flag != 0) begin
for (i = 512; i < 1024; i=i+1) begin
if (posi[i] != 1) begin
if (i != posi[i] && 512 <= posi[i] && posi[i] < 1024) be
dead[posi[i]] <= 1;
end
if (posi[i] % 4 == 0) begin
if (512 <= posi[i]/2 && posi[i]/2 < 1024) begin
dead[posi[i]/2] <= 1;
end
posi[i] <= posi[i] / 4;
hilen[i] <= hilen[i]+2;
end
else if (posi[i] % 4 == 2) begin
if (posi[i] == 2) begin
posi[i] <= 1;
hilen[i] <= hilen[i]+1;
end
else begin
if (512 <= posi[i]/2 && posi[i]/2 < 1024) begin
dead[posi[i]/2] <= 1;
end
if (512 <= (posi[i]/2)*3+1 && (posi[i]/2)*3+1 <
dead[(posi[i]/2)*3+1] <= 1;
end
posi[i] <= ((posi[i]/2)*3+1)/2;
if ((hilen[i]>>8) < (posi[i]/2)*3 + 1) hilen[i]
else hilen[i] <= hilen[i]+3;
end
end
else if (posi[i] % 4 == 3) begin
posi[i] <= (((posi[i] * 3 + 1)/2)*3+1)/2;
if (512 <= posi[i]*3+1 && posi[i]*3+1 < 1024) begin
dead[posi[i]*3+1] <= 1;
end
if (512 <= (posi[i]*3+1)/2 && (posi[i]*3+1)/2 < 1024
dead[(posi[i]*3+1)/2] <= 1;
end
if (512 <= ((posi[i]*3+1)/2)*3+1 && ((posi[i]*3+1)/2
dead[((posi[i]*3+1)/2)*3+1] <= 1;
end
if ((hilen[i]>>8) < ((posi[i]*3+1)/2)*3+1) hilen[i]
else hilen[i] <= hilen[i]+4;
end
else begin
posi[i] <= (posi[i] * 3 + 1)/4;
if (512 <= posi[i]*3+1 && posi[i]*3+1 < 1024) begin
dead[posi[i]*3+1] <= 1;
end
if (512 <= (posi[i]*3+1)/2 && (posi[i]*3+1)/2 < 1024
dead[(posi[i]*3+1)/2] <= 1;
end
if ((hilen[i]>>8) < posi[i]*3 + 1) hilen[i] <= ((pos
else hilen[i] <= hilen[i]+3;
end
end
else flag[i] <= 0;
end
end
else begin
mode <= 1;
for (i = 512; i < 1024; i=i+1) begin
if (dead[i] == 1) begin
hilen[i] <= 0;
end
end
end
end
else if (fin == 0) begin
if (mode != 512) begin
for (i = 0; i < 512; i=i+mode*2) begin
if (hilen[index[i*4]] >= hilen[index[(i+mode)*4]]) begin
if (hilen[index[i*4+1]] >= hilen[index[(i+mode)*4]]) beg
if (hilen[index[i*4+2]] >= hilen[index[(i+mode)*4]])
if (hilen[index[i*4+3]] < hilen[index[(i+mode)*4
index[i*4+3] <= index[(i+mode)*4];
end
end
else begin
if (hilen[index[i*4+2]] >= hilen[index[(i+mode)*
index[i*4+3] <= index[i*4+2];
end
else begin
index[i*4+3] <= index[(i+mode)*4+1];
end
index[i*4+2] <= index[(i+mode)*4];
end
end
else begin
if (hilen[index[i*4+1]] >= hilen[index[(i+mode)*4+1]
if (hilen[index[i*4+2]] >= hilen[index[(i+mode)*
index[i*4+3] <= index[i*4+2];
end
else begin
index[i*4+3] <= index[(i+mode)*4+1];
end
index[i*4+2] <= index[i*4+1];
end
else begin
if (hilen[index[i*4+1]] >= hilen[index[(i+mode)*
index[i*4+3] <= index[i*4+1];
end
else begin
index[i*4+3] <= index[(i+mode)*4+2];
end
index[i*4+2] <= index[(i+mode)*4+1];
end
index[i*4+1] <= index[(i+mode)*4];
end
end
else begin
if (hilen[index[i*4]] >= hilen[index[(i+mode)*4+1]]) beg
if (hilen[index[i*4+1]] >= hilen[index[(i+mode)*4+1]
if (hilen[index[i*4+2]] >= hilen[index[(i+mode)*
index[i*4+3] <= index[i*4+2];
end
else begin
index[i*4+3] <= index[(i+mode)*4+1];
end
index[i*4+2] <= index[i*4+1];
end
else begin
if (hilen[index[i*4+1]] >= hilen[index[(i+mode)*
index[i*4+3] <= index[i*4+1];
end
else begin
index[i*4+3] <= index[(i+mode)*4+2];
end
index[i*4+2] <= index[(i+mode)*4+1];
end
index[i*4+1] <= index[i*4];
end
else begin
if (hilen[index[i*4]] >= hilen[index[(i+mode)*4+2]])
if (hilen[index[i*4+1]] >= hilen[index[(i+mode)*
index[i*4+3] <= index[i*4+1];
end
else begin
index[i*4+3] <= index[(i+mode)*4+2];
end
index[i*4+2] <= index[i*4];
end
else begin
if (hilen[index[i*4]] >= hilen[index[(i+mode)*4+
index[i*4+3] <= index[i*4];
end
else begin
index[i*4+3] <= index[(i+mode)*4+3];
end
index[i*4+2] <= index[(i+mode)*4+2];
end
index[i*4+1] <= index[(i+mode)*4+1];
end
index[i*4] <= index[(i+mode)*4];
end
end
mode <= mode*2;
end
else begin
fin <= 1;
r1 <= index[0]; r2 <= index[1]; r3 <= index[2]; r4 <= index[3];
l1 <= (hilen[index[0]]&8'b11111111);
l2 <= (hilen[index[1]]&8'b11111111);
l3 <= (hilen[index[2]]&8'b11111111);
l4 <= (hilen[index[3]]&8'b11111111);
end
end
end
initial begin
mode <= 0;
fin <= 0;
dead <= 0;
for (i = 0; i < 4*512; i=i+1) begin
if ((i&3) == 0) index[i] <= 512+(i>>2);
else index[i] <= 512;
end
for (i = 512; i < 1024; i=i+1) begin
flag[i] <= 1;
posi[i] <= i;
hilen[i] <= {i, 8'b0};
end
end
endmodule
Raw
collatz2test.v
module COLLATZ2TEST;
reg clk;
reg [19:0] counter;
wire [9:0] r1, r2, r3, r4;
wire [7:0] l1, l2, l3, l4;
wire fin;
always #2 clk <= !clk;
always #4 if (fin == 0) counter <= counter+1;
COLLATZ hoge (clk, r1, r2, r3, r4, l1, l2, l3, l4, fin);
initial begin
$dumpfile("collatz2test.vcd");
$dumpvars(0,COLLATZ2TEST);
$monitor("hoge");
#1 clk <= 1; counter <= 0;
#1000
$monitor("r1=%d,r2=%d,r3=%d,r4=%d\nl1=%d,l2=%d,l3=%d,l4=%d,fin=%d,counter=%d", r1, r2, r3, r4, l1, l2, l3, l4, fin, counter);
$finish;
end
endmodule
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment