|
DJCollatz
Provides overview of the problem, and the proposed solution.
IntroductionThe Collatz conjecture is as follows: Given a series, a(n) = a(n-1)/2 ; when a(n-1) is even 3a(n-1) + 1 ; when a(n-1) is odd converges to '1' for all positive a(n). The problem 3n+1 solved here is to compute the maximum cycle length (the # of oscillations before a(n) converges to 1) given a range of numbers. DetailsSolution ApproachWe herein have used a cache, which stores the cycle length of each number (within the range) provided it is below a certain MAX_SIZE. const int MAX_SIZE = 250000; //defines the cache size
int cache[MAX_SIZE] = {0}; //constructs cache as array of MAX_SIZE
//initializes all elements to 0The cycle length is then calculated recursively by calling cycleLength(k). If the cycle length of 'k' is already computed and stored in the cache, it is returned to the calling function; else the cache is populated with the cycle length of the new 'k' at the corresponding index 'k-1.' /**
* computes cycle length
* We have assumed that no operation will result into an overflow of 32-bit int.
* NOTE: using 'long long int' will compile without '-pedantic'
* and will cover the range of all the cyclelengths for 1-999999
* @param int k which is the previously computed series value
* @return int cycleLength for a given k > 0; else assertion fails
*/
int cycleLength( int k )
{
int cyclen;
/* if k <= MAX_SIZE and cache already contains cycle length for k */
if ( ( k <= MAX_SIZE ) && cache[k - 1] != 0 )
{
return cache[k-1];
}
else
{
if ( k == 1 )
{
cyclen = 1;
}
else
if ( (k % 2) == 0 )
{
cyclen = cycleLength(k/2) + 1; //recursive call
}
else
{
cyclen = cycleLength(3 * k + 1) + 1;
}
if ( k <= MAX_SIZE )
cache[k - 1] = cyclen; //populate cache
return cyclen;
}
}Different Alternatives ConsideredPreliminary ApproachThe basic idea is to build a simple 'for loop' and calculate the cycle length of each number in the range given as the input. Pros: Simple algorithm Cons: Time inefficient Eager CachingUsing a cache to store the powers of 2 upto 2^32, and using the (index + 1) as the cycle length. Expected pros: Time efficient Actual cons : Quite contrary -- UVa prompted "Time Exceeded" Consequently, even being eager, we had to resort to the lazy caching approach described above!
|