collatz.c [optimization patch]

// Optimized version of http://pastebin.com/8EiQw3mB
// Whereas the previous version took almost 10 minutes to finish 1 billion collatz paths, this one takes 11 *seconds*.
// These optimizations were way more effective than I had anticipated.

// Edit: this whole program is meaningless.

#include <stdio.h>

typedef unsigned long ul;

int
power_2(ul n)
{
    int i;
    ul temp;

    for(i = 0; i < 64; i++){
        temp = 1 << i;

        if(n & temp) // wait a minute. This will return true with all n > 0. Changing '&' to '==' makes it slow again. I fucked up.
            return 1;
    }

    return 0;
}

void
collatz(ul n)
{
    static ul largest;
    ul n_cpy = n;

    while(n > 1){
        if(power_2(n) || n == largest)
            break;

        if(!(n % 2))
            n /= 2;
        else
            n = (n * 3 + 1) / 2;
    }

    largest = n_cpy;
}

void
do_collatz(ul n)
{
    ul i;

    for(i = 1; i < n; i++){
        if(i % 1000000 == 1)
            printf("collatz(%lu million)\n", i / 1000000);

        collatz(i);
    }
}

int
main()
{
    do_collatz(1000000000);
}