I reduced the time of the algorithm by ~36% by reducing the algorithm and improving the Cache. Tested for N=500,000,000
.
First lets look at the properties of the Collatz sequence
1) If the number is even, then we will perform a right-shift until the value is odd.
2) If the number is odd, then it will take one iteration of n=3*n+1
to become even.
Proof
Let's rewrite our equation n = 3*n + 1
= (2*n) + (n+1)
= (n<<1) + (n+1)
.
The first term (n<<1)
is guaranteed to be even, because a left shift will pad a 0 to the lsb.
The second term (n+1)
is guaranteed to be even, because an odd number plus one is even.
The sum of two even terms is even.
As a result, n = 3*n + 1
is guaranteed to create an even n (when n is odd).
3) n = 3*n+1
for odd n will never be 1
.
Proof
See #2. Result must be even.
Now let's rewrite our Collatz sequence
// if even, right shift until odd
while ((n & 1) == 0) {
n >>= 1;
++len;
}
while ( n != 1 ) {
// odd (guaranteed)
n = 3*n + 1;
// even (guaranteed)
n >>= 1;
// if even, right shift until odd
while ((n & 1) == 0) {
n >>= 1;
++len;
}
// account for 2 guaranteed steps (see above)
len += 2;
}
Now let's improve the Cache
From our properties (see above), we notice that the Collatz sequence will frequently alternate between positive and negative numbers. The maximum number of odd numbers that can be seen before seeing an even number is one. The maximum number of even numbers that can be seen before seeing an odd number depends on N, but it is relatively small due to right shifting (max 31 for an unsigned int). For this reason, I have decided to only store odd numbers in the Cache, which will reduce our Cache to half the size.
Additionally, I have decided to store values in the cache as I encounter them--rather than set only the initial values at the end of each sequence. In order to achieve this, we will need to store the values in a preliminary buffer, and then, at the end of the Collatz sequence, add them to the cache and calculate the length by taking the difference between the length that we first encountered the number, and the final length of the sequence.
Since we are storing the values we encounter rather than the initial values. We can now improve our algorithm by starting at N/2 as you mentioned, because we will still cache values for the range [2, N/2).
Here is the resulting function
void collatz(unsigned N, unsigned& r_index, unsigned& r_length) {
unsigned *cache, n0, len, i=0, lenMax=0;
unsigned long long n;
// cache size
const unsigned cacheMaxN = N;
const unsigned cacheSize = (cacheMaxN/2) + 1; // store all odd from (1,cacheMaxN) exclusive
// cache
cache = new unsigned[cacheSize];
memset(cache, 0, cacheSize*sizeof(unsigned));
// cache buffer (for temporarily holding cache values)
struct CacheObject {
unsigned n;
unsigned n0_to_n_len;
};
std::vector<CacheObject> buffer;
buffer.reserve(128);
CacheObject cObj;
for (n0 = N/2; n0 < N; ++n0 ) {
// initial
n = n0;
len = 0;
// collatz
// if even, right shift until odd
while ((n & 1) == 0) {
n >>= 1;
++len;
}
while ( n != 1 ) {
// odd (guaranteed), check cache
if ( n < cacheMaxN ) {
if ( cache[ n>>1 ] ) {
// use cache value
len += cache[ n>>1 ];
break;
} else {
// store cache value
// store to cache as difference between current length and final length
// needs to resolve final length first, so store in queue
cObj.n = n;
cObj.n0_to_n_len = len;
buffer.push_back( cObj );
}
}
// odd (guaranteed)
n = 3*n + 1;
// even (guaranteed)
n >>= 1;
// if even, right shift until odd
while ((n & 1) == 0) {
n >>= 1;
++len;
}
// account for 2 guaranteed steps (see above)
len += 2;
}
// buffer to cache
if ( buffer.size() != 0 ) {
for (CacheObject o : buffer) {
cache[ o.n>>1 ] = len - o.n0_to_n_len;
}
buffer.clear();
}
// set max len
if ( len > lenMax ) {
lenMax = len;
i = n0;
}
}
r_index = i;
r_length = lenMax;
delete [] cache;
}