Discussion :

[TrexXx]

Bonsoir,
Après mon post sur la racine carrée, je m'intéresse à la factorielle.
J'ai trouvé plusieurs algo qui les calculent mais je ne les comprends pas très bien et j'ai donc besoin de votre aide.
L'algo le plus rapide (d'après mes recherches) parle de factorisation des nombres premiers, ce que fait apparemment la lib GMP en C : http://gmplib.org/manual/Factorial-A...rial-Algorithm mais je comprends pas exactement comment le mettre en place, surtout au niveau de la récursivité, quelles sont les conditions d'arrêt ?
La deuxième 'famille' d'algos dont j'ai entendu parler sont ceux du type : 'SplitRecursive', mais je ne trouve pas de liens qui explique réellement comment fonction ces algos ...
Merci à tous ceux qui ont des pistes et qui pourront m'aider sur ce sujet

[droggo]

Nao,

Compte tenu du sujet à propos des racines carrées, tu veux manipuler des nombres de l'ordre de grandeur de 1000 chiffres.

As-tu fait une évaluation du nombre de chiffres de la factorielle de tels nombres ?

[TrexXx]

Je sais bien que la factorielle de tels nombres est énorme, je ne veux pas calculer la factorielle de nombres si grands, je sais bien que c'est "impossible", mais la factorielle de nombres plus petits ! Et je veux essayer d'implémenter les 'meilleurs' algo, pour pouvoir calculer la factorielle du plus de nombres possible !

[droggo]

Voa,

Je sais bien que la factorielle de tels nombres est énorme, je ne veux pas calculer la factorielle de nombres si grands, je sais bien que c'est "impossible", mais la factorielle de nombres plus petits ! Et je veux essayer d'implémenter les 'meilleurs' algo, pour pouvoir calculer la factorielle du plus de nombres possible !

Ouf, ça me rassure, car je te voyais mal barré.

[SpiceGuid]

Il y a une implémentation diviser pour régner dans mon article sur les grands nombres, avec utilisation de la multiplication Karatsuba.

[TrexXx]

Ton article ? Celui que tu m'as donné dans le post sur la racine carrée ?

[FR119492]

Salut!
Une méthode peut-être un peu plus lente, mais beaucoup plus simple serait de partir de la fonction gamma, qui est disponible sur le site www.netlib.org, dans la bibliothèque slatec.
Jean-Marc Blanc

[TrexXx]

J'ai lu la partie de ton article sur la factorielle, et j'ai une petite question à propos de l'algo de permutation :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
let permutation_big n p =
  assert(0 <= p && p <= n);
  let rec product a b =
    if a = b then
      big_of_int a
    else if a + 1 = b then
      big_of_int (a * b)
    else 
      let ab2 = (a + b) / 2 in
      mult_big (product a ab2) (product (ab2+1) b)
  in
    if p = 0 then unit_big else product (n - p + 1) n;;

Je comprends pas la dernière ligne ? Quand est-ce qu'elle est exécutée en fait ?

Et cette méthode calculer la factorielle est-elle rapide (relativement aux autres bien sur !).

[SpiceGuid]

Code Objective-Caml :

Sélectionner tout - Visualiser dans une fenêtre à part

if p = 0 then unit_big else product (n - p + 1) n;;

• le nombre d'arrangements de p parmi n vaut 1 si p=0
• sinon il vaut le produit des entiers de n-p+1 à n

Quant à l'algorithme cette page détaille le calcul de sa complexité :

http://numbers.computation.free.fr/C...splitting.html

Il est d'autant plus rapide que tu as une multiplication rapide, avec une multiplication Karatsuba c'est surtout la mémoire qui va te limiter

[TrexXx]

Ok mais pourquoi ce test précis est-il mis après tout les autres ? Est ce un test qu'il faut faire après ou est-ce qu'il faut le faire en même temps ? C'est ca que je comprends pas très bien.
Merci pour ton aide.

[SpiceGuid]

C'est la même chose que ceci:

Code Objective-Caml :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
let rec product a b =
  if a = b then
    big_of_int a
  else if a + 1 = b then
    big_of_int (a * b)
  else 
    let ab2 = (a + b) / 2 in
    mult_big (product a ab2) (product (ab2+1) b)
 
let permutation_big n p =
  assert(0 <= p && p <= n);
  if p = 0 then unit_big else product (n - p + 1) n

[TrexXx]

Ok je te remercie pour tout

En fait une dernière petite question, après je te dérange plus, je comprends pas bien le but de la fonction product ?

[SpiceGuid]

product a b c'est le produit de tous les entiers dans l'intervalle [a,b].
Je n'en dirai pas plus, il faut lire le lien que j'ai donné ci-dessus.

[TrexXx]

Ok d'accord, je le lis de suite alors, je te remercie encore une fois pour ton temps

[Wachter]

Bonsoir,

La deuxième 'famille' d'algos dont j'ai entendu parler sont ceux du type : 'SplitRecursive', mais je ne trouve pas de liens qui explique réellement comment fonction ces algos ...
Merci à tous ceux qui ont des pistes et qui pourront m'aider sur ce sujet

Regarde ces codes source en Java et C# implémentant plusieurs fonctions de calcul rapide de la factorielle.
Cependant, si n est grand et tu désires calculer appoximativement sa factorielle, la formule de Stirling fera l'affaire.

Code Formule de Stirling :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
n! = (2 * Pi * n)^½ * (n / e)^n

--
Wachter