Calculer la factorielle de grands nombres dans C

Dans mon code C Je veux calculer le factoriel pour les nombres dans la gamme de 1 avant que 100. Pour les petits nombres, la fonction fonctionne, mais pour les grands nombres /par exemple, 100!/ Il renvoie le mauvais résultat. Y a-t-il un moyen de faire face à la factorielle de grands nombres dans C?

Compilateur que j'utilise, - c'est gcc v4.3.3.
Mon code ressemble à ceci:


#include <stdio.h>
#include <math.h>

double print_solution/int/;

int main/void/
{
int no_of_inputs, n;
int ctr = 1;

scanf/"%d",&amp;no_of_inputs/; //Read no of inputs

do
{
scanf/"%d",&amp;n/; //Read the input
printf/"%.0f\n", print_solution/n//;
ctr++;
} while/ctr &lt;= no_of_inputs/;

return 0;
}

double print_solution/int n/
{
if/n == 0 || n == 1/
return 1;
else
return n*print_solution/n-1/;
}


</math.h></stdio.h>
Invité:

Gaetan

Confirmation de:

Aucun type de données standard C ne traitera pas avec précision les numéros 100!. Votre seule option est d'utiliser
http://en.wikipedia.org/wiki/A ... metic
, soit à travers la bibliothèque ou indépendamment.

Si ce n'est qu'une sorte de projet de loisirs, je vous conseillerais de l'essayer vous-même. C'est une sorte d'exercice drôle. Si cela est connecté au travail, utilisez la bibliothèque existante.

Le plus grand type de données C, que vous obtenez habituellement - Ceci est un entier 64-bit. 100! Situé dans l'ordre 10

157

, Ce qui ne prend pas moins 525 Bit pour un stockage précis sous la forme d'un entier.

Catherine

Confirmation de:

100 factorial est énorme, si vous êtes précis, alors cela 93326215443944152681699238856266700490715968264381621468592963895217
59999322991560894146397615651828625369792082722375825118521091686400
00000000000000000000.

Peut-être devriez-vous utiliser la bibliothèque bignum, tel que
http://gmplib.org/
. Il a de bons documents, une jolie interface série, une vitesse et si vous êtes sur Linux, Votre distribution est susceptible d'avoir un paquet. /Je pense que le mien l'installe par défaut/

Hannah12

Confirmation de:

Pour calculer approximativement les facteurs de grand nombre, vous pouvez aller comme suit:

n! = n * /n-1/!
so log/n!/ = log/n/ + log/n-1!/
Maintenant, vous pouvez utiliser une programmation dynamique pour calculer log/n!/ et calculs

N! comme /De base/^/Valeur de journal/

Darius

Confirmation de:

Si vous ne voulez pas utiliser la bibliothèque bigint, Le meilleur que vous puissiez faire avec stdlib, - C'est utilisé
long double

et
tgammal//

de
math.h

:


long double fact/unsigned n/
{
return tgammal/n + 1/;
}


Ça va te donner
100!

Avec précision 18 signes décimaux sur x86 /c'est à dire 80 bit
long double

/.

La mise en œuvre précise n'est pas non plus si difficile:


#include <math.h>
#include <stdio.h>
#include <string.h>

void multd/char * s, size_t len, unsigned n/
{
unsigned values[len];
memset/values, 0, sizeof/unsigned/ * len/;
for/size_t i = len; i--; /
{
unsigned x = values[i] + /s[i] - '0'/ * n;
s[i] = '0' + x % 10;
if/i/ values[i - 1] += x / 10;
}
}

void factd/char * s, size_t len, unsigned n/
{
memset/s, '0', len - 1/;
s[len - 1] = '1';
for/; n &gt; 1; --n/ multd/s, len, n/;
}

int main/void/
{
unsigned n = 100;
size_t len = ceill/log10l/tgammal/n + 1///;
char dstr[len + 1];
dstr[len] = 0;
factd/dstr, len, n/;
puts/dstr/;
}


</string.h></stdio.h></math.h>

Agathe

Confirmation de:

Tout le monde vous dit la bonne réponse, mais il y a encore quelques instants.

Votre idée initiale d'utiliser un double pour obtenir une plage plus large ne fonctionne pas, car le jumeau ne peut pas stocker avec précision ces données. Il peut effectuer des calculs, mais avec un grand nombre de tours. C'est pourquoi les bibliothèques existent bigint.

Je sais que c'est probablement un exemple du manuel ou du site d'exemples, mais l'exécution de la récursivité illimitée vous mordera à un moment donné. Vous avez une solution récursive pour le fait que c'est essentiellement un processus itératif. Vous comprendrez pourquoi ce site est appelé tel quel moment vous essayez d'exécuter votre programme avec de grandes valeurs /Essayer 10000/.

Une approche itérative simple est la suivante


int answer, idx;

for /answer = 1, idx = 1; idx <= no_of_inputs; idx++ / {
answer = answer * idx;
}
printf/"Factorial of %3d = %d\n", no_of_inputs, answer/;

Giselle

Confirmation de:

C'est ce que j'ai fait pour résoudre l'énigme google Il y a quelques années, elle utilise la bibliothèque GMP
http://gmplib.org/
/ :


#include <stdio.h>
#include "gmp.h"

void fact/mpz_t r,int n/{
unsigned int i;
mpz_t temp;
mpz_init/temp/;
mpz_set_ui/r,1/;
for/i=1;i&lt;=n;i++/{
mpz_set_ui/temp,i/;
mpz_mul/r,r,temp/;
}
mpz_clear/temp/;
}
int main/void/ {
mpz_t r;
mpz_init/r/;
fact/r,188315/;
/* fact/r,100/; */
gmp_printf/"%Zd\n",r/;
mpz_clear/r/;
return/0/;
}


gcc -lgmp -o fait fact.c

./fait
</stdio.h>

Ernest

Confirmation de:

Ceci est définitivement dû au débordement. Vous avez besoin d'un moyen de représenter grand nombre /
unsigned long long

ne peut même pas couvrir 21!/.

Alice

Confirmation de:

Vous pouvez essayer d'aller au type "unsigned long long", Mais c'est le maximum que vous pouvez obtenir avec les types intégrés.
je voudrais suggerer /Comment a déjà mentionné la cellule/ Ou aller avec la mise en œuvre bien connue de grandes nombres, ou écrivez-le vous-même. "its a nice exercise" H. 2.

Hippolite

Confirmation de:

Si vous souhaitez utiliser uniquement des types de données standard et que vous n'avez pas besoin d'une réponse précise, calculez le logarithme n! au lieu de lui-même n!. Logarithme N! Facile placé dans
double

/Si n est un énorme/.

Gaetan

Confirmation de:

Y a-t-il des moyens de traiter le factoriel de grands nombres dans C ?

Étant donné que les facteurs facteurs peuvent rapidement dépasser la plage de largeurs fixes des entiers standard et même des types de points flottants , tel que
double

, Le code doit prendre en compte le type d'utilisateur qui admet une précision intégrée illimitée pour

exact

Réponse.

Il existe diverses bibliothèques une grande précision entière, mais si le code nécessite une solution simple, envisagez d'utiliser

cordes

.

Ce qui suit n'est pas rapide et ne se souvient pas des limites des tableaux, mais illustre toujours cette idée. Conversion
'0'-'9'

à/de
0-9

tellement gusté, mais cela facilite la déboguer step-by-step.


#include <stdlib.h>
#include <string.h>
#include <stdio.h>

static char *strfact_mult/char *s, unsigned x/ {
unsigned sum = 0;
size_t len = strlen/s/;
size_t i = len;
while /i &gt; 0/ {
sum += /s[--i] - '0'/ * x;
s[i] = sum % 10 + '0';
sum /= 10;
}
while /sum/ {
len++;
memmove/&amp;s[1], s, len/;
s[i] = sum % 10 + '0';
sum /= 10;
}
return s;
}

char *str_fact/char *dest, unsigned n/ {
strcpy/dest, "1"/;
while /n &gt; 1/ {
strfact_mult/dest, n--/;
}
return dest;
}

void test_fact/unsigned n/ {
char s[1000];
printf/"%3u %s\n", n, str_fact/s, n//;
}

int main/void/ {
test_fact/0/;
test_fact/4/;
test_fact/54/;
test_fact/100/;
}


Sortir


0 1
4 24
54 230843697339241380472092742683027581083278564571807941132288000000000000
100 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000


</stdio.h></string.h></stdlib.h>

Florian

Confirmation de:

Factoriels 12! Convient à un entier 32 bits. Factoriels 20! convient à un entier 64-bit. Après cela, vous avez fini de bits sur la plupart des machines. mais 34! Convient à un entier non signé 128 bits 57! Convient à un entier de 256 bits et 98! Convient à un entier non signé 512 bits. Calculer 100! En tant qu'intéger, vous avez besoin au moins 525 bit.

Ce script
bc

Calcule les facteurs facteurs /avant que 35! Mais vous pouvez facilement changer la limite/:


#!/usr/bin/bc -l

define f/n/ {
auto r, i
r = 1
for /i = 1; i <= n; i++/
{
r *= i;
print "n = ", i, ", log2 = ", l/r//l/2/, ", n! = ", r, "\n"
}
}

f/35/
quit


Et certaines valeurs approximatives:


# Key values
# n = 1, log2 = 0.00000000000000000000, n! = 1
# n = 2, log2 = 1.00000000000000000000, n! = 2
# n = 3, log2 = 2.58496250072115618147, n! = 6
# n = 4, log2 = 4.58496250072115618149, n! = 24
# n = 5, log2 = 6.90689059560851852938, n! = 120
# n = 6, log2 = 9.49185309632967471087, n! = 720
# n = 7, log2 = 12.29920801838727881834, n! = 5040
# n = 8, log2 = 15.29920801838727881836, n! = 40320
# n = 9, log2 = 18.46913301982959118130, n! = 362880
# n = 10, log2 = 21.79106111471695352921, n! = 3628800
# n = 11, log2 = 25.25049273335425078544, n! = 39916800
# n = 12, log2 = 28.83545523407540696694, n! = 479001600
# n = 13, log2 = 32.53589495221649912738, n! = 6227020800
# n = 14, log2 = 36.34324987427410323486, n! = 87178291200
# n = 15, log2 = 40.25014046988262176421, n! = 1307674368000
# n = 16, log2 = 44.25014046988262176426, n! = 20922789888000
# n = 17, log2 = 48.33760331113296117256, n! = 355687428096000
# n = 18, log2 = 52.50752831257527353551, n! = 6402373705728000
# n = 19, log2 = 56.75545582601885902935, n! = 121645100408832000
# n = 20, log2 = 61.07738392090622137726, n! = 2432902008176640000
# n = 21, log2 = 65.46970134368498166621, n! = 51090942171709440000
# ...
# n = 34, log2 = 127.79512061296909618950, n! = 295232799039604140847618609643520000000
# n = 35, log2 = 132.92440362991406264487, n! = 10333147966386144929666651337523200000000
# ...
# n = 57, log2 = 254.48541573017643505939
# n = 58, log2 = 260.34339672530400718017
# ...
# n = 98, log2 = 511.49178048020535201128
# n = 99, log2 = 518.12113710028496163045
# n = 100, log2 = 524.76499329005968632625


Pour les facteurs facteurs 57!, 58!, 98!, 99!, 100! J'ai abaissé la valeur de factorielle car elle s'applique à plusieurs lignes dans les données de sortie et n'est pas si importante. noter que 100! Nécessité non moins 525 Précision du bit.

Ce code est disponible dans mon
https://github.com/jleffler/soq
SOQ /Stack Overflow des questions/ sur le GitHub sous forme de fichier
factorial.bc

dans le sous-répertoire
https://github.com/jleffler/so ... llany
.

vous pouvez utiliser
double

ou
long double

Pour développer la gamme de valeurs, mais vous perdez une précision.

Christine

Confirmation de:

Je pense que c'est parce que vous submergez la gamme int, qui est jusqu'à env. 2 milliard. Vous pouvez arriver à 4 des milliards si vous utilisez unsigned int, Mais à part cela, vous devez utiliser
http://mattmccutchen.net/bigint/
.

Emilie

Confirmation de:

100! = 933262154439441526816992388562667004907159682643816214685929
6389521759999322991560894146397156518286253697920827223758251185210
916864000000000000000000000000

Vous ne pouvez pas imaginer le nombre de cette taille avec int ou long.

Edouard

Confirmation de:

En plus des conseils des autres, je vous conseillerais de vous familiariser avec les restrictions de stockage des principaux types. /int, long, long long, .../ Pour tout ordinateur/Plate-forme que vous utilisez réellement. /"Si vous doutez, imprimez plus!"/

L'une des affiches précédentes a mentionné la limite de précision 80 bits, mais elle s'applique particulièrement à x86 CPU.

Une autre personne citée plusieurs fois ISO C90, Bien que C99 soit la dernière norme; Même si de nombreux compilateurs ne sont pas complètement mis en œuvre C99, Vous constaterez probablement qu'ils sont très, très susceptibles d'avoir au moins un soutien long long, qui doit correspondre à la précision >= 64-bit.

Georges

Confirmation de:

Voici la solution de votre question:


#include <stdio.h>
void factorial/int b/{
int temp = 0, r, size = 0, x;
int arr[200] = {0};
int l_b = b-1;
while/b&gt;0/{
r = b;
arr[size++] = r;
b = b/10;
}
while/l_b &gt;= 2/{
int i=0;
while/size&gt;0/{
x = arr[i]*l_b+temp ;
arr[i++] = x;
temp = x/10;
size--;
}
while/temp&gt;0/{
arr[i++] = temp;
temp = temp/10;
}
size = i; --l_b;
}
for/int k=size-1;k&gt;=0;k--/
printf/"%d",arr[k]/;//ok i'm taking space here
printf/"\n"/;
}
int main/void/ {
// your code goes here
int fact;

scanf/"%d\n",&amp;fact/;
factorial/fact/;

return 0;
}


</stdio.h>

Hippolite

Confirmation de:

N'utilisez pas l'algorithme récursif, je pense que c'est très lent, même si elle se cache, elle sera lente. C'est juste ce que vous devriez considérer.

La raison en est que lorsque vous appelez fact/100/, Vous le lancez réellement pas 100 OK, A.

5050

temps. Ce qui est mauvais s'il est mis en cache, alors ça peut être 100 fois, mais toujours plus lentement d'exécuter un appel de fonction avec des opérateurs if, Quoi commencer le cycle.


double print_solution/int n/
{
double rval = 1;
unsigned int i;

for/ i = 1; i <= n; i++ / {
rval *= i;
}

return rval;

}


En utilisant des arithmétiques avec une précision arbitraire, vous pouvez le rendre très élevé, mais pour cela, vous devez utiliser la bibliothèque ou créer votre propre bibliothèque, mais cela prendra beaucoup de temps.

Pour répondre aux questions, connectez-vous ou registre