La fonction récursive pour calculer les échecs factoriels après 20

Question

J'ai écrit le code Java ci-dessous pour calculer la factorielle des nombres de 1 à 30 récursivement. Pour une raison quelconque, la sortie ne correspond pas au results here pour les nombres supérieurs à 20. Je suis surpris de voir aussi des nombres négatifs.

code

class Test { 

    public static Long factorial(Long number) { 
     if(number == 1){ 
      return 1L; 
     }else{ 
      return number*factorial(number-1); 
     } 
    } 

    public static void main(final String... arguments){ 
     for(Long number=1L;number<=30;number++){ 
      System.out.println("Factorial of " + number + " : " + factorial(number)); 
     } 
    } 
} 

Sortie

Factorial of 1 : 1 
Factorial of 2 : 2 
Factorial of 3 : 6 
Factorial of 4 : 24 
Factorial of 5 : 120 
Factorial of 6 : 720 
Factorial of 7 : 5040 
Factorial of 8 : 40320 
Factorial of 9 : 362880 
Factorial of 10 : 3628800 
Factorial of 11 : 39916800 
Factorial of 12 : 479001600 
Factorial of 13 : 6227020800 
Factorial of 14 : 87178291200 
Factorial of 15 : 1307674368000 
Factorial of 16 : 20922789888000 
Factorial of 17 : 355687428096000 
Factorial of 18 : 6402373705728000 
Factorial of 19 : 121645100408832000 
Factorial of 20 : 2432902008176640000 
Factorial of 21 : -4249290049419214848 
Factorial of 22 : -1250660718674968576 
Factorial of 23 : 8128291617894825984 
Factorial of 24 : -7835185981329244160 
Factorial of 25 : 7034535277573963776 
Factorial of 26 : -1569523520172457984 
Factorial of 27 : -5483646897237262336 
Factorial of 28 : -5968160532966932480 
Factorial of 29 : -7055958792655077376 
Factorial of 30 : -8764578968847253504 

Quelqu'un pourrait-il s'il vous plaît aidez-moi à calculer factoriel jusqu'à 30 correctement?

Answer 1

C'est ce que l'on appelle le "débordement". Les longueurs sont stockées avec 64 bits; leur valeur maximale est de 2^63 - 1, soit 9 223 372 036 854 775 807. Essayez plutôt d'utiliser un BigInteger. L'utilisation de BigInteger est un peu compliquée car l'instanciation et les opérations sont différentes des int/longs habituels. Voici votre code retravaillé pour BigInteger:

public class BigIntFactorial { 

    public static BigInteger factorial(BigInteger number) { 
     if(number.equals(BigInteger.ONE)) { 
      return BigInteger.valueOf(1); 
     } else { 
      return number.multiply(factorial(number.subtract(BigInteger.ONE))); 
     } 
    } 

    public static void main(final String... arguments){ 
     for(Long number=1L;number<=30;number++){ 

      System.out.println("Factorial of " + number + " : " + factorial(BigInteger.valueOf(number))); 
     } 
    } 
} 

sortie est:

Factorial of 1 : 1 
Factorial of 2 : 2 
Factorial of 3 : 6 
Factorial of 4 : 24 
Factorial of 5 : 120 
Factorial of 6 : 720 
Factorial of 7 : 5040 
Factorial of 8 : 40320 
Factorial of 9 : 362880 
Factorial of 10 : 3628800 
Factorial of 11 : 39916800 
Factorial of 12 : 479001600 
Factorial of 13 : 6227020800 
Factorial of 14 : 87178291200 
Factorial of 15 : 1307674368000 
Factorial of 16 : 20922789888000 
Factorial of 17 : 355687428096000 
Factorial of 18 : 6402373705728000 
Factorial of 19 : 121645100408832000 
Factorial of 20 : 2432902008176640000 
Factorial of 21 : 51090942171709440000 
Factorial of 22 : 1124000727777607680000 
Factorial of 23 : 25852016738884976640000 
Factorial of 24 : 620448401733239439360000 
Factorial of 25 : 15511210043330985984000000 
Factorial of 26 : 403291461126605635584000000 
Factorial of 27 : 10888869450418352160768000000 
Factorial of 28 : 304888344611713860501504000000 
Factorial of 29 : 8841761993739701954543616000000 
Factorial of 30 : 265252859812191058636308480000000 

Answer 2

Cela ne fonctionne pas car vous dépassez le nombre maximal pouvant être représenté par un long. Il a une valeur minimale de -9 223 372 036 854 775 808 et une valeur maximale de 9 223 372 036 854 775 807 (inclus). Les nombres négatifs apparaissent parce que Java roule dans les négatifs quand vous dépassez le maximum. Trouver une manière différente de représenter les nombres.

Answer 3

Vous semblez avoir couru dans le problème qui se factorielles ridiculement grand vraiment rapide. Plus grand que le plus grand nombre qui peut être représenté par un long. Et en java, cela signifie que la valeur "survole" et devient négative.

Une solution consiste à utiliser BigInteger. Il a une quantité variable de bits, vous pouvez donc représenter presque n'importe quelle taille de nombre et vous ne rencontrerez pas de problèmes de débordement. Notez que quand je dis presque, je veux dire que biginteger est limité à Integer.MAX_VALUE bits sur certaines implémentations, et vous ne devriez jamais rencontrer cette limite.

Une autre solution serait de représenter les nombres avec des doubles. Ils ont une limite plus élevée que les longs, au prix d'une perte de précision. Je n'ai pas couru les chiffres, mais vous devriez bien calculer 30!

Une autre chose sympa que vous pouvez faire lorsque vous voulez vraiment pousser les limites est d'utiliser fft pour calculer la multiplication des nombres de très haute précision. Plus d'informations ici: http://numbers.computation.free.fr/Constants/Algorithms/fft.html

edit: a couru les nombres, double précision est bien