Puissance de 2, essayant d'atteindre 2^1000, erreur de segmentation

Question

Je suis en train de construire un programme qui va multiplier par 2, et atteindre de longs nombres précis. Ici, je construis un programme dans lequel chaque chiffre est stocké dans une variable différente. Lorsque je compile le programme, et je tape 2^63, il me donne la bonne réponse. Mais quand je tape 2^64, j'obtiens un "défaut de segmentation".

Qu'est-ce que c'est? Que puis-je faire?

#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

Je pense que votre problème est

int num[array]; 

Ceci est un tableau statique, une fois que sa taille est déclarée taille de 1 (tableau = 1 seulement quelques lignes ci-dessus) des thats alors la taille du tableau.

Les bibliothèques de grands nombres sont très compliquées et il vaut mieux les laisser à une bibliothèque tierce.

Essayez de jeter un oeil à GMP

Si vous devez le faire vous-même, essayez d'utiliser une classe de tableau dynamique comme std :: vecteur

Answer 2

C'est parce que pour stocker 2^n vous avez besoin d'un type de n bits - qui est généralement disponible pour n < 64, mais pas pour un plus grand nombre que cela.

Ce dont vous aurez besoin est une librairie de grand nombre entier à usage général.

Answer 3

Même si votre solution est en langage C, vous pouvez utiliser d'autres langages pour résoudre les problèmes liés au projet. Euler est indépendant de la langue. J'utilise C pour beaucoup de problèmes et quand il s'agit de gros problèmes entiers, j'ai tendance à utiliser python car il traite bien les opérations/manipulations/calculs de grand nombre.

Modifier
spécifié le code exemple dans la question C plutôt que C++.

Answer 4

num ne peut contenir 1 entier. Vous étiez chanceux que int num[1] était sur une page (?) Qui a fourni l'espace pour 64 entiers (256 octets), avant que l'accès à num[64] ait provoqué l'erreur de segmentation.

Vous pouvez utiliser un int* et réaffecter les fonds au besoin de stocker de nouveaux morceaux ...

Answer 5

D'autres personnes ont plus ou moins répondu à la question, alors je vais faire quelque chose d'un peu différent: I Je vais coller ici une révision complète de votre programme. J'ai corrigé le bug que vous posiez, mais j'ai aussi fait beaucoup d'autres changements. Je veux que vous lisiez le programme révisé attentivement et pensez à pourquoi j'ai changé certaines choses.

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