Algorithme factoriel plus efficace que la multiplication naïve

Je sais comment coder des factorielles en utilisant à la fois des méthodes itératives et récursives (par exemple, n * factorial(n-1)par exemple). J'ai lu dans un manuel (sans autre explication) qu'il existe un moyen encore plus efficace de coder des factorielles en les divisant de manière récursive.

Je comprends pourquoi cela peut être le cas. Cependant, je voulais essayer de le coder moi-même et je ne pense pas savoir par où commencer. Un ami m'a suggéré d'écrire d'abord les cas de base. et je pensais utiliser des tableaux pour que je puisse garder une trace des nombres ... mais je ne vois vraiment aucun moyen de concevoir un tel code.

Quel genre de techniques devrais-je effectuer des recherches?

Le meilleur algorithme connu consiste à exprimer la factorielle en tant que produit de puissances premières. On peut rapidement déterminer les nombres premiers ainsi que la bonne puissance pour chaque nombre premier en utilisant une approche par tamis. Le calcul de chaque puissance peut être effectué efficacement en utilisant des quadrillages répétés, puis les facteurs sont multipliés ensemble. Ceci a été décrit par Peter B. Borwein, De la complexité des facteurs de calcul , Journal of Algorithms 6 376–380, 1985. ( PDF ) En bref,peut être calculé en temps , comparé au temps requis pour l’utilisation de la définition.$n!$$O(n(\log n)^3\log \log n)$$\Omega(n^2 \log n)$

Le manuel a peut-être voulu dire que c'était la méthode diviser pour régner. On peut réduire les multiplications en utilisant le motif régulier du produit.$n-1$

Letnotez comme une notation pratique. Réarrangez les facteurs de tant que Supposons maintenant que pour un nombre entier . (Ceci est une hypothèse utile pour éviter des complications dans la discussion suivante, et l'idée peut être étendue au général .) Alorset en élargissant cette récurrence, Informatique1 ⋅ 3 ⋅ 5 ⋯ ( 2 n - 1 ) ( 2 n ) ! = 1 ⋅ 2 ⋅ 3 ⋯ ( 2 n ) ( 2 n ) ! = n ! ⋅ 2 n ⋅ 3 ⋅ 5 ⋅ 0 n ( 2 k ) ! = ( 2 k - 1 ) $n?$$1 \cdot 3 \cdot 5 \dotsm (2n-1)$$(2n)! = 1 \cdot 2 \cdot 3 \dotsm (2n)$n = 2 k k

$$(2n)! = n! \cdot 2^n \cdot 3 \cdot 5 \cdot 7 \dotsm (2n-1).$$ $n = 2^k$$k>0$$n$( 2 k ) ! = ( 2 2 k - 1 + 2 k - 2 + ⋯ + 2 0 ) k - 1 Π i = 0 ( 2 i$(2^k)! = (2^{k-1})!2^{2^{k-1}}(2^{k-1})?$( 2 k - 1 ) ? ( k - 2 ) + 2 k - 1 - 2 2 2 2 k - 2 2 2 k - $$(2^k)! = \left(2^{2^{k-1}+2^{k-2}+\dots+2^0}\right) \prod_{i=0}^{k-1} (2^i)? = \left(2^{2^k - 1}\right) \prod_{i=1}^{k-1} (2^i)?.$$ $(2^{k-1})?$et multiplier les produits partiels à chaque étape prend multiplications. Il s’agit d’une amélioration d’un facteur de près de sur multiplications en utilisant simplement la définition. Quelques opérations supplémentaires sont nécessaires pour calculer la puissance de , mais en arithmétique binaire, cela peut être effectué à moindre coût (selon ce qui est requis, il suffit d'ajouter un suffixe de zéros).$(k-2) + 2^{k-1} - 2$$2$$2^k-2$$2$$2^k-1$

Le code Ruby suivant implémente une version simplifiée de cela. Cela n'évite pas de recalculermême où il pourrait le faire:$n?$

def oddprod(l,h)
  p = 1
  ml = (l%2>0) ? l : (l+1)
  mh = (h%2>0) ? h : (h-1)
  while ml <= mh do
    p = p * ml
    ml = ml + 2
  end
  p
end

def fact(k)
  f = 1
  for i in 1..k-1
    f *= oddprod(3, 2 ** (i + 1) - 1)
  end
  2 ** (2 ** k - 1) * f
end

print fact(15)

Même ce code de premier passage améliore la trivialité

f = 1; (1..32768).map{ |i| f *= i }; print f

d'environ 20% lors de mes tests.

Avec un peu de travail, cela peut encore être amélioré, en supprimant également la nécessité que soit une puissance de (voir la discussion approfondie ).$n$$2$

Gardez à l'esprit que la fonction factorielle croît si rapidement que vous aurez besoin de nombres entiers de taille arbitraire pour tirer le meilleur parti de techniques plus efficaces que l'approche naïve. La factorielle de 21 est déjà trop grosse pour tenir dans un 64 bits unsigned long long int.

Pour autant que je sache, il n'y a pas d'algorithme pour calculer(factorielle de ) qui est plus rapide que de faire les multiplications.¹$n!$$n$

Cependant, l'ordre dans lequel vous effectuez les multiplications est important. La multiplication sur un entier de la machine est une opération de base qui prend le même temps, quelle que soit la valeur de cet entier. Mais pour des entiers de taille arbitraire, le temps nécessaire pour multiplier a et b dépend de la taille de a et b : un algorithme naïf fonctionne dans le temps (où est le nombre de chiffres de - quelle que soit la base de votre choix, le résultat est le même jusqu'à une constante multiplicative). Il existe des algorithmes de multiplication plus rapides , mais il existe une limite inférieure évidente de| x | x Ω ( | a | + | b | ) max ( |$\Theta(|a| \cdot |b|)$$|x|$$x$$\Omega(|a| + |b|)$puisque la multiplication doit au moins lire tous les chiffres. Tous les algorithmes de multiplication connus croissent plus rapidement que linéairement dans .$\max(|a|,|b|)$

Fort de ce contexte, l'article de Wikipedia devrait avoir un sens.

Étant donné que la complexité des multiplications dépend de la taille des entiers multipliés, vous pouvez gagner du temps en organisant les multiplications dans un ordre qui permet de multiplier les nombres. Cela fonctionne mieux si vous vous arrangez pour que les nombres soient à peu près de la même taille. La «division en deux» à laquelle votre manuel fait référence consiste en l’ approche suivante consistant à diviser pour mieux régner pour multiplier un ensemble (multi) d’entiers:

1. Organisez les nombres à multiplier (initialement, tous les nombres entiers de à ) en deux ensembles dont le produit a à peu près la même taille. C'est beaucoup moins cher que de faire la multiplication:(un ajout de machine).n | a ⋅ b | ≈ $1$$n$$|a \cdot b| \approx |a| + |b|$
2. Appliquez l'algorithme de manière récursive sur chacun des deux sous-ensembles.
3. Multipliez les deux résultats intermédiaires.

Voir le manuel GMP pour plus de détails.

Il existe même des méthodes plus rapides qui non seulement réorganisent les facteurs à mais divisent les nombres en les décomposant en une factorisation première et en réorganisant le produit très long résultant de la plupart des entiers petits. Je citerai simplement les références de l'article de Wikipedia: «Sur la complexité des calcul de factorielles» de Peter Borwein et de mises en œuvre de Peter Luschny .$1$$n$

¹ _{Il existe des moyens plus rapides de calculer des approximations de, mais ce n’est plus le calcul factoriel, c’est une approximation.$n!$}

Comme la fonction factorielle croît si rapidement, votre ordinateur ne peut stocker quepour relativement petit . Par exemple, un double peut stocker des valeurs allant jusqu'à. Donc, si vous voulez un algorithme très rapide pour calculer, utilisez simplement une table de taille .$n!$$n$$171!$$n!$$171$

La question devient plus intéressante si vous êtes intéressé par Ou par la fonction (ou par ). Dans tous ces cas (y compris ), Je ne comprends pas vraiment le commentaire de votre manuel.Γ log Γ n $\log(n!)$$\Gamma$$\log \Gamma$$n!$

De plus, vos algorithmes itératifs et récursifs sont équivalents (jusqu’à des erreurs en virgule flottante), puisque vous utilisez la récursion en queue.