C++ Collatz Conjecture

Inori · 08-14-2016, 03:11 AM

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.3597

Fun 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.

C++ Collatz Conjecture
Author Message