www.digitalmars.com         C & C++   DMDScript  

D - [Request suggestons for improvement] 3n + 1 Problem

reply Andrew Edwards <remove_ridimz remove_yahoo.com> writes:
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.
Mar 17 2004
parent reply 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,
 
 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.
Mar 18 2004
parent 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,

 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.
Mar 18 2004