Codage C++ de Factoriel d'un nombre entier

Version imprimable

22/10/2007, 21h02
theserialkiller10

Codage C++ de Factoriel d'un nombre entier
Bonjour,

Voila je voudrais savoir comment donner le resultat d'un nom factoriel en C++

voila l'algo
Code:

1 2 3 4 5 6 7 resultatFact : entier //init à 1 debut POUR i de 1 à valeur FAIRE DEBUT resultatFact = resultatFact * i ; FINPOUR fin
moi je pense faire comme sa mais je ne sais pas si c'est la meilleure solution

codage
Code:

1 2 3 4 5 6 int i ; int valeur ; int resultatFact = 1 ; for(i = 1; i <= valeur){ resultatFact = resultatFact * i ; }
désole pour lecriture je ne peu pas activé le code html

merci d'avance de votre aide

Cordialement Arnaud
22/10/2007, 21h31
theserialkiller10
Voila j'ai modifier mon code j'obtient sa

Codage
Code:

1 2 3 4 5 6 7 int valeur = 10 ; int resultatFact = 1 ; int i ; for(i = 1; i <= valeur; i++) { resultatFact = resultatFact * i ; }
voila et a koi sert le i++ je ne sais pas trop et j'aimerai savoir merci de votre aide

Cordialement Arnaud
22/10/2007, 22h25
aoyou
Oui, c'est bien. Encadre le d'une fonction et ce sera parfait.
Code:

1 2 3 4 5 6 7 8 int fact (int valeur) { int resultatFact = 1; for(int i = 1; i <= valeur; i++) { resultatFact *= i; } return resultatFact; }
i++ est équivalent à i += 1
i += a est équivalent à i = i + a

Tu peux aussi coder la factorielle de manière récursive...
23/10/2007, 00h03
koala01
Salut,

Tous les langages nécessitent de savoir de quelle valeur faire varier une variable pour les boucle incrémentales...

Certains permettent de dire qu'il faut prendre "toutes les valeurs comprises entre (x et y), mais ce n'est pas là le problème :D

Le C et le C++ fournissent une série de raccourcis régulièrement utilisés pour représenter les opérations de base (addition, soustraction, multiplication et division, mais aussi "incrémentation" (addition de 1) et "décrémentation" (soustraction de 1))

Ces raccourcis sont
- Pour l'addition x+=valeur_a_ajouter (équivalent à x = x + valeur_a_ajouter)
  - i++ pour la "post incrémentation"
  - ++i pour la "pré incrémentation"
- Pour la soustraction x-=valeur_a_soustraire (équivalent à x=x - valeur_a_soustraire)
  - i-- pour la "post décrémentation"
  - --i pour la "pré dércrémentation
- Pour la multiplication x*=multiplicateur (équivalent à x = x * multiplicateur)
- Pour la division x/=diviseur (équivalent à x = x / diviseur)
à noter qu'il y a une nuance de taille entre pré et post incrémentation/décrémentation, mais que ca sort du contexte du problème et que tu reste malgré tout tout à fait libre d'utiliser l'équivalent quand il y en a :D

Citation:

Envoyé par aoyou

Tu peux aussi coder la factorielle de manière récursive...

Heuuu... Oui, mais non...

Oui, dans le sens où il est tout à fait possible de le faire,

Non dans le sens où la récursivité fait partie de ces techniques qui sont forts utiles quand elles sont nécessaires et catastrophique quand elles sont utilisées à mauvais escient...

Elle est indispensable pour une gestion correcte et évolutive des "tours de Hannoï", et donc très utile dans ce cas là, mais peut tout à fait être remplacée de manière très avantageuse par une simple boucle pour ce qui est des calculs de factorielles, d'exponentielles et autre fonctions similaires...

Dans de tels cas, cela revient à sacrifier inutilement des ressources qui pourraient être tellement utiles ailleurs (et c'est d'ailleurs le seul cas pour lequel j'estime utile de penser en "temps d'exécution" plutot qu'en "nombre d'exécution" :D)

@theserialkiller10 ==>Si tu t'intéresse à la récursivité, tu peux aller voir sur mon site( @aoyou ==> impregne toi peut-être du contenu des §4 et §15 de la dite page :D)
23/10/2007, 02h02
droggo

Luo,

Je suis d'accord avec koala01 : la récursivité est un belle chose, mais mais quand on peut s'en passer sans trop de difficulté, il vaut mieux la laisser de côté.

Le calcul de la factorielle est un cas typique où il faut faire de l'itératif, et c'est hélas un exemple classique dans les cours comme exercice d'application de la récursivité.

ps : on s'en passe aussi très facilement pour les tours de Hanoi. :)
23/10/2007, 02h02
nicroman
Marrant... moi j'aurai codé la factorielle un peu différemment...
Et, j'ai l'impression, un peu plus juste... Parceque dans le code précedant... 0! = 1 !!!
Code:

1 2 3 4 5 6 7 long fact(long n) { long ret = n--; while (n>1) ret *= n--; return ret; }
A noter que si ca se trouve le compilo fait exactement ça....
23/10/2007, 07h52
screetch

Citation:

Envoyé par Wikipedia

Par exemple :

* 1! = 1
* 2! = 1 × 2 = 2
* 3! = 1 × 2 × 3 = 6
* 10! = 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 × 10 = 3 628 800

Par convention :

0! = 1

La définition de la factorielle sous forme de produit rend naturelle cette convention puisque 0! est un produit vide, c'est-à-dire réduit à l'élément neutre de la multiplication. Cette convention est pratique pour deux points :

* Elle permet une définition récursive de la factorielle : (n+1)! = n! × (n+1) pour tout n.
* Elle permet à de nombreux identifés en combinatoire d'être valides pour des tailles nulles. En particulier, le nombre d'arrangements ou de permutations de l'ensemble vide est égal à 1.

quand a la recursivité, je n'ai pas de compilo sous la paluche mais la version recursive genere le meme code assembleur (a des details prets)
23/10/2007, 11h04
aoyou

Citation:

@aoyou ==> impregne toi peut-être du contenu des §4 et §15 de la dite page )

Oh non merci, je n'ai pas besoin de conseil sur ce point là :P. Je proposais juste cela à titre d'exercice. C'est à priori un exercice de base qui permet de facilement aborder la récursivité mais ce n'est pas si simple.

La définition de la factorielle est très simple. On en déduit donc une version récursive naturellement très simple (et encore plus simple que la version itérative) mais qui n'est effectivement pas du tout efficace en terme de pile et d'exécution.

Il existe une seconde version récursive qui elle est beaucoup plus efficace, et comme le sous-entend screetch, que le compilateur peut dérécursifier. Le code assembleur généré est alors à peu près le-même.

Enfin, voilà, ça aurait pu être un bon exercice pour notre ami, si ça l'intéresse bien sûr. Et au final, on aurait pu conclure qu'il faut quand même plus souvent privilégier l'itératif, mais c'est tellement beau la récursivité.

Bonne journée à tous,
23/10/2007, 12h17
koala01

Citation:

Envoyé par screetch

quand a la recursivité, je n'ai pas de compilo sous la paluche mais la version recursive genere le meme code assembleur (a des details prets)

Normalement, non...

Le propre d'une fonction récursive est qu'il s'agit d'une fonction qui s'appelle elle-même...

Le compilateur n'a normalement aucun moyen de déterminer le nombre de fois qu'il faudrait faire apparaître les instructions contenue par cette fonction, étant donné que sa seule possibilité serait de "dérouler" la boucle

Citation:

Envoyé par aoyou

Oh non merci, je n'ai pas besoin de conseil sur ce point là :P. Je proposais juste cela à titre d'exercice. C'est à priori un exercice de base qui permet de facilement aborder la récursivité mais ce n'est pas si simple.

Pourquoi faire simple quand on peut faire compliqué :question:

Je préfèrerais fortement que l'on propose le problème des tours de Hanoï pour introduire la récursivité...

Citation:

Envoyé par aoyou

Enfin, voilà, ça aurait pu être un bon exercice pour notre ami, si ça l'intéresse bien sûr. Et au final, on aurait pu conclure qu'il faut quand même plus souvent privilégier l'itératif, mais c'est tellement beau la récursivité.

C'est en effet très beau, la récursivité...

Et c'est, quelque part la raison pour laquelle il faut respecter l'introduction de cette manière de faire:

Le fait de l'introduire en parlant de la factorielle ou de l'exponentielle peut donner, à tord, l'impression que c'est un concept tout à fait inutile, alors qu'il y a des cas dans lesquels tu ne peux pas envisager sereinement un algorithme itératif susceptible de s'adapter au plus grand nombre de situations...

Citation:

Envoyé par droggo

<snip>
ps : on s'en passe aussi très facilement pour les tours de Hanoi. :)

Si tu décide de "figer" le nombre de disques utilisés, oui, de fait, tu peux assez facilement te passer de la récursivité...

Par contre, si tu veux obtenir quelque chose qui fonctionne aussi bien avec 3, 9 ou 12 disques (et, pourquoi pas, avec 64 :roll:), tu n'arrivera pas *facilement* à t'en passer... Ou du moins, pas sans passer par la "multiplication des petits code", à l'image de ce que quelqu'un a fait, paraît il, avec les pains il y a deux mille ans :P
23/10/2007, 12h26
droggo

Leu,

Citation:

Envoyé par koala01

Si tu décide de "figer" le nombre de disques utilisés, oui, de fait, tu peux assez facilement te passer de la récursivité...

Par contre, si tu veux obtenir quelque chose qui fonctionne aussi bien avec 3, 9 ou 12 disques (et, pourquoi pas, avec 64 :roll:), tu n'arrivera pas *facilement* à t'en passer... Ou du moins, pas sans passer par la "multiplication des petits code", comme quelqu'un l'a fait, paraît il, avec les pains il y a deux mille ans :P

Non, l'algorithme itératif pour les tours de Hanoi est simple, et s'écrit sans problème pour un nombre quelconque de disques (enfin, quelconque... avec les mêmes limitations que la version récursive, ça explose rapidement le temps de calcul :)).

Je le concède, ça demande un peu plus de code qu'en récursif, mais ça ne va pas bien loin, et il n'y a pas "multiplication des petits code" pour autant.

Ceci étant dit, oui, les tours de Hanoi devraient être préférées à la factorielle pour introduire la récursivité. :)
23/10/2007, 12h45
screetch

Citation:

Envoyé par koala01

Normalement, non...

Le propre d'une fonction récursive est qu'il s'agit d'une fonction qui s'appelle elle-même...

attention koala, ne me tente pas... arf je suis sous linux, j'ai un compilo, c'est parti ^^

code source :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
int factorielle_iteratif(int val)
{
	int result = 1;
	for(int i = val; i > 0; --i)
		result *= i;
	return result;
}
 
int factoriel_recursif(int val)
{
	if(val == 0)
		return 1;
	else
		return val*factoriel_recursif(val-1);
}

compilé avec :

gcc -c -O2 fac.cc
objdump -d fac.o

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
0000000000000000 <_Z20factorielle_iteratifi>:
   0:   85 ff                   test   %edi,%edi
   2:   b8 01 00 00 00          mov    $0x1,%eax
   7:   7e 0f                   jle    18 <_Z20factorielle_iteratifi+0x18>
   9:   0f 1f 80 00 00 00 00    nopl   0x0(%rax)
  10:   0f af c7                imul   %edi,%eax
  13:   83 ef 01                sub    $0x1,%edi
  16:   75 f8                   jne    10 <_Z20factorielle_iteratifi+0x10>
  18:   f3 c3                   repz retq 
  1a:   66 0f 1f 44 00 00       nopw   0x0(%rax,%rax,1)
 
0000000000000020 <_Z18factoriel_recursifi>:
  20:   85 ff                   test   %edi,%edi
  22:   b8 01 00 00 00          mov    $0x1,%eax
  27:   74 0f                   je     38 <_Z18factoriel_recursifi+0x18>
  29:   0f 1f 80 00 00 00 00    nopl   0x0(%rax)
  30:   0f af c7                imul   %edi,%eax
  33:   83 ef 01                sub    $0x1,%edi
  36:   75 f8                   jne    30 <_Z18factoriel_recursifi+0x10>
  38:   f3 c3                   repz retq

que ce soit une lecon pour ceux qui se pretendent plus malin qu'un compilo ^^
(je ne dis pas cela pour toi koala, mais je vois souvent des posts qui trainent sur des mecs qui se croient plus fort que les 3GHz de ma machine)

Hé bien, cela signifie donc que cela dépend de l'option d'optimisation fournie...

Mon code:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
int FactIte(int nb)
{
    int total=1;
    for (int i=1;i<=nb;i++)
        total*=i;
    return total;
}
int FactRecur(int nb)
{
    if(nb!=1)
        nb*=(FactRecur(nb-1));
    return nb;
}

compilé avec gcc -c main.cpp

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
00000000 <__Z7FactItei>:
   0:	55                   	push   %ebp
   1:	89 e5                	mov    %esp,%ebp
   3:	83 ec 10             	sub    $0x10,%esp
   6:	c7 45 f8 01 00 00 00 	movl   $0x1,-0x8(%ebp)
   d:	c7 45 fc 01 00 00 00 	movl   $0x1,-0x4(%ebp)
  14:	eb 0e                	jmp    24 <__Z7FactItei+0x24>
  16:	8b 45 f8             	mov    -0x8(%ebp),%eax
  19:	0f af 45 fc          	imul   -0x4(%ebp),%eax
  1d:	89 45 f8             	mov    %eax,-0x8(%ebp)
  20:	83 45 fc 01          	addl   $0x1,-0x4(%ebp)
  24:	8b 45 fc             	mov    -0x4(%ebp),%eax
  27:	3b 45 08             	cmp    0x8(%ebp),%eax
  2a:	7e ea                	jle    16 <__Z7FactItei+0x16>
  2c:	8b 45 f8             	mov    -0x8(%ebp),%eax
  2f:	c9                   	leave  
  30:	c3                   	ret    
  31:	90                   	nop    
 
00000032 <__Z9FactRecuri>:
  32:	55                   	push   %ebp
  33:	89 e5                	mov    %esp,%ebp
  35:	83 ec 04             	sub    $0x4,%esp
  38:	83 7d 08 01          	cmpl   $0x1,0x8(%ebp)
  3c:	74 0e                	je     4c <__Z9FactRecuri+0x1a>
  3e:	8b 45 08             	mov    0x8(%ebp),%eax
  41:	83 e8 01             	sub    $0x1,%eax
  44:	89 04 24             	mov    %eax,(%esp)
  47:	e8 e6 ff ff ff       	call   32 <__Z9FactRecuri>
  4c:	8b 45 08             	mov    0x8(%ebp),%eax
  4f:	c9                   	leave  
  50:	c3                   	ret    
  51:	90                   	nop

compilé avec gcc -O2 -c main.cpp

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
 
00000000 <__Z7FactItei>:
   0:	55                   	push   %ebp
   1:	b8 01 00 00 00       	mov    $0x1,%eax
   6:	89 e5                	mov    %esp,%ebp
   8:	8b 4d 08             	mov    0x8(%ebp),%ecx
   b:	85 c9                	test   %ecx,%ecx
   d:	7e 12                	jle    21 <__Z7FactItei+0x21>
   f:	ba 01 00 00 00       	mov    $0x1,%edx
  14:	83 c1 01             	add    $0x1,%ecx
  17:	0f af c2             	imul   %edx,%eax
  1a:	83 c2 01             	add    $0x1,%edx
  1d:	39 ca                	cmp    %ecx,%edx
  1f:	75 f6                	jne    17 <__Z7FactItei+0x17>
  21:	5d                   	pop    %ebp
  22:	c3                   	ret    
  23:	90                   	nop    
  24:	8d b6 00 00 00 00    	lea    0x0(%esi),%esi
  2a:	8d bf 00 00 00 00    	lea    0x0(%edi),%edi
 
00000030 <__Z9FactRecuri>:
  30:	55                   	push   %ebp
  31:	89 e5                	mov    %esp,%ebp
  33:	8b 45 08             	mov    0x8(%ebp),%eax
  36:	5d                   	pop    %ebp
  37:	c3                   	ret    
  38:	90                   	nop    
  39:	8d b4 26 00 00 00 00 	lea    0x0(%esi),%esi

compilé avec gcc -O3 -c main.cpp

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
00000000 <__Z7FactItei>:
   0:	55                   	push   %ebp
   1:	b8 01 00 00 00       	mov    $0x1,%eax
   6:	89 e5                	mov    %esp,%ebp
   8:	8b 4d 08             	mov    0x8(%ebp),%ecx
   b:	85 c9                	test   %ecx,%ecx
   d:	7e 12                	jle    21 <__Z7FactItei+0x21>
   f:	ba 01 00 00 00       	mov    $0x1,%edx
  14:	83 c1 01             	add    $0x1,%ecx
  17:	0f af c2             	imul   %edx,%eax
  1a:	83 c2 01             	add    $0x1,%edx
  1d:	39 ca                	cmp    %ecx,%edx
  1f:	75 f6                	jne    17 <__Z7FactItei+0x17>
  21:	5d                   	pop    %ebp
  22:	c3                   	ret    
  23:	90                   	nop    
  24:	8d b6 00 00 00 00    	lea    0x0(%esi),%esi
  2a:	8d bf 00 00 00 00    	lea    0x0(%edi),%edi
 
00000030 <__Z9FactRecuri>:
  30:	55                   	push   %ebp
  31:	89 e5                	mov    %esp,%ebp
  33:	8b 45 08             	mov    0x8(%ebp),%eax
  36:	5d                   	pop    %ebp
  37:	c3                   	ret    
  38:	90                   	nop    
  39:	8d b4 26 00 00 00 00 	lea    0x0(%esi),%esi

Dans le premier cas, on remarque qu'il effectue réellement l'appel de la fonction, alors que si l'on demande une optimisation, il la considère comme une boucle (qui a dit que le compilo était un idiot :question: :oops:)

Moralité: j'ai parlé un peu vite, et je reconnais - à moitié - mon erreur, car l'absence d'options de compilation me donne raison :D

23/10/2007, 13h33
screetch

je dirai que l'absence d'options de compilation te donne raison a 1/3 ^^

cela depend aussi sans doute de la facon dont on ecrit la fonction, boucle for(top to bottom) ou (bottom to top) car on obtient des resultats differents.

connaissant le resultat a atteindre (obtenir deux codes identiques) j'avoue que j'ai orienté l'ecriture vers ce resultat la :)

mais n'empeche!! ;)
23/10/2007, 13h35
screetch

ps : la version en -O3 donne un disassembly faux, en tous cas pour la version recursive... enfin, de tete, je me dis que ca doit pas tres bien marcher
23/10/2007, 13h56
PierroElMito

ça doit être parce que le compilo a tellement optimisé qu'il a déjà calculé le résultat (car c'est un appel de fonctions sur une valeur immédiate)!
23/10/2007, 14h35
koala01

Citation:

Envoyé par screetch

je dirai que l'absence d'options de compilation te donne raison a 1/3 ^^

Bah, moitié... 1/3... si tu t'arrête à des détaux...:D:roll:

Citation:

cela depend aussi sans doute de la facon dont on ecrit la fonction, boucle for(top to bottom) ou (bottom to top) car on obtient des resultats differents.

connaissant le resultat a atteindre (obtenir deux codes identiques) j'avoue que j'ai orienté l'ecriture vers ce resultat la :)

mais n'empeche!! ;)

Là, sur ce coup là, j'ai simplement codé mes fonctions sans faire attention à ce que je voulais réellement obtenir (hormis, bien sur, la justesse de l'algorithme...)

La démarche est moins partisane :D

:dehors:
23/10/2007, 15h02
aoyou

Eh bien, je ne pensais pas que gcc se débrouillait aussi bien. En fait, je pensais à une troisième version de la factorielle codée de manière récursive terminale. En regardant le fichier assembleur généré avec l'option -S de gcc, seule cette version devient itérative. La version classique reste toujours récursive. Mais je ne pensais pas qu'il était encore capable par la suite de l'optimiser à ce point.

Du coup, vu que gcc arrive à optimiser des fonctions récursives même non terminales, j'ai regardé ce que ça donnait pour Fibonacci avec objdump cette fois-ci :D. Mais là dommage, il n'y a que la version récursive terminale qu'il arrive à optimiser (un seul appel récursif au lieu de deux).

Mais quand même un grand bravo à gcc pour la factorielle. Il n'y a pas de doute, comme le dit screetch, le compilateur est toujours plus fort que nous.
23/10/2007, 15h11
koala01

C'est en substance ce que je maintiens aussi sur la "fameuse" discution optimisation de la vitesse pure

Mon avis personnel a toujours été qu'il était préférable d'optimiser l'algorithme afin de restreindre le nombre de fois qu'un groupe d'instructions est effectué, et de laisser le champs au compilateur pour ce qui est de l'optimisation du résultat... il est beaucoup plus doué que nous sur ce point :P

[EDIT] Et je reconnais que le résultat obtenu dés le moment où l'on demande l'optimisation du code a quelque chose de bluffant ;):P:roll:

en fait la factorielle se prete bien a une forme d'optimisation qui est une recursivité quasi terminale.

pour factorielle, on peut dire que factorielle(n) = operation(factorielle(n-1))
et si operation est suffisemment simple, cela peut etre optimisé grace a un accumulateur de resultat (de la forme

factorielle(n) = factorielle et operation(n, 1)
factorielle et operation(n, resultat) = factorielle et operation(n-1, operation(resultat) )

on ajoute virtuellement une seconde variable a l'appel de fonction qui sert 'accumulateur et va contenir le resultat, et dans ce cas on a transformé une recursivité non terminale en recursivité terminale.

reste a derouler la recursivité terminale pour optenir le resultat en iteratif

soit
Code:

1 2 3 4 5 6 7 8 9 10 11 int accum = 1; //actorielle et operation(n, 1) again: if(n > 0) //condition terminale { //corps de factorielle accum = n * accum; --n; goto again; // c'est du pseudo code pour remplacer l'appel recursif, on fait juste un goto } return accum;
ce qui est strictement equivalent a la boucle while plus haut

donc en deux etapes, gcc a trouvé la version iterative.

comme il existe un ALGORITHME permettant de passer du premier au second, il n'y a aucun doute que gcc y arrivera mieux que l'oeil humain; il reperera plus facilement les constructions permettant cette optimisation.

23/10/2007, 19h34
theserialkiller10

Merci pour vos aide je vais regarder de plus près tou ce ke vous m'avais mis

encore merci

Cordialement

Arnaud
24/10/2007, 07h38
screetch

ah j'ai trouvé pourquoi ca donne un assembly douteux! koala tu as une petite faute dans ton programme dans la version recursive, il faut soit que tu rajoutes return nb*fac(n-1) ou bien nb *= fac(n-1) car sinon tu as une instruction qui ne fait rien au milieu
24/10/2007, 16h18
koala01

Citation:

Envoyé par screetch

ah j'ai trouvé pourquoi ca donne un assembly douteux! koala tu as une petite faute dans ton programme dans la version recursive, il faut soit que tu rajoutes return nb*fac(n-1) ou bien nb *= fac(n-1) car sinon tu as une instruction qui ne fait rien au milieu

:oops: Une erreur de copie... Corrigée :D

mais c'est quoi du coup l'assembleur correspondant ?

quoi qu'il en soit je vois que visual C++ ne genere pas des fonctions iteratives sur ces exemples :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int factorielle_recursive1(int value)
{
10001000  push        esi  
	if(value > 1)
10001001  mov         esi,dword ptr [esp+8] 
10001005  cmp         esi,1 
10001008  jle         factorielle_recursive1+1Bh (1000101Bh) 
		value *= factorielle_recursive1(value-1);
1000100A  lea         eax,[esi-1] 
1000100D  push        eax  
1000100E  call        factorielle_recursive1 (10001000h) 
10001013  add         esp,4 
10001016  imul        eax,esi 
10001019  pop         esi  
}
1000101A  ret