• Andrew Edwards (11/11) Mar 17 2004 Gentlemen,
• Russ Lewis (25/40) Mar 18 2004 My first thought is that you should add a cache of cycle lengths:
• Russ Lewis (9/57) Mar 18 2004 (At least) One thing I forgot: remember that you might have to extend

Andrew Edwards <remove_ridimz remove_yahoo.com> writes:

Gentlemen,


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.

Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:

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,
 

 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.

Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:

(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,


 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.