Gentlemen,

The attachment contains my solution to ACM problem set #100.
I have two questions...
How do I calculate the execution time?
How do I prevent the resulting buffer overrun error?

If you have any suggestions on how to improve upon the implementation (*speed* and design) I would appreciate them.

Thanks,
Andrew

P.S. I am just trying to sharpen my skills. Please don't hold back on your criticism.

My first thought is that you should add a cache of cycle lengths:

uint[] cache;
	/* cycle length for n is at cache[n-1] */

/* in main */
	cache.length = 10000;
	cache[] = 0;	/* initializes all entries */
	cache[1-1] = 1;	/* a few quick & easy values */
	cache[2-1] = 2;
	cache[4-1] = 3;
	cache[8-1] = 4;
	cache[16-1] = 5;

/* new getCycleLength, recursive, caching */
int getCycleLength(int n) {
	if(n > cache.length) {
		uint oldLen = cache.length;
		cache.length = oldLen*2;
		cache[oldLen .. oldLen*2] = 0;	/* initialize */
	} else if(cache[n-1] != 0)
		return cache[n-1];

	if(n % 2 == 0)
		return cache[n-1] = 1+getCycleLength(n/2);
	else
		return cache[n-1] = 1+getCycleLength(3*n+1);
}

Andrew Edwards wrote:
> Gentlemen,
> 
> The attachment contains my solution to ACM problem set #100.
> I have two questions...
> How do I calculate the execution time?
> How do I prevent the resulting buffer overrun error?
> 
> If you have any suggestions on how to improve upon the
> implementation (*speed* and design) I would appreciate them.
> 
> Thanks,
> Andrew
> 
> P.S. I am just trying to sharpen my skills. Please don't hold
> back on your criticism.

(At least) One thing I forgot: remember that you might have to extend the cache multiple times, if the number you're looking for is far far larger than the current size of the cache.

Caching will consume a lot of memory, especially if you start with a large number.  But it should vastly accelerate your program if you are working with large datasets.  (You could even decide to save your cache to disk and load it as needed.  Try mmap'ing a region, rather than using D's built-in arrays.)

Russ Lewis wrote:
> My first thought is that you should add a cache of cycle lengths:
> 
> uint[] cache;
>     /* cycle length for n is at cache[n-1] */
> 
> /* in main */
>     cache.length = 10000;
>     cache[] = 0;    /* initializes all entries */
>     cache[1-1] = 1;    /* a few quick & easy values */
>     cache[2-1] = 2;
>     cache[4-1] = 3;
>     cache[8-1] = 4;
>     cache[16-1] = 5;
> 
> /* new getCycleLength, recursive, caching */
> int getCycleLength(int n) {
>     if(n > cache.length) {
>         uint oldLen = cache.length;
>         cache.length = oldLen*2;
>         cache[oldLen .. oldLen*2] = 0;    /* initialize */
>     } else if(cache[n-1] != 0)
>         return cache[n-1];
> 
>     if(n % 2 == 0)
>         return cache[n-1] = 1+getCycleLength(n/2);
>     else
>         return cache[n-1] = 1+getCycleLength(3*n+1);
> }
> 
> Andrew Edwards wrote:
> 
>> Gentlemen,
>>
>> The attachment contains my solution to ACM problem set #100.
>> I have two questions...
>> How do I calculate the execution time?
>> How do I prevent the resulting buffer overrun error?
>>
>> If you have any suggestions on how to improve upon the
>> implementation (*speed* and design) I would appreciate them.
>>
>> Thanks,
>> Andrew
>>
>> P.S. I am just trying to sharpen my skills. Please don't hold
>> back on your criticism.
> 
>