Степень 2, пытается достичь 2 ^ 1000, ошибка сегментации

Question

Я строю программу, которая умножится на 2 и достигнет длинных точных чисел.Здесь я строю программу, в которой каждая цифра хранится в другой переменной.Когда я компилирую программу и набираю 2 ^ 63, она дает мне правильный ответ.Но когда я набираю 2 ^ 64, я получаю «Ошибка сегментации».

Что это?Что я могу сделать?

#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

Я думаю, что ваша проблема

int num[array];

Это статический массив, если его размер объявлен равным 1 (массив = 1 только несколькими строками выше), то это размер массива.

Библиотеки больших чисел очень сложны и лучше оставить их сторонней библиотеке.

Попробуйте взглянуть на GMP

Если вам необходимосделайте это сами, попробуйте использовать класс динамического массива, такой как std :: vector

Answer 2

num может содержать только 1 целое число. Вам повезло, что int num[1] находился на странице (?), Которая предоставляла место для 64 целых чисел (256 байт), прежде чем доступ к num[64] вызвал ошибку сегментации.

Вы можете использовать int* и перераспределить его при необходимости для хранения новых битов ...

Answer 3

Это потому, что для хранения 2 ^ n вам нужен тип n битов - который обычно доступен для n <64, но не для чисел, превышающих это.партия больших целочисленных библиотек. </p>

Answer 4

Другие люди более или менее ответили на вопрос, поэтому я собираюсь сделать что-то немного другое: я собираюсь вставить здесь полный пересмотр вашей программы. Я исправил ошибку, о которой вы спрашивали, но также внес много других изменений. Я хочу, чтобы вы внимательно прочитали пересмотренную программу и подумали о , почему я изменил некоторые вещи.

// 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;
}

Answer 5

Даже если ваше решение написано на C, вы можете использовать другие языки для решения проблем, поскольку проект euler не зависит от языка. Я использую C для многих проблем, а когда дело касается больших целочисленных задач, я склонен использовать python, потому что он хорошо справляется с большим количеством операций / манипуляций / вычислений.

Редактировать
Указан пример кода в вопросе как C, а не C ++.