cycle_length.cc

#include <stdio.h>
#include <time.h>

typedef unsigned int uint32; 
typedef long long int64;

template<typename F, typename V>
V collision_point(const F& f, V x) {
    V slow = x;
    V fast = f(x);
    
    while (slow != fast) {
        slow = f(slow);
        fast = f(f(fast));
    }
    
    return slow;
}

template<typename F, typename V>
int64 distance(F f, V x, V y) {
    int64 result = 0;
    
    while (x != y) {
        ++result;
        x = f(x);
    }
    
    return result;
}

template<typename F, typename V>
int64 cycle_length(const F& f, V x) {
    return distance(f, f(x), x) + 1;
}

struct LCG {
    uint32 a_;
    uint32 c_;
    
    LCG(uint32 a, uint32 c) : a_(a), c_(c) { }
    
    uint32 operator()(uint32 x) const {
        return x * a_ + c_;
    }  
};

int main(int argc, char** argv) {
    LCG lcg(1664525, 1013904223);

    time_t t1 = time(NULL);
    uint32 cp = collision_point(lcg, 7);
    time_t t2 = time(NULL);
    
    printf("Collision Point: %d (%d sec)\n", cp, (t2 -t1));
    
    t1 = time(NULL);
    int64 cl = cycle_length(lcg, cp);
    t2 = time(NULL);
    
    printf("Cycle lentgh: %lld (%d sec)\n", cl, (t2 - t1));
    
    return 0;
}

gistfile2.txt

$ g++ -O3 -o collision collision.cc && time ./collision 
Collision Point: 502824264 (9 sec)
Cycle length: 4294967296 (9 sec)
./collision  14.65s user 0.15s system 82% cpu 18.001 total