probleme de calcul factoriel

Version imprimable

13/02/2007, 07h56
argon

probleme de calcul factoriel
Bonjour tout le monde

J'ai un problème avec le calcul de la factoriel.

Voici le code, je ne mets que la fonction où il y a la boucle.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 int factoriel(int m) { int i; for(i=1;i<m;i++) { m = m*i; } printf("resulat %d\n", m); return m; }
Il me sort des résultat négatif.

Pourquoi?

Merci.

Cordialement

A bientôt
13/02/2007, 08h26
JeitEmgie
Citation:
Envoyé par argon

Bonjour tout le monde

J'ai un problème avec le calcul de la factoriel.

Voici le code, je ne mets que la fonction où il y a la boucle.

Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 int factoriel(int m) { int i; for(i=1;i<m;i++) { m = m*i; } printf("resulat %d\n", m); return m; }

Il me sort des résultat négatif.

Pourquoi?

Merci.

Cordialement

A bientôt
… overflow…

un "int" est stocké sur un nombre fini de bits (8, 16, 32, 64, 128 pour les architectures les plus courantes)
dès que le résultat est plus grand que le plus grand entier positif représentable sur le nombre de bits dédiés aux entiers "int" par votre architecture (hardware + compilateur), le résultat apparaîtra négatif…

vous gagnerez un peu "d'espace" en déclarant i et m "unsigned int",
ou encore "unsigned long long"…

mais pour calculer de très grand nombres il faut utiliser une bibliothèque adhoc… voir par exemple http://www.swox.com/gmp/

Salut,

Le problème vient du fait que tu utilises le paramètre m comme condition d'arrêt de ta boucle for, mais que m est également modifié dans le corps de ta boucle. Le code suivant fonctionne:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include <stdio.h> #include <stdlib.h> int factoriel(int m) { int i; int result = m; for (i = 1; i < m; i++) { result = result * i; } printf("resulat %d\n", result); return result; } int main(void) { factoriel(3); return EXIT_SUCCESS; }
Thierry

13/02/2007, 08h38
Thierry Chappuis

Citation:

Envoyé par JeitEmgie

… overflow…

un "int" est stocké sur un nombre fini de bits (8, 16, 32, 64, 128 pour les architectures les plus courantes)
dès que le résultat est plus grand que le plus grand entier positif représentable sur le nombre de bits dédiés aux entiers "int" par votre architecture (hardware + compilateur), le résultat apparaîtra négatif…

vous gagnerez un peu "d'espace" en déclarant i et m "unsigned int",
ou encore "unsigned long long"…

mais pour calculer de très grand nombres il faut utiliser une bibliothèque adhoc… voir par exemple http://www.swox.com/gmp/

En l'occurence, il y avait overflow déjà avec l'appel factoriel(3). Le problème était un problème de logique et non d'entier signé ou non. Toutefois, il est vrai qu'on peut déclarer result comme unsigned int, celui-ci ne prenant jamais de valeur négative (c'est même préférable). En ce qui concerne i, ce n'est pas forcément nécessaire. Dans le calcul d'une factorielle, c'est surtout le résultat qui devient énorme.

Thierry

oui dans ce cas-là moi je mettrais le résultat en double....

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
double factoriel(int m)
{
    int i;
    double result = (double)m;
 
    for (i = 1; i < m; i++)
    {
        result = result * (double)i;
    }
 
    printf("resultat %g\n", result);
    return result;
}

13/02/2007, 12h51
Franck.H

Citation:

Envoyé par souviron34

oui dans ce cas-là moi je mettrais le résultat en double....

Heu pas plutôt unsigned long ? double étant un nombre à virgule flottante et lui il est basé sur un int au départ.
13/02/2007, 13h51
souviron34

Citation:

Envoyé par Franck.H

Heu pas plutôt unsigned long ? double étant un nombre à virgule flottante et lui il est basé sur un int au départ.

et ??

factorielle (255 ) doit bien dépasser les capacités d'un int ou long non ?
Suivant l'architecture c'est assez facile à calculer :

le max est soit 32 soit 64 bits pour un entier... donc 2^ 32 ou 64

je suppose donc (en gros, je vais pas me taper le calcul) que factorielle(66) dépasse les 64 bits..
13/02/2007, 14h10
Thierry Chappuis

Citation:

Envoyé par souviron34

et ??

factorielle (255 ) doit bien dépasser les capacités d'un int ou long non ?
Suivant l'architecture c'est assez facile à calculer :

le max est soit 32 soit 64 bits pour un entier... donc 2^ 32 ou 64

je suppose donc (en gros, je vais pas me taper le calcul) que factorielle(66) dépasse les 64 bits..

Tu as raison! Un entier, même de 64 bits, c'est ridicule pour calculer une factorielle...

Thierry
13/02/2007, 14h16
Franck.H

Ouais effectivement, j'avais pas vu ca sous cet angle :lol:
15/02/2007, 12h24
Melem

Re:
Comme mujigka l'a déja fait remarqué déja l'algorithme est faux. Théoriquement c'est même une boucle sans fin puisque m sera toujours supérieur a i. Bref, un code plus éfficace :
Code:

1 2 3 4 5 6 double factorielle(int n) { if (n == 0) return 1.0; else return n * factorielle(n - 1); }
Utilise %g dans printf pour afficher le résultat.
15/02/2007, 12h58
millie
Citation:

Envoyé par Melem

Bref, un code plus éfficace :

Ici, ça va qu'il est peu probable que l'on fasse un appel avec une grosse valeur. Mais faire un nombre d'appel important (à cause de la définition récursive) peut être dangereux car il peut vite y avoir des dépassements de piles.

Maintenant, si tu fais un appel avec -1.0 dans ta fonction, là, tu auras à coup sur un beau stack overflow.

Un dépassement de pile serait encore plus susceptible d'arriver avec une fonction du genre :
Code:

1 2 3 4 5 6 7 long fonction(long n) { if (n <= 0) return 0; else return(1 + fonction(n - 1)); }
15/02/2007, 13h06
Médinoc

Pourquoi encore plus ?
15/02/2007, 13h15
millie

Enfin, je parlais dans la mesure ou la fonction fonctionne bien :

faire un appel à : fonction(1000000) retournera le bon résultat alors que l'appel à factoriel(1000000) ne retournera pas le bon (comme ça avait déjà été signalé).

Enfin, si on met une précondition supplémentaire afin que le résultat soit correcte, il faut énormement limiter l'espace de départ de la fonction factoriel. L'espace de départ de l'autre est pas contre beaucoup plus grand.

Je parlais qu'il y avait plus de chance de faire un dépassement de pile si l'on se retreint à ces espaces.
15/02/2007, 13h34
Thierry Chappuis

Citation:

Envoyé par Melem

Bref, un code plus éfficace :

Plus efficace, vraiment?

Thierry
15/02/2007, 13h36
souviron34

Citation:

Envoyé par millie

Ici, ça va qu'il est peu probable que l'on fasse un appel avec une grosse valeur. Mais faire un nombre d'appel important (à cause de la définition récursive) peut être dangereux car il peut vite y avoir des dépassements de piles.
[/CODE]

Euh.. Pardon, mais il me semble que vu que le code ne fait pas d'allocation et n'a aucune variable "à lui", en quoi la taille de la pile est-elle importante ?? A la limite il y aura du swap, mais je vois pas pourquoi on ne pourrait pas faire 500 000 appels itératifs ??? (ou bien il y a quelque chose qui m'échappe, ce qui est fort possible :oops: )

[EDIT]

Mais bon tout ceci pour dire que la première version (aux détails réglés après près) est nettement plus effiicace quand même que celle de Melem..

[/EDIT]
15/02/2007, 13h42
JeitEmgie

Citation:

Envoyé par millie

Enfin, je parlais dans la mesure ou la fonction fonctionne bien :

faire un appel à : fonction(1000000) retournera le bon résultat alors que l'appel à factoriel(1000000) ne retournera pas le bon (comme ça avait déjà été signalé).
.

FYI,
100000! est déjà un nombre de 456.575 chiffres…
et 1000000! fait 5.565.710 chiffres…
15/02/2007, 13h50
thewho
Bonjour,
Citation:
Envoyé par millie

Code:

1 2 3 4 5 6 7 long fonction(long n) { if (n <= 0) return 0; else return(1 + fonction(n - 1)); }

...

faire un appel à : fonction(1000000) retournera le bon résultat alors que l'appel à factoriel(1000000) ne retournera pas le bon (comme ça avait déjà été signalé).
Certes, mais fonction ne calcule pas la factorielle, ou alors il faut que je retorune à l'école.

Citation:

Envoyé par millie

EDIT : D'ailleurs, en prenant le fait que le nombre d'atome dans l'univers est minoré par 2^100 et le fait que 100! est minoré par 2^100. On en déduit facilement :p que l'on ne pourra jamais calculer 100!. Donc au pire, il y aura 100 appels récursifs (même si on a une possibilité de représentation immense pour les entiers). Ca ne ferait que 100 éléments à peu près sur la pile. Donc, c'est fort respectable.

Parce que tu penses que le nombre de particules dans l'univers interdit l'utilisation de nombre plus grands ?

Pour quelle raison cela serait-il ?

100! est de l'ordre de 10^158.

Pour ta gouverne, les mathématiciens (essentiellement) de certains domaines utilisent assez régulièrement des nombres beaucoup plus, mais alors vraiment beaucoup plus grands.

Moi-même, j'utilise journellement des nombres de longueur moyenne 10^1000, et occasionnellement, jusqu'à 10^100000, et je ne suis qu'un modeste utilisateur par rapport à d'autres.
15/02/2007, 14h09
millie

J'ai oublié un 2^100. Je voulais dire qu'il n'est pas possible d'utiliser d'entier dont la representation binaire requiert plus de 2^100 bits, comme par exemple 2^2^100.

Donc, revois ton jugement avec ma correction :king:

Citation:

Certes, mais fonction ne calcule pas la factorielle, ou alors il faut que je retorune à l'école.

je n'ai jamais dit le contraire. J'ai dit qu'il etait plus probable de faire tout planter avec cette fonction si l'on se restreint à un espace de depart où la fonction donne un résultat correct. C'était juste un exemple pour montrer que certaines fonctions avec des appels récursifs peuvent facilement faire des dépassements de pile.

Citation:

Euh.. Pardon, mais il me semble que vu que le code ne fait pas d'allocation et n'a aucune variable "à lui", en quoi la taille de la pile est-elle importante ??

Il faut bien une adresse de retour stockée sur la pile...
15/02/2007, 14h12
crocodilex

Citation:

Envoyé par souviron34

Euh.. Pardon, mais il me semble que vu que le code ne fait pas d'allocation et n'a aucune variable "à lui", en quoi la taille de la pile est-elle importante ?? A la limite il y aura du swap, mais je vois pas pourquoi on ne pourrait pas faire 500 000 appels itératifs ??? (ou bien il y a quelque chose qui m'échappe, ce qui est fort possible :oops: )

[EDIT]

Mais bon tout ceci pour dire que la première version (aux détails réglés après près) est nettement plus effiicace quand même que celle de Melem..

[/EDIT]

Lorsqu’on fait de l’allocation dynamique, la mémoire n’est certainement pas allouée dans la pile. Donc le problème n’est pas là.
Par contre les paramètres passés à une fonction sont, eux, alloués dans la pile. On y sauvegarde également l’état de certains registres ainsi que l’adresse de retour.
Donc forcément, si une fonction est appelée 500 000 fois de façon récursive, la pile aura tendance à grossir jusqu’à l’explosion.

euhhh...

testez ce petit prog. et dites-moi ce qui se passe :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include <stdio.h> #include <stdlib.h> static double MaFonction ( double Val ) { Val = Val + 1.0 ; fprintf ( stderr, "\r%g", Val ); return ( MaFonction(Val) ); } /* ********************* main routine ********************* */ int main (int argc, char **argv) { double d, d1=0.0 ; d=MaFonction(d1); return 0 ; }
[EDIT]
Bon pour faire propre et correct j'aurais dû passer par adresse.. Ne faites pas la remarque :oops: ...

Mais il n'empêche que ça ne plante pas (modification "down"), et que je n'ai pas réussi à faire craquer .... ;) (bon j'ai arrêté à 12 10^7... Mais bon ça m'étonnerait que la pile fasse autant :P )

[/EDIT]

16/02/2007, 10h07
Melem

Citation:

Envoyé par millie

Ici, ça va qu'il est peu probable que l'on fasse un appel avec une grosse valeur. Mais faire un nombre d'appel important (à cause de la définition récursive) peut être dangereux car il peut vite y avoir des dépassements de piles.

Citation:

Envoyé par Médinoc

Pouquoi encore plus

Mais c'est sur qu'avec n'importe quelle fonction en ne pourra jamais calculer 1.000.000! sinon donnez-moi un exemple. Même la fonction fact() de math.h ne peut pas. Pour faire de pareils calculs on utilise même pas des PC mais des supercalculateurs. Mettez double factorielle(int n) ou même double factorielle(char n) si vous en avez envi. Mais moi je trouve que pour une fonction récursive qu'est factorielle, un code récursif c'est plus adapté, plus concis et plus lisible. Donc puisque ce n'est pas du code optimisé qu'on recherche, c'est plus efficace! Et avec des valeurs raisonnables passées e argument, il n'y aura pas de débodement de pile. Sinon prévenez-moi.
16/02/2007, 10h11
Médinoc

Citation:

Envoyé par Melem

moi je trouve que pour une fonction récursive qu'est factorielle, un code récursif c'est plus adapté, plus concis et plus lisible.

Pas moi. C'est un exemple d'école de calcul récursif, mais l'algorithme itératif est tout aussi simple, voire plus.

Là où la récursivité est plus évidente, c'est pour des fonctions comme le parcours d'arbre sans chaînage double, où l'algorithme est forcément récursif (une implémentation "itérative avec une pile" reste du récursif pour moi, puisqu'on utilise toujours une pile).

Citation:
Envoyé par souviron34
euhhh...

testez ce petit prog. et dites-moi ce qui se passe :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include <stdio.h> #include <stdlib.h> static double MaFonction ( double Val ) { Val = Val + 1.0 ; fprintf ( stderr, "\r%g", Val ); return ( MaFonction(Val) ); } /* ********************* main routine ********************* */ int main (int argc, char **argv) { double d, d1=0.0 ; d=MaFonction(d1); return 0 ; }
Erreur de segmentation à Val = 261637!!! Il est possible qu'avec certaines options d'optimisation, une fonction aussi simple soit dérécursifiée, ce qui expliquerait pourquoi tu n'obtient pas d'explosion de la pile. En compilant avec gcc -Wall -O2, pas d'explosion de la pile (j'ai arrêté vers 10^7).

Thierry

Citation:

Envoyé par mujigka

Erreur de segmentation à Val = 261637!!! Il est possible qu'avec certaines options d'optimisation, une fonction aussi simple soit dérécursifiée, ce qui expliquerait pourquoi tu n'obtient pas d'explosion de la pile. En compilant avec gcc -Wall -O2, pas d'explosion de la pile (j'ai arrêté vers 10^7).

Thierry

Pour ceux que ca interesse (j'ai retire le printf).
Code:

1 2 3 4 static double MaFonction ( double Val ) { return ( MaFonction(Val+1.0) ); }
(pas d'explosion de pile)

Avec -O3 -S (sur un x86):
Code:

1 2 3 4 5 MaFonction: pushl %ebp movl %esp, %ebp .L3: jmp .L3
Avec -O0 -S :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 MaFonction: pushl %ebp movl %esp, %ebp subl $16, %esp movl 8(%ebp), %eax movl %eax, -8(%ebp) movl 12(%ebp), %eax movl %eax, -4(%ebp) fldl -8(%ebp) fld1 faddp %st, %st(1) fstpl (%esp) call MaFonction leave
La fonction a ete derecursifiee. :D

Citation:
Envoyé par souviron34
euhhh...

testez ce petit prog. et dites-moi ce qui se passe :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include <stdio.h> #include <stdlib.h> static double MaFonction ( double Val ) { Val = Val + 1.0 ; fprintf ( stderr, "\r%g", Val ); return ( MaFonction(Val) ); } /* ********************* main routine ********************* */ int main (int argc, char **argv) { double d, d1=0.0 ; d=MaFonction(d1); return 0 ; }
[EDIT]
Bon pour faire propre et correct j'aurais dû passer par adresse.. Ne faites pas la remarque :oops: ...

Mais il n'empêche que ça ne plante pas (modification "down"), et que je n'ai pas réussi à faire craquer .... ;) (bon j'ai arrêté à 12 10^7... Mais bon ça m'étonnerait que la pile fasse autant :P )

[/EDIT]
Chez moi, la pile a explosé à Val=65074 :)

16/02/2007, 12h26
souviron34

ben moi sur un Acer Aspire 1362 256 M de RAM Linux Redhat 7.3 jamais explosé..... Sans optimisation.. cc -Wall ...

:mrgreen:
16/02/2007, 12h32
Thierry Chappuis

Citation:

Envoyé par souviron34

ben moi sur un Acer Aspire 1362 256 M de RAM Linux Redhat 7.3 jamais explosé..... Sans optimisation.. cc -Wall ...

:mrgreen:

Soit, mais c'est osé du point de vue portabilité de parier dessus... As-tu essayée avec l'option -O0 pour être certain que le compilateur ne réalise pas des optimisation par défaut?

Thierry
16/02/2007, 12h48
hegros

Citation:

Envoyé par crocodilex

Chez moi, la pile a explosé à Val=65074 :)

C'est quoi ton système ?

Je suis allé jusqu'a 14.68658e+006 et ca tourne encore

Systéme windows 2000 SP4 Intel celeron 2.7Ghz 515mo de ram :mrgreen:
16/02/2007, 13h52
millie

Comme je l'ai indique avec mon exemple, le code peut etre optimise, et il y aura seulement une boucle infinie sans avoir de call a la fonction (desole, toujours sous qwerty). Donc, on empile par l'adresse de retour, et la base et le sommet de la pile ne bougent plus.

Il faut (je repete ce qu'a dit mujigka), il faut compiler avec -O0. Et normalement, il fera un depassement de pile.

Pour indication, je suis sur un serveur sun :

Code:

74821 Segmentation Fault (core dumped)

Mais il est possible de modifier la taille de la pile.
16/02/2007, 14h41
souviron34

bon j'ai fini par le faire planter :yaisse2:

Quelques explications théoriques s'imposent, et non du tatonnement...

Et je crois que j'ai compris, car j'ai fait quelques petits tests et réflexions....

1) ça plante vers 1.7 E+07 appels...

Ce qui correspond à (en gros) 2^24 ...

Donc la taille de la pile est de 24 bits....

On peut donc si on le désire (et donc si les prévisions d'imbrications sont inférieures à ceci) monter jusqu'à 24 bits de pile.

2) le nombre maximum pour lequel une factorielle peut être calculé dépend de l'architecture, bien sûr, et directement du nombre de bits : la place prise par un double.

Un petit test rapide (machine 32 bits donc double = 64 bits) indique que l'on peut calculer jusqu'à: factorielle(1.97969 e+308)

ça vous suffit ?? :P :mrgreen:
16/02/2007, 14h56
millie

Citation:

Envoyé par souviron34

Ce qui correspond à (en gros) 2^24 ...

Donc la taille de la pile est de 24 bits....

Et non, sinon ca planterait beaucoup plus vite :mouarf:

Citation:

Envoyé par souviron34

le nombre maximum pour lequel une factorielle peut être calculé dépend de l'architecture, bien sûr, et directement du nombre de bits : la place prise par un double.

En fait, sur un systeme UNIX, on peut changer la taille de la pile avec ulimit -s:

Un oeil dans le man donne : -s maximum size of stack segment (in kbytes)
16/02/2007, 15h15
souviron34

Citation:

Envoyé par millie

En fait, sur un systeme UNIX, on peut changer la taille de la pile avec ulimit -s:

Un oeil dans le man donne : -s maximum size of stack segment (in kbytes)

ok donc disons que par défaut la taille est de 24 bits d'adressage.. C'est bon comme ça ?
16/02/2007, 16h17
crocodilex

Citation:

Envoyé par souviron34

ok donc disons que par défaut la taille est de 24 bits d'adressage.. C'est bon comme ça ?

24 bits cela fait 16 Mo. Une pile allouée à un processus dépasse rarement les quelques kilo octets. Donc je suis assez surpris par cette valeur que tu avances. Ou alors je n'ai rien compris à ton raisonnement... 8O
16/02/2007, 16h37
souviron34

je fais juste un petit calcul :

ça plante à 2^24 appels...

Donc il me semble que au minimum (sans compter l'adresse de la variable) il y a 2^24 emplacements sur la pile... (par défaut), c'est tout ce que je dis.. (sans doute au moins 2 fois plus, à cause de l'adresse de la variable).

j'ai essayé côté Linux et côté Windows avec cygwin. Même résultat. hegros a sans doute eu le même résultalt.

j'essaye de trouver une explication mesurable car il doit y en avoir une..

mais comme je suis nul en calcul de bits etc.. peut-être me trompe-je.. :oops:

Et pour le nombre maximal pour la factorielle, ça doit suffire dans la quasi-totalité des cas, non ?
16/02/2007, 23h46
Thierry Chappuis

Citation:

Envoyé par souviron34

je fais juste un petit calcul :

ça plante à 2^24 appels...

Donc il me semble que au minimum (sans compter l'adresse de la variable) il y a 2^24 emplacements sur la pile... (par défaut), c'est tout ce que je dis.. (sans doute au moins 2 fois plus, à cause de l'adresse de la variable).

j'ai essayé côté Linux et côté Windows avec cygwin. Même résultat. hegros a sans doute eu le même résultalt.

j'essaye de trouver une explication mesurable car il doit y en avoir une..

mais comme je suis nul en calcul de bits etc.. peut-être me trompe-je.. :oops:

Et pour le nombre maximal pour la factorielle, ça doit suffire dans la quasi-totalité des cas, non ?

J'aimerais bien voir le code assembleur généré pour MaFonction(), chez toi.

Thierry
17/02/2007, 00h55
souviron34

je posterais ça demain ;-)

la taille du stack par défaut sur la plupart des U*x 32 bits est 8192 Kb (soit 8 Mb… (= 2^23)…
c'est un paramètre la plupart du temps modifiable via ulimit.

le coût sur la pile d'un appel récursif dépend de l'ABI de l'OS sur le processeur cible, du compilateur choisi et des optimisations demandées…

discuter de la profondeur de récusion que l'on atteindre dans le contexte de la fonction factorielle dont les résultats intermédiaires dépassent rapidement la taille des nombres que le processeur peut gérer en natif, a-t-il un grand intérêt ?

comme déjà dit plus haut, si vous avez besoin de très grands nombres, utilisez une bibliothèque adhoc :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
 
#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>
 
// cc -o fact -I/opt/local/include -L/opt/local/lib -lgmp fact.c
 
char *fact(unsigned long int inNumber, char *inBuffer, size_t inMaxBufSize)
{
    mpz_t r ;
 
    if (inBuffer == NULL) {
       inBuffer = calloc(inMaxBufSize, sizeof(char)) ;
       if (inBuffer == NULL) 
           return NULL ;
    }
 
    mpz_init(r) ;
    mpz_fac_ui (r, inNumber) ;
 
    gmp_snprintf (inBuffer, inMaxBufSize, "%Zd", r) ;
 
    return inBuffer ;
}
 
#define BSIZE (100000000)
 
int main(int argc,char **argv)
{
	char *buffer = calloc( BSIZE, sizeof(char)) ;
 
	char *s ;
 
	if (argc > 1)	{
		--argc ;
		while (*++argv) {
			unsigned int n = atoi(*argv) ;
			s = fact(n, buffer, BSIZE) ;
			printf("%d!= %s\n",n,s) ;
		}
	}
	else {
		char line[32] ;
 
		while (fgets(line, 32, stdin)) {
			if (0 == strcmp(line,".\n"))
				break ;
 
			unsigned int n = atoi(line) ;
			s = fact(n, buffer, BSIZE) ;
			printf("%d!= %s\n",n,s) ;
		}
	}
	return 0 ;
}

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
% cc -o fact -I/opt/local/include -L/opt/local/lib -lgmp fact.c
% time jot 40 1 | ./fact 
1!= 1
2!= 2
3!= 6
4!= 24
5!= 120
6!= 720
7!= 5040
8!= 40320
9!= 362880
10!= 3628800
11!= 39916800
12!= 479001600
13!= 6227020800
14!= 87178291200
15!= 1307674368000
16!= 20922789888000
17!= 355687428096000
18!= 6402373705728000
19!= 121645100408832000
20!= 2432902008176640000
21!= 51090942171709440000
22!= 1124000727777607680000
23!= 25852016738884976640000
24!= 620448401733239439360000
25!= 15511210043330985984000000
26!= 403291461126605635584000000
27!= 10888869450418352160768000000
28!= 304888344611713860501504000000
29!= 8841761993739701954543616000000
30!= 265252859812191058636308480000000
31!= 8222838654177922817725562880000000
32!= 263130836933693530167218012160000000
33!= 8683317618811886495518194401280000000
34!= 295232799039604140847618609643520000000
35!= 10333147966386144929666651337523200000000
36!= 371993326789901217467999448150835200000000
37!= 13763753091226345046315979581580902400000000
38!= 523022617466601111760007224100074291200000000
39!= 20397882081197443358640281739902897356800000000
40!= 815915283247897734345611269596115894272000000000
 
real    0m0.028s
user    0m0.003s
sys     0m0.018s

Code:

1
2
3
4
5
6
7
8
9
10
11
 
time ./fact 10000
 
10000!= 2846259680917054518906413212119868890 ...
... un nombre de + de 35600 chiffres
...
0000000000000000000000000000
 
real    0m0.042s
user    0m0.025s
sys     0m0.011s

17/02/2007, 11h04
Médinoc

La taille de pile par défaut est d'1Mo sous Windows (source : MSDN)

Citation:

Envoyé par JeitEmgie

la taille du stack par défaut sur la plupart des U*x 32 bits est 8192 Kb (soit 8 Mb… (= 2^23)…
c'est un paramètre la plupart du temps modifiable via ulimit.

OK c'est donc ça...

Citation:

mujigka a écrit :

J'aimerais bien voir le code assembleur généré pour MaFonction(), chez toi.

OK voilà (j'ai enlevé le printf) :
Code:

1 2 cc ./Test.c -S -o ./test1
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 .file "Test.c" .version "01.01" gcc2_compiled.: .text .align 4 .type MaFonction,@function MaFonction: pushl %ebp movl %esp, %ebp subl $8, %esp movl 8(%ebp), %eax movl 12(%ebp), %edx movl %eax, -8(%ebp) movl %edx, -4(%ebp) fldl -8(%ebp) fld1 faddp %st, %st(1) fstpl -8(%ebp) subl $8, %esp pushl -4(%ebp) pushl -8(%ebp) call MaFonction addl $16, %esp leave ret .Lfe1: .size MaFonction,.Lfe1-MaFonction .align 4 .globl main .type main,@function main: pushl %ebp movl %esp, %ebp subl $24, %esp movl $0, -8(%ebp) movl $1072693248, -4(%ebp) subl $8, %esp pushl -4(%ebp) pushl -8(%ebp) call MaFonction addl $16, %esp fstpl -16(%ebp) movl $0, %eax leave ret .Lfe2: .size main,.Lfe2-main .ident "GCC: (GNU) 2.96 20000731 (Red Hat Linux 7.3 2.96-110)"

19/02/2007, 08h53
argon

Bonjour tout le monde

Ca fonctionne.

Je devais le faie en itératif pas en récusif.

Merci

Cordialement

A bientôt