0

Memory seems to run out when I run the executable from within the Visual Studio Code terminal, and then my computer freezes.

But all is fine when I run it from gnome terminal, and I get the desired outputs.

I'm not yet knowledgeable about c or the gmp.h library. I wouldn't be surprised if there is a bug somewhere, or something I am missing, even if the code I've posted does give me correct results when not run from VSCode.

Btw it does take about 1m43s to run, with N 666666, on my pc.

// problem from: https://www.reddit.com/r/dailyprogrammer/comments/jfcuz5/20201021_challenge_386_intermediate_partition/
#include "gmp.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define N 666666

mpz_t results[N + 1];

void segment(int n)
{
    if (n <= 1)
        return;
    if (mpz_cmp_ui(results[n - 1], 0) > 0)
        return;

    mpz_t result;
    mpz_t diff;
    mpz_init(result);
    mpz_init(diff);
    int i = 0;
    int seq = 1;
    int is_positive;

    while (n - seq >= 0)
    {
        segment(n - seq);
        is_positive = 1 - 2 * (i / 2 % 2);
        mpz_mul_si(diff, results[n - seq - 1], is_positive);
        mpz_add(result, result, diff);
        seq += (i % 2 > 0) ? i + 2 : (i + 2) / 2;
        i += 1;
        mpz_set_ui(diff, 0);
    }

    mpz_add_ui(results[n - 1], result, 0);
    mpz_clear(result);
    mpz_clear(diff);
    return;
}

int main(void)
{
    for (int i; i < N; i++)
    {
        mpz_init(results[i]);
    }
    mpz_set_ui(results[0], 1);
    mpz_set_ui(results[1], 1);

    for (int i; i <= N + 1; i++)
    {
        segment(i);
    }

    gmp_printf("Result: %Zd\n", results[N]);

    for (int i; i < N; i++)
    {
        mpz_clear(results[i]);
    }
}
  • 1
    Nobody can tell you for certain unless you show your code. It's likely a bug in your program that results in Undefined Behaviour (.e.g buffer overrun, memory corruption, memory leaks, using unintialised variables, etc). The nature of UB is that it can behave in unpredictable ways under different conditions. – kaylum Feb 08 '21 at 21:22
  • Hold on, I'll post it. Thought there might be I was missing about VSCode. –  Feb 08 '21 at 21:23
  • If you're about to post code that crashes, it's a good idea to use a debugger to see which line it crashes on. – klutt Feb 08 '21 at 21:28
  • I just posted the code. it gives me correct results when I run it from gnome terminal. –  Feb 08 '21 at 21:34
  • 2
    All the `for` loops are wrong. `for (int i; i <= N + 1; i++)` is undefined behaviour as `i` is uninitialized. Should be `for (int i=0; i <= N + 1; i++)`. Also, `N+1` will cause `result[i-1]` to access out of bounds memory. – kaylum Feb 08 '21 at 22:03
  • @kaylum, thanks I have made changes and am testing it now. note that (rather confusingly) segment(n) accesses 'n-1' of the array, meaning segment(N+1) only accesses array[N], which is fine, since len(array)=N+1. this does seem like bad style. –  Feb 09 '21 at 13:52
  • The uncorrected code doesn't seem to cause a crash any more, even if the `i`s aren't initialised. oh well, i'll assume there was a worse bug in a previous version. –  Feb 09 '21 at 14:06
  • 1
    *even if the `i` is aren't initialised. oh well*. No, no, no! Do not have that attitude. It must be fixed and not left like that even if it appears to "work". Using an unintiaialised variable is Undefined Behaviour. Which means it can fail at any time. You should understand that as you have already observed that very thing happening. [Undefined, unspecified and implementation-defined behavior](https://stackoverflow.com/questions/2397984/undefined-unspecified-and-implementation-defined-behavior) – kaylum Feb 09 '21 at 20:03
  • @kaylum, thank you for that link. I did fix the code! I just meant "oh well, I'm giving up on finding the cause of the crash", since it wasn't caused by the uninitialized index values, and I didn't keep track of versions. I am going to assume that there were more bugs before. –  Feb 09 '21 at 20:42

1 Answers1

1

The code has undefined behavior because the for loops do not initialize the i loop index: for (int i; i < N; i++) Furthemore, the array has N + 1 elements, so the initialization loop should run one step farther and the segment loop one less.

Modify the main() function to:

int main() {
    for (int i = 0; i < N + 1; i++) {
        mpz_init(results[i]);
    }
    mpz_set_ui(results[0], 1);
    mpz_set_ui(results[1], 1);

    for (int i = 0; i < N + 1; i++) {
        segment(i);
    }

    gmp_printf("Result: %Zd\n", results[N]);

    for (int i = 0; i < N + 1; i++) {
        mpz_clear(results[i]);
    }
    return 0;
}
chqrlie
  • 131,814
  • 10
  • 121
  • 189
  • Note, that segment(i) can run to N+1, since it accesses i-1 of the array. apart from that, thanks for pointing out the index errors. –  Feb 09 '21 at 14:07