Comment faire la somme d'un grand nombre?

Question

Je suis en train de calculer 1 + 1 * 2 + 1 * 2 * 3 + 1 * 2 * 3 * 4 + ... + 1 * 2 * ... * n où n est la saisie de l'utilisateur. Il travaille pour des valeurs de n jusqu'à 12. Je veux calculer la somme de n = 13, n = 14 et n = 15. Comment dois-je faire en C89? Comme je sais, je peux utiliser unsigned long long int seulement en C99 ou C11.

1. Entrée 13, résultat 2455009817, devrait 6749977113
2. Entrée 14, résultat 3733955097, devrait 93928268313
3. Entrée 15, résultat 1443297817, devrait 1401602636313

Mon code:

#include <stdio.h>
#include <stdlib.h>
int main()
{
    unsigned long int n;
    unsigned long int P = 1;
    int i;
    unsigned long int sum = 0;
    scanf("%lu", &n);
    for(i = 1; i <= n; i++)
    {
        P *= i;
        sum += P;
    }
    printf("%lu", sum);
    return 0;
}

Answer 1

Dans la pratique, vous voulez des précision arbitraire (un.k.un. bigint ou bignum) de la bibliothèque. Ma recommandation est GMPlib mais il y a les autres.

N'essayez pas de votre propre code de bignum de la bibliothèque. Efficace et algorithmes intelligents existent, mais ils sont peu intuitive et difficile à comprendre (vous pouvez trouver des livres entiers consacrés à cette question). En outre, les bibliothèques, comme GMPlib profitent de certaines instructions machine (par exemple, ADC -ajouter à transporter) qu'un compilateur C standard ne pas émettre (à partir de pur code C).

Si c'est un travail et vous n'êtes pas autorisé à utiliser le code externe, par exemple comme représentant un nombre en base ou radix 1000000000 (un milliard) et le code vous-même les opérations dans un très naïve de façon similaire à ce que vous avez appris comme un enfant. Mais sachez que les algorithmes plus efficaces existent (et que le véritable bignum les bibliothèques sont de leur utilisation).

Un nombre peut être représenté dans la base de 1000000000 en ayant un tableau de unsigned, chacune étant un "chiffre" de la base de 1000000000. Donc, vous avez besoin pour gérer des tableaux (probablement segment de mémoire allouée, à l'aide de malloc) et leur longueur.

Answer 2

Vous pouvez utiliser un double , surtout si votre plate-forme utilise IEEE754.

Un tel double vous donne 53 bits de précision, ce qui signifie que les entiers sont exacts jusqu'à la 53ème puissance de 2. C'est assez bon pour ce cas.

Si votre plate-forme n'utilise pas IEEE754, consultez la documentation sur le schéma à virgule flottante adopté. Cela pourrait être suffisant.

Answer 3

Une approche simple, quand vous êtes juste au dessus de la limite de l'exemple maxint, est de faire les calculs modulo 10^n pour une solution de n et de vous faire le même calcul à virgule flottante calcul, mais où vous divisez le tout par 10^r.Le premier résultat sera de vous donner les n premiers chiffres, tandis que le dernier résultat va vous donner les derniers chiffres de la réponse à la première r chiffres supprimés. Puis le dernier quelques chiffres ici seront inexactes en raison des erreurs d'arrondi, donc vous devez choisir r un peu plus petit que n. Dans ce cas, en prenant n = 9 et r = 5 fonctionne bien.