Calcul de la factorielle pour de grands nombres


Commenter

Contenu du snippet

En mathématiques : le calcul de la factorielle d'un nombre N consiste à multiplier tous les nombres entiers entre 1 et N, on note le résultat N!

Exemple : 
5! = 1*2*3*4*5 = 120



Solution simpliste

  • Tous les étudiants en informatique connaissent ce problème qui se résout classiquement de deux manières.

public static int factorielleIterative(int n) {
    int produit = 1;
    for (int i=1; i<=n; i++)
        produit *= i;
    return produit;
}

public static int factorielleRecursive(int n) {
    if (n>1)
        return n*factorielleRecursive(n-1);
    else
        return 1;
}

Limites

  • Par nature, la factorielle d'un nombre devient vite très grand lorsque l'on augmente la valeur de N.
  •  
  • Or le type int est codé sur 4 octets il peut représenter au maximum la valeur 2^31, donc à partir de N=13 le résultat devient faux.

Améliorations de base

  • Une première solution consiste à remplacer les int par des long. Avec 8 octets la valeur maximum est 2^63. Mais cela ne fait que repousser le problème, le résultat devient alors faux à partir de N=21.
  •  
  • Une deuxième solution est de remplacer le résultat par une valeur flottante, avec un double on peut atteindre une valeur de 2^1024. Mais d'une part le résultat sera fortement imprécis, d'autre part ça ne permettra que d'aller jusqu'à N=170.

Utilisation de grands nombres

  • Alors comment calculer la factorielle pour des valeurs de N plus importantes et tant qu'à faire exactes ?
  •  
  • Il faut pour cela utiliser des classes de calculs de grands nombres comme BigInteger.
  •  
  • Remarque : je parle ici uniquement du calcul de la factorielle, je n'inclue donc pas la partie affichage, ou sauvegarde du résultat.
  • En particulier il faut oublier la conversion de la base 2 en base 10 pour des valeurs aussi grandes, cela prendrait encore plus de temps que le calcul de la factorielle en lui même !

Exemple

public static BigInteger factorielleGrandNombre(int n) {
    BigInteger produit = BigInteger.ONE;
    BigInteger mul = BigInteger.ONE;
    for (int i = 1; i <= n; i++ , mul = mul.add(BigInteger.ONE))
        produit = produit.multiply(mul);
    return produit;
}

Avantages et Inconvénients

  • La valeur maximale théorique d'un BigInteger est 2^(2^34), c'est donc suffisant pour représenter la factorielle de n'importe quel int.
  •  
  • La taille en mémoire d'un BigInteger va grandir proportionnellement à la valeur qu'il représente. Il faut donc éviter de faire des calculs sur des nombres trop grands qui provoquerait une OutOfMemoryError.
  •  
  • Le temps nécessaire pour effectuer une opération sur deux BigInteger dépend de leurs valeurs respectives. Il est en effet évident que multiplier des nombres de plusieurs Mo est bien plus lent que multiplier des nombres de quelques Ko.
  •  
  • Exemple : la factorielle de 2^31 (le plus grand int) prend environ 7.4 Go en mémoire. Sachant qu'il est nécessaire d'avoir au moins trois BigInteger en mémoire en même temps pour faire une multiplication, il faudrait donc au moins 15 Go de mémoire pour effectuer le dernier produit de la méthode factorielleGrandNombre.

Contraintes

  • Pour éviter les dépassements de mémoire, il vaut mieux se limiter au maximum à des calculs de factorielle de l'ordre de 100 millions (environ 300 Mo).
  •  
  • Pour diminuer le temps de calcul, il faut repenser l'algorithme et prendre en compte le temps de chaque produit. Cela implique de changer l'ordre des calculs pour multiplier des nombres les plus petits possibles.

Nouveaux algorithmes

  • Pour le calcul de 8! la méthode factorielleGrandNombre ci-dessus faisait :
  • 1*2=2, 2*3=6, 6*4=24, 24*5=120, 120*6=720, 720*7=5040 puis 5040*8=40320.
  •  
  • En continuant ainsi avec de plus grandes valeurs, les facteurs seront de plus en plus déséquilibrés.
  • Pour le k ième produit, le premier facteur sera de l'ordre de n^k, alors que le deuxième facteur sera toujours de l'ordre de n.

Par dichotomie

  • Par dichotomie on pourrait s'arranger pour répartir les produits de manière à avoir des facteurs de même ordre de grandeur.
  •  
  • Par exemple pour le calcul de 8! on pourrait faire :
  • 1*2=2, 3*4=12, 5*6=30, 7*8=56 puis 2*12=24, 30*56=1680 et enfin 24*1680=40320.

private static BigInteger produit(int p, int n) {
    if (p == n)
        return BigInteger.valueOf(p);
    else {
        int a = (n + p) / 2;
        return produit(p, a).multiply(produit(a + 1, n));
    }
}

public static BigInteger factorielleDichotomie(int n) {
    if (n > 1)
        return produit(2, n);
    else
        return BigInteger.ONE;
}

Exemple :
  •  
  • pour la factorielle de 100 000 : 3.5 secondes avec factorielleGrandNombre, 0.2 secondes avec factorielleDichotomie
  • pour la factorielle de 1 million : 7mn30 avec factorielleGrandNombre, 9 secondes avec factorielleDichotomie
  •  
  • Remarque : les temps sont donnés à titre de comparaisons, ils varieront d'une machine à l'autre.

Améliorations

  • Avec la méthode par dichotomie, on multiplie au premier niveau tous les entiers successifs : 1 avec 2, 3 avec 4, etc. cela donne au final des écarts importants de valeurs lorsque l'on compare les premiers produits (1*2) avec les derniers (7*8), cet écart se creuse de plus en plus aux niveaux suivants jusqu'au 26*1680 final.
  •  
  • On pourrait essayer un autre arrangement de multiplications, par exemple en associant le premier entier avec le dernier, le deuxième avec l'avant dernier, etc.
  •  
  • Pour le calcul de 8! cela donnerait :
  • 1*8=8, 2*7=14, 3*6=18, 4*5=20, puis 8*20=160, 14*18=252 et enfin 160*252=40320.
  •  
  • Cela peut se faire assez facilement en raisonnant sur l'écriture binaire des nombres.
  • En considérant les entiers de 1 à 8 dans l'ordre, on multiplie l'entier à l'indice 000 avec l'entier à l'indice de son complément 111, de même avec 001 et 110, etc.
  • Puis avec les résultats successifs obtenus dans cet ordre, on multiplie de la même manière, le produit 00 avec 11, ainsi que 01 avec 10, jusqu'à multiplier le produit 0 avec le produit 1.

private static BigInteger produit(int n, int val, int sup, int level) {
    if (level == 0) {
        if (val > n)
            return null;
        else
            return BigInteger.valueOf(val + 2);
    }
    else {
        BigInteger b = produit(n, val ^ (sup - 1), sup *= 2, --level);
        BigInteger a = produit(n, val, sup, level);
        if (b == null)
            return a;
        return a.multiply(b);
    }
}

private static int niveau(int n) {
    if (n < 2)
        return 1;
    int res = 0;
    while (n != 0) {
        res++ ;
        n /= 2;
    }
    return res;
}

public static BigInteger factorielleComplement(int n) {
    if(n > 1)
        return produit(n - 2, 0, 2, niveau(n - 2));
    else
        return BigInteger.ONE;
}
  •  
  • Malheureusement, cette méthode est un peu décevante, elle est certes un peu plus rapide, mais pas autant que ce que l'on pouvait en espérer.
  •  
  • Exemples :
  • pour la factorielle de 10 millions, 5mn45 avec factorielleDichotomie, 5mn35 avec factorielleComplement.
  • pour la factorielle de 20 millions, 17mn20 avec factorielleDichotomie, 16mn50 avec factorielleComplement.

Approximations

  • Puisque les calculs exacts sont particulièrement longs et que leur affichage l'est encore plus, il peut être intéressant de récupérer une approximation du résultat, par exemple son écriture scientifique.
  •  
  • Pour cela on utilisera des logarithmes, en effet si la factorielle de N est le produit des N premiers entiers, le logarithme de N! est lui la somme des N premiers logarithmes.
  • Or le résultat d'une somme est beaucoup plus petit en mémoire que le résultat d'un produit, d'autant que les logarithmes de k sont bien plus petits que k.
  •  
  • On pourra donc obtenir cette approximation avec un type double, sans problème de mémoire, ni de gestion du temps, mais avec une limite sur la valeur de N : 2^28 maximum.

public static String factorielleRapide(int n) {
    double d = 0;
    for (int i = 2; i <= n; i++ )
        d += Math.log10(i);
    int p = (int) Math.floor(d);
    return String.format(Locale.US, "%.16fe+%s%d", Math.pow(10, d - p), (p < 10 ? "0" : ""), p);
}

Exemple :
  • factorielle de 100 millions : 2 secondes, résultat = 1.6170898630981347e+756570556
  • factorielle de 200 millions : 4.5 secondes, résultat = 2.003692197432533000e+1573347107

Compatibilité : 1

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (KX)