C / Trouve 190! (factorielle) en programmation c

J’essaie de trouver 190! en C .

Je définis ma variable long double, mais je vois qu’elle ne calcule (correctement) qu’à 172 !:

Après cela, j’ai eu #INF00000

Il y a un moyen de le faire?

Il ne s’agit en réalité que de quelques lignes de code pour implémenter suffisamment d’implémentation bigint pour calculer des factoriels. Voici le code qui imprime les 200 premiers factoriels.

 #include  int mult(int n, size_t size, unsigned char *data) { int carry = 0; for (int i = 0; i < size; i++) { int result = data[i] * n + carry; data[i] = result % 100; carry = (result - data[i]) / 100; } return carry != 0; } void print(size_t size, unsigned char *data) { int first = 1; for (int i = 0; i < size; i++) { int d = data[size - i - 1]; if (first && d == 0) continue; printf("%0*d", first && d < 10 ? 1 : 2, d); first = 0; } } int main(int argc, char*argv[]) { for (int fact = 1; fact <= 200; fact++) { unsigned char data[1000] = {1}; for (int i = 1; i <= fact; i++) { if (mult(i, sizeof(data), data)) { return 1; } } printf("%d! = ", fact); print(sizeof(data), data); printf("\n"); } return 0; } 

Factorial de 190 est:

9680322675255249156123346514615331205418161260462873360750859919944104623425228207640470674933540169424682360525991982916161596983449594045525553704253602287443197783274656957056546338783001340434094795097553229620273057440272298773179365935914105128629426348958748638226084106818484328004851174161755668480000000000000000000000000000000000000000000000

ou 1170 bits. Donc, ça ne va pas dans n’importe quel type intégré. Vous avez vraiment besoin d’une bibliothèque bigint pour représenter des choses aussi grandes.

Une solution consiste à utiliser une arithmétique à précision arbitraire. Vous pouvez l’implémenter vous-même ou utiliser l’une de ces bibliothèques .

Notez que même la valeur de 172! vous avez est probablement seulement approximativement correct.

Cet exemple de programme (Win32 / Visual Studio Express) indique que l’erreur devient un 23 avec un bit 64 non signé:

 #include  #include  unsigned __int64 fact( unsigned __int64 in) { if( in == 1 ) { return 1; } unsigned __int64 f = fact(in-1); printf( "!%3I64u = %20I64u = 0x%016I64X\n", in-1, f, f ); return in*f; } int main( int argc, char * argv[] ) { unsigned __int64 in = atoi(argv[1]); unsigned __int64 f = fact(in); printf( "!%3I64u = %20I64u = 0x%016I64X\n", in, f, f ); return 0; } 

courir:

 C:\> Factorial 23 ! 1 = 1 = 0x0000000000000001 ! 2 = 2 = 0x0000000000000002 ! 3 = 6 = 0x0000000000000006 ! 4 = 24 = 0x0000000000000018 ! 5 = 120 = 0x0000000000000078 ! 6 = 720 = 0x00000000000002D0 ! 7 = 5040 = 0x00000000000013B0 ! 8 = 40320 = 0x0000000000009D80 ! 9 = 362880 = 0x0000000000058980 ! 10 = 3628800 = 0x0000000000375F00 ! 11 = 39916800 = 0x0000000002611500 ! 12 = 479001600 = 0x000000001C8CFC00 ! 13 = 6227020800 = 0x000000017328CC00 ! 14 = 87178291200 = 0x000000144C3B2800 ! 15 = 1307674368000 = 0x0000013077775800 ! 16 = 20922789888000 = 0x0000130777758000 ! 17 = 355687428096000 = 0x0001437EEECD8000 ! 18 = 6402373705728000 = 0x0016BEECCA730000 ! 19 = 121645100408832000 = 0x01B02B9306890000 ! 20 = 2432902008176640000 = 0x21C3677C82B40000 ! 21 = 14197454024290336768 = 0xC5077D36B8C40000 ! 22 = 17196083355034583040 = 0xEEA4C2B3E0D80000 ! 23 = 8128291617894825984 = 0x70CD7E2933680000 

! 21 et après sont faux.