巨型数的阶乘不叠加，也不返回结果(JAVA) [英] Factorial of giant number not oveflowing stack but also not returning the result (JAVA)
问题描述
我专门尝试将这个问题看作是尾递归函数.不能使用迭代解决方案.
我正在尝试将一个阶乘计算器组装在一起，只要结果为< ;，它就可以处理任何整数作为输入. 2 ^ 2147483647(因为我使用的是BigInteger).
I am trying to put together a factorial calculator that can handle any integer as input as long as the result is < 2^2147483647 (Since I am using BigInteger to do it).
我遇到了一个问题，即使我不认为我已经通过了堆栈的容量，阶乘的结果也只会在某些时候作为输出显示.它对于〜8000以下的值似乎始终如一地工作(估计，每次执行都不相同..?)，但是对于〜8000和〜31400之间的值断断续续地不打印任何内容(随着数字的增加，空白的回报越来越频繁..?)
I am running into an issue where the result of the factorial only prints as output SOMETIMES, even though I do not believe I have passed the capacity of the stack. It seems to work consistently for values under ~8000 (estimated, was not the same each execution..?), but intermittently prints nothing for values between ~8000 and ~31400 (showing blank returns increasingly often as number go up..?).
一次执行时，我得到13947作为堆栈溢出之前处理的最高整数，而另一次是在12000年代.我认为至少可以在执行过程中归因于可变堆栈状态(因为每次都要获取用户输入并每次都进行更改)，但是我是一个相当新的程序员，我对某些事情的理论理解会有些动摇，所以我不确定.
One execution I got 13947 as the highest integer handled before the stack overflow, another time it was in the 12000s. I'm thinking at least that much can be attributed to variable stack states during execution (since user input is taken and changes each time), but I am a fairly new programmer and my theoretical understanding on some things can be shaky, so I am not sure.
有人知道为什么代码对于某些较高的值可能什么也不打印吗?我最好的猜测是
Does anyone know why the code might be printing nothing for some high values? My best guesses are
- 该结果大于2 ^ 2147483647，因此无法将其存储为BigInteger，(但这不能解释其间歇性...)
- 计算花费了太长时间，并且循环在计算完成之前一直在继续(解释了间歇性，但似乎是不可能的)
- 即使计算正在进行中，我的Eclipse IDE仍然不能很好地将那么多的数字打印到屏幕上.
我不确定如何验证上述猜测.我已经了解了BigInteger的局限性以及Eclipse的局限性，但是没有找到可以与我的任务进行比较的答案.
I am not sure how to validate above guesses. I have read about the limitations of BigInteger, as well as Eclipse limitations but have not found any answer that I can compare to my task.
这是代码:
package factorielRecursiveTerminale;
import java.math.BigInteger;
import java.util.Scanner;
public class factorielRecursiveTerminale {
static BigInteger factoriel(BigInteger n, BigInteger m) { //calcule le factoriel pour n'importe quel entier.
if (n.compareTo(BigInteger.ZERO) < 1) return m; // théoriquement valide pour tout entier dont n! < 2^2147483647, mais
return factoriel(n.subtract(BigInteger.ONE), n.multiply(m));// limité par la capacité de la pile (à cause de la récursion).
}
static BigInteger fact(int n) { //convertir l'entree en BigInteger et lancer la recursion
if(n < 0) {
return BigInteger.valueOf(-1);
}
BigInteger b = BigInteger.valueOf(n);
return factoriel(b, BigInteger.ONE);
}
public static void main(String[] args) { //demonstration
String valeurRecu = "";
int valeur;
BigInteger resultat;
System.out.println("Calcul Factoriel\n");
while(!valeurRecu.contentEquals("q")){
System.out.println("Entrer la valeur a calculer (q - quitter) : ");
Scanner entree = new Scanner(System.in);
valeurRecu = entree.nextLine();
if (valeurRecu.contentEquals("q")) entree.close();
else {
try {
valeur = Integer.parseInt(valeurRecu);
} catch (NumberFormatException e){
System.out.println("Pas un entier. Essayer encore.\n");
continue;
}
try {
resultat = fact(valeur);
if(resultat.compareTo(BigInteger.valueOf(-1)) == 0) {
System.out.println("Valeur negative. Essayer encore.\n");
}
else System.out.println("Factoriel " + valeur + " -> " + fact(valeur) + "\n");
}
} catch(StackOverflowError e) {
System.out.println("Depassement de la pile. Essayer encore.\n");
}
}
}
System.out.println("Au revoir! :)\n");
}
}
以下是一些示例输出:
Calcul Factoriel
Entrer la valeur a calculer (q - quitter) : 0
Factoriel 0 -> 1
Entrer la valeur a calculer (q - quitter) : 1
Factoriel 1 -> 1
Entrer la valeur a calculer (q - quitter) : 2
Factoriel 2 -> 2
Entrer la valeur a calculer (q - quitter) : 3
Factoriel 3 -> 6
Entrer la valeur a calculer (q - quitter) : 4
Factoriel 4 -> 24
Entrer la valeur a calculer (q - quitter) : 10
Factoriel 10 -> 3628800
Entrer la valeur a calculer (q - quitter) : 8000
Factoriel 8000 -> 518418106.......
Entrer la valeur a calculer (q - quitter) : 9050
Factoriel 9050 -> 480838025.......
Entrer la valeur a calculer (q - quitter) : 9100
Factoriel 9100 ->
Entrer la valeur a calculer (q - quitter) : 31400
Factoriel 31400 ->
Entrer la valeur a calculer (q - quitter) : 31401
Depassement de la pile. Essayer encore.
推荐答案
阶乘方法可以正常工作，但是当超出堆栈大小时，确实会产生相对一致的溢出.对我来说，这大约是9000-10000个电话.请记住，对于每个递归，n上的大值！在BigInteger对象中占用了大量空间.因此，SO发生在堆栈跟踪的早期.
The factorial method works fine but you do get relatively consistent overflow when exceeding the stack size. The count for me is somewhere about 9000-10000 calls. Remember that for each recursion, the large values on n! are taking up quite a bit of space in the BigInteger object. So the SO is occurring somewhat early in stack trace.
我建议您执行的操作是将值打印到文件中，而不是打印到IDE的控制台中.这样，您可以确定它是IDE(可能是)还是程序(可能不是).我知道对于Eclipse，必须为控制台设置一个内部缓冲区大小，以及一个最大行大小.
What I suggest you do is print the values to a file instead of to the console of the IDE. That way you can determine if it is the IDE (probably) or the program (probably not). I know for Eclipse there is an internal buffer size for the console that one must set as well as a max line size.
static int count;
public static void main(String[] args) {
count = 0;
int n = 20000;
BigInteger f = fact(n);
}
static BigInteger factoriel(BigInteger n, BigInteger m) {
// calcule le factoriel pour n'importe quel entier.
if (n.compareTo(BigInteger.ONE) < 1)
return m; // théoriquement valide pour tout entier dont n! < 2^2147483647, mais
count++;
BigInteger f = null;
try {
f = factoriel(n.subtract(BigInteger.ONE), n.multiply(m));// limité par la capacité de la pile (à cause de la récursion).
} catch(StackOverflowError e) {
System.out.println(count);
}
return f;
}
static BigInteger fact(int n) { // convertir l'entree en BigInteger et lancer la recursion
if (n < 0) {
return BigInteger.valueOf(-1);
}
BigInteger b = BigInteger.valueOf(n);
return factoriel(b, BigInteger.ONE);
}
这篇关于巨型数的阶乘不叠加，也不返回结果(JAVA)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
