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

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

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