+- Sinisterly (https://sinister.ly)
+-- Forum: Coding (https://sinister.ly/Forum-Coding)
+--- Forum: C, C++, & Obj-C (https://sinister.ly/Forum-C-C-Obj-C)
+--- Thread: C++ Collatz Conjecture (/Thread-C-Collatz-Conjecture)
C++ Collatz Conjecture - Inori - 08-14-2016
I was watching a bunch of numberphile videos, which gave me the idea to make a ridiculously optimized program that finds out how many iterations are needed to complete the collatz conjecture for any given number. I originally made it with Python, but wasn't satisfied with the speeds I was getting (~373 ms for 1-100), so I went ahead and ported it to C++. Originally, I used uint, but as I tested it with higher values, I found that that wouldn't cut it, so I'm now running with monster unsigned long long integers, which are guaranteed to be >64 bits.
Source:
Code:
#include <tgmath.h>
#include <stdio.h>
#include <map>
#define STEPS 100ull
std::map<int,int> mem;
unsigned long long start,tmpN;
double logN;
int b,c;
int collatz(unsigned long long n){
start=n;
c=0;
while(n>1ull){
tmpN=n;
if(n&1ull){
n=(n*3ull)+1ull;
c++;
}else{
logN=log2(n);
if(floor(logN)==logN){
c+=(int)logN;
break;
}
}
n=n/2ull;
c++;
if(mem.find(n)!=mem.end()){
b=mem[n];
mem[tmpN]=b+1;
c+=b;
break;
}
}
mem[start]=c;
return c;
};
int main(){
mem=std::map<int,int>();
printf("sep=,\nnumber,iterations\n");
for(unsigned long long i=1ull;i<=STEPS;i++){
// I was getting weird results with only one printf
printf("%i",i);
printf(",%i\n",collatz(i));
}
return 0;
}Powershell Measure-Command benchmark:
Code:
> Measure-Command {".\collatz.exe"}
...
Ticks : 53597
TotalSeconds : 0.0053597
TotalMilliseconds : 5.3597Fun fact: while torture testing the program (and I guess my laptop as well), I found that the number under 100,000,000 that requires the most steps to complete the conjecture is 63,728,127 with 949 iterations.