memoization should have worked

user_8791403 0
Viewed 60

without memoization this solution for Euler Project 14 works fine! Then with memoization it should work faster... but it stops nearly at i = 1818 or near. How strange! what's wrong trying hard to understand! can you help?

#include <stdio.h>

#define limit 1000000

int arr[limit];

int fun(long long int i) {
    long long int count = 1;
    long long int num;
    arr[limit];
    num = i;
    while (num > 1) {
        if (arr[num] != NULL) {
            count = count - 1 + arr[num];
            break;
        }
        if (num % 2 == 0) {
            num = num / 2;
            count++;
        } else {
            num = 3 * num + 1;
            count++;
        }
    }
    arr[i] = count;
    return count;
}

int main() {
    long long int i;
    for (i = 2; i < limit; i++) {
        long long int count = fun(i);
        printf("d %lld c: %lld\n", i, count);
    }
    return 0;
}
memoization computer-science dynamic c algorithm
1 Answers

OK, I think the main problem with your code is that the Collatz sequence can give you numbers that are much higher than the one you started with before descending to 1. According to Project Euler 14, you're supposed to find the starting number below 1000000 that produces the longest chain before reaching zero. But the Collatz sequence starting at 1819 includes numbers that are larger than one million. As a result, you're attempting to access elements of arr[] that are way out of bounds.

Also, as pointed out in the comments, the statement arr[limit]; in your fun() function does nothing useful. If you had enabled warnings in your compiler, it probably would have flagged this, as well as the statement if(arr[num]!=NULL), which compares a void* pointer with an integer.

If you replace the first statement of your while() block with if (num < limit && arr[num]!=NULL), then you should at least avoid the segmentation fault.

Your main() function needs to be rewritten to find the starting number that produces the longest chain, instead of just printing out a million lines of data.

If you like, you could try running this instead:

#include <stdio.h>

#define LIMIT 1000000

int arr[LIMIT] = { 0 };

long fun(long i) {
    long count = 1;
    long num;
    num = i;
    while (num > 1) {
        if (num < LIMIT && arr[num] != 0) {
            count = count - 1 + arr[num];
            break;
        }
        if (num % 2 == 0) {
            num = num / 2;
            count++;
        }
        else {
            num = 3 * num + 1;
            count++;
        }
    }
    arr[i] = count;
    return count;
}

int main(){
    long i, longest=0, maxstart;
    for (i=2; i<LIMIT; i++) {
        long count = fun(i);
        if (count > longest) {
            longest = count;
            maxstart = i;
        }
    }
    printf("%ld\n",maxstart);
    return 0;
}
user_16798490
Related