Power of 2, trying to reach 2^1000, Segmentation fault.

Question

I am building a program which will multiply by 2, and reach long accurate numbers. Here I build a program in which each digit is stored in a different variable. When I compile the program, and I type 2^63, It gives me the correct answer. But when I type 2^64, I get a “Segmentation fault”.

What is it? What can I do?

#include <stdio.h>
int main(void)
{
  printf("2^n, enter n: ");
  int n, array = 1;

  scanf("%d", &n);
  int num[array];

  num[0] = 2;
  int remainder = 0;
  if (n > 1) {
    int counter = 0;
    int counter3 = 1;

    for (counter3 = 1; counter3 < n; counter3++) {
      remainder = 0;

      for (counter = 0; counter < array; counter++) {
        num[counter] *= 2;
        num[counter] += remainder;
        remainder = 0;

        if (num[counter] / 10 != 0) {
          remainder = num[counter] / 10;
          num[counter] -= remainder * 10;
          if (counter+1 >= array) {
            array++;
            num[counter+1] = remainder;
            remainder = 0;
            break;
          }
        }
      }
    }
  }

  int counter2;
  for (counter2 = array - 1; counter2 >= 0; counter2--)
    printf("%d", num[counter2]);

  putchar('\n');
  return 0;
}

Answer 1

Thats because to store 2^n you need an n bit type - which is generally available for n < 64, but not for numbers higher than this.

What you'll need is a general purpose 3rd party large integer library.

Answer 2

Even though your solution is in C you can use other languages to work problems considering project euler is language agnostic. I use C for a lot of the problems and when it comes to large integer problems I tend to use python because it deals well with large number operations/manipulation/calculations.

Edit
Specified the example code in the question as C rather than C++.

Answer 3

I think your problem is

int num[array];

This is a static array, once its size is declared to be size of 1 (array=1 only a few lines above) then thats the size of the array.

Big number libraries are very complicated and best left up to a 3rd party library.

Try taking a look at GMP

If you must do it yourself, try using a dynamic array class like std::vector

Answer 4

num can only contain 1 integer. You were lucky that int num[1] was on a page (?) which provided space for 64 integers (256 bytes), before the access to num[64] caused the segmentation fault.

You could use a int* and reallocate it as necessary to store new bits...

Answer 5

Other people have more-or-less answered the question, so I'm going to do something a little different: I'm going to paste here a complete revision of your program. I fixed the bug you were asking about, but I also made a whole lot of other changes. I want you to read the revised program carefully and think about why I changed certain things.

// Note: This program uses C99 features; must be compiled with e.g.
// -std=c99 (for GCC).  Nonetheless it is C, not C++.

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

static void
printdigits(const int num[], int top)
{
  for (int i = top - 1; i >= 0; i--) {
    assert(0 <= num[i] && num[i] < 10);
    putchar('0' + num[i]);
  }
  putchar('\n');
}

int
main(int argc, char **argv)
{
  if (argc != 2) {
    fprintf(stderr, "usage: %s n\ncomputes 2^n\n", argv[0]);
    return 1;
  }

  char *eptr;
  long n = strtol(argv[1], &eptr, 10);
  if (eptr == argv[1] || *eptr != '\0') {
    fprintf(stderr, "%s: '%s' is not a number\n", argv[0], argv[1]);
    return 1;
  }

  if (n < 1) {
    fputs("n must be at least 1\n", stderr);
    return 1;
  }

  unsigned int num[n]; // could be short or even char, but memory is not tight
  int top = 1;
  num[0] = 2;

  for (int i = 1; i < n; i++) {
    int carry = 0;
    for (int j = 0; j < top; j++) {
      num[j] = num[j] * 2 + carry;
      carry = 0;

      if (num[j] >= 10) {
        assert(num[j] < 20); // largest possible is 2*9+1 = 19
        carry = 1;
        num[j] -= 10;

        if (j+1 >= top) {
          assert(top < n);
          num[j+1] = carry;
          top++;
          break;
        }
      }
    }

#ifndef NDEBUG
    printf("Iteration %d: top=%d num=", i, top);
    printdigits(num, top);
#endif
  }

#ifndef NDEBUG
  putchar('\n');
#endif
  printdigits(num, top);
  return 0;
}