www.digitalmars.com         C & C++   DMDScript  

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

reply Andrew Edwards <remove_ridimz remove_yahoo.com> writes:
------------PDk3KPQAeCCsN01YlJSSfK
Content-Type: text/plain; format=flowed; charset=iso-8859-15
Content-Transfer-Encoding: 8bit

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.
------------PDk3KPQAeCCsN01YlJSSfK
Content-Disposition: attachment; filename=data.in
Content-Type: application/octet-stream; name=data.in
Content-Transfer-Encoding: 8bit

1 10
100 200
201 210
900 1000

------------PDk3KPQAeCCsN01YlJSSfK
Content-Disposition: attachment; filename=maxcycle.d
Content-Type: application/octet-stream; name=maxcycle.d
Content-Transfer-Encoding: 8bit

// (c) Andrew C Edwards (20040318)

// ACM problem set #100: The 3n + 1 problem
//   http://acm.uva.es/p/v1/100.html
// This program determines the maximum cycle-length for all numbers over
// the interval [i,j] and outputs the result in the format [i j max]

import std.stream;

int main(char[][] args)
{
  // Open file
  File file = new File("data.in");

  // get starting and ending points
  int i = 0;  // starting point
  int j = 0;  // ending point

  // invariant:
  //   end of file not reached
  while(file) {
    file.scanf("%d%d",&i,&j);
    stdout.printf("%d\t%d\t%d\n",i,j,getMaxCycleLength(i,j));
  }
  return 0;
}

// Determine max cycle-length for interval
int getMaxCycleLength(int i, int j)
{
  int maxCycleLength;
  int value;

  // invariant:
  //   checking cycle-length of iter
  for(int iter = i; iter <= j; iter++) {
    value = getCycleLength(iter);
    if( value > maxCycleLength)  // Am I the longest?
      maxCycleLength = value;
  }
  return maxCycleLength;
}

// Determine cycle-length of a number n
int getCycleLength(int n)
{
  int cycleLength = 1;

  while (n != 1) {
    if (n % 2 == 0)  // even
      n /= 2;
    else
      n = n * 3 + 1; // odd
    ++cycleLength;
  }
  return cycleLength;
}

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