Projet électronique FPGA #7 : Calcul de Factorielle – n!

Domaines d’application:

• Théorie des probabilités: Pour N objets distincts, il existe N! Combinaisons ou permutations différentes d’arranger N objets (Ex: Avec trois caracatères A, B et C, il existe 3! = 6 permutations possibles)
• Algorithmique: Suite de Fibonacci en apprentissage de la récursivité
• Mathématique:
  • Calculs de Développements limités: Approximations des fonctions usuelles (sin, cos, exp,…)
  • Calcul des constantes des coefficients binomiaux dans la formule du binôme de newton
  • Formule des polynômes de Bernstein, la construction géométrique de Bézier
• Etc

Calcule du nombre de bit de sortie du composant:

On considère les paramètres suivantes :

• d_in : la valeur entière à l’entrée (d_in=N)
• n_in : le nombre des bits de l’entrée
• d_out : la valeur entière à la sortie est égale à la factorielle de la donnée à l’entrée (d_out=d_in ! =N !)
• n_out : le nombre des bits de la sortie

Dans le cas pratique le nombre de bits à l’entrée est connu (ou bien la valeur maximale que peut prendre l’entrée), il reste à déterminer le nombre des bits à la sortie (ou valeur maximale de sortie). Rappel : lorsque d’in est codée sur n_in bits, l’entrée peut varier entre 0 et 2^n_in-1 (idem pour la sortie). Autrement dit la valeur maximale à l’entre est égale à 2^n_in-1.Exemple : On suppose que n_in=5. Dans ce cas, la valeur maximale à l’entrée est égale à 2^5-1=31.

D’où, la valeur maximale de sortie d_out=d_in !=31 != 8222838654177922817725562880000000.

On peut écrire la valeur maximale de la sortie sous la forme suivante :

2^n_out-1 => n_out=log2(d_out+1)

n_out=log2(31!+1)=log2(8222838654177922817725562880000000+1)= 112.6633

Pour être sure que la sortie ne déborde pas, on prend la valeur 113.

On peut obtenir la valeur 113 en utilisant la fonction mattlab d’arrondie Round(), mais la fonction floor()+1 est plus sure. Ex: round(112.3)=112, floor(112.3)+1=113.

Résumé:

nin                  2nin-1               nout
1                    1                      2
2                    3                      3
3                    7                     13
4                   15                     41
5                   31                    113
6                   63                    290
7                  127                    710
8                  255                    Inf

Comment choisir le nombre des bits du Multiplieur ?

Le cœur du composant qui calcule la factorielle de n est composée d’un multiplieur. La première entrée du multiplieur est sur 5 bits, l’entrée de réaction est sur 108 bits, la sortie sur 113 bits égal à 108+5. La deuxième entrée est le résultat précédent du multiplieur, autrement dit la sortie actuelle décalée d’une période d’horloge. Notre approche consiste l’Implimentation de la formule de la factorielle suivante :

n! =p*(p+1)*(p+2)*(p+3)*…*(n-1)*n, avec p=1   

n!=1*2*3*4*5*…*(n-1)*n

n!=((((1*2)*3)*4)*5)*…*(n-1)*n

Il est clair que n! Est une multiplication récursive (résultat précédent x donnée actuelle) de n itérations des valeurs successives (1, 2,3,…n) variant de 1 à n. Pour une entrée sur 5 bits, le nombre des bits de la sortie est égal à 113. Ci-dessous le schéma illustrant le circuit multiplieur:

Schéma de principe de la factorielle de n – n! en utilisant l’approche du compteur:

Signaux de l’entité:

• d_in : la valeur entière à l’entrée sur 5 bits
• Clk: Horloge maitre
• d_out : la valeur entière à la sortie est égale à la factorielle de la donnée à l’entrée sur 113 bits
• Rst : Entrée d’initialisation activée niveau haut
• Z^-1: Retard d’un cycle d’horloge (décalage d’une période de l’entrée par rapport à la sortie du composant Z^-1
• Compteur 5 bits: Compteur à rechargement sur 5 bits: l’entrée peut prendre des valeurs entre 1 et 31 (la factorielle de 0! =1)
• Initialisation: Mise à ‘1’ des divers composants  à la fin du calcule et la génération du signal Data_valid (ou DoutReady)  indiquant la présence du résultat dans le bus de sortie Dout