J'essaie d'écrire une fonction factorielle pour calculer un grand nombre (factorielle (105)), son résultat a 168 chiffres, alors utilisez long double, mais cela semble être une erreur, ne peut-il pas utiliser comme ça?

#include <stdio.h>

long double factorial(long double n,long double base = 1){
  if (n <= 1){
    return 1*base;
  }else{
    return factorial(n-1,n * base);
  }
}  
int main(){  
    printf("%.0Lf\n",factorial(25));     // this result is correct

    printf("%.0Lf\n",factorial(26));    
    //correct result is 403291461126605635584000000,but it return 403291461126605635592388608
    return 0;
}
-1
archi 20 nov. 2018 à 09:11

3 réponses

Meilleure réponse

25

Étant donné qu'un long double, sur les plates-formes qui le supportent, est généralement de 80 bits pour la valeur entière (pas seulement la mantisse!), Apparemment il n'y a aucun moyen que vous ayez assez de mantisse pour effectuer ces calculs de cet ordre de grandeur avec une précision entière.

Cependant : factorielle ici est un peu magique, car beaucoup de facteurs contiennent des puissances de deux, qui ajoutent juste des zéros binaires à droite, qui ne nécessitent pas de mantisse (ils finissent dans l'exposant). En particulier:

25! = 2   4   2   8   2    4    2    16    2    4     2    8    = 2²² · m
        3   5 3 7   9 5 11 3 13 7 15    17 9 19 5 21 11 23 3 25 

dix 6 3 2

Par conséquent, notre estimation initiale dépasse les besoins réels de 22 bits.

Il se trouve que

Log 2 (f) = 10 · log 2 3 + 6 · log 2 5 + 3 · log 2 7 + 2 · journal 2 11 + journal 2 13 + journal 2 17 + journal 2 19 + journal < sous> 2 23 = 61,68

Qui est en effet juste en dessous de la taille de la mantisse du double de 80 bits (64 bits). Mais lorsque vous le multipliez par 26 (donc, en excluant le facteur 2, qui se termine dans l'exposant, par 13), vous ajoutez log2 (13) = 3,7 bits. 61,7 + 3,7 est 65,4, donc à partir de 26! à partir de là, vous n'avez plus la précision pour effectuer exactement votre calcul.

5
Matteo Italia 20 nov. 2018 à 08:16

Depuis 105! est un nombre énorme qui ne tient pas dans un seul mot (ou deux d’entre eux), vous voulez arithmétique de précision arbitraire, également appelée bignum s. Utilisez l 'l'approximation de Stirling pour avoir une idée de la taille de 105! est et lisez le wikipage sur factorials.

Standard C (lisez n1570 pour vérifier) n'ont pas de bignums nativement, mais vous trouverez de nombreuses bibliothèques pour cela.

Je recommande GMPlib. BTW, une partie de son code est un assemblage écrit à la main pour des raisons de performances (lors du codage de l'ajout de bignum, vous voulez profiter des instructions de la machine add with carry ).

Je recommande d'éviter d'écrire vos propres opérations bignum. Les bibliothèques existantes utilisent des algorithmes très intelligents (et vous devrez faire fonctionner certains doctorats pour obtenir quelque chose de mieux). Si vous essayez de coder votre propre bibliothèque bignum, ce sera probablement bien pire que vos concurrents (à moins que vous ne passiez des années de travail).

3
Basile Starynkevitch 20 nov. 2018 à 07:01

Premièrement, personne ne sait ce que long double peut ou ne peut pas représenter. Les propriétés spécifiques du format dépendent de l'implémentation.

Deuxièmement, le format à virgule flottante de précision étendue X86 a une signification de 64 bits avec un début explicite 1, ce qui signifie qu'il peut représenter des entiers contigus dans une plage de ± 2 64 . Au-delà de cette plage, les entiers représentables ne sont pas contigus (c'est-à-dire qu'ils commencent à «sauter» avec des intervalles de plus en plus larges). Vos factorielles se situent bien en dehors de cette plage, ce qui signifie que l'on s'attend parfaitement à ce qu'elles ne soient pas représentées avec précision.

3
AnT 20 nov. 2018 à 06:53