OutOfMemoryError на BigInteger - PullRequest
Новая
       9

OutOfMemoryError на BigInteger

5 голосов
/ 14 мая 2011

Я пишу калькулятор польской нотации для BigIntegers (просто *, ^ и!) И получаю OutOfMemoryError в строке, где я вычитаю BigInteger.ONE, чтобы заставить факториал работать, почему? 

package polish_calculator;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Stack;

public class Main {
    static BigInteger factorial(BigInteger number){
        Stack <BigInteger> factorialStack = new Stack<BigInteger>();
        factorialStack.push(number);

        while (!number.equals(BigInteger.ONE)){ //load the stack
            factorialStack.push(number.subtract(BigInteger.ONE)); // here's the error
        }

        BigInteger result = BigInteger.ONE;

        while(!factorialStack.empty()){ // empty and multiply the stack
            result.multiply(factorialStack.pop());
        }

        return result;
    }


    public static void main(String[] args) throws IOException {

        BigInteger testFactorial = new BigInteger("12");
        System.out.println(factorial(testFactorial));
        Stack <String> stack = new Stack<String>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String readExpression = br.readLine();
        while(!readExpression.equals("")){
            String [] splittedExpression = readExpression.split(" ");
            for(int i=0; i<splittedExpression.length;i++){
                if(splittedExpression[i].equals("*"))
                {
                    BigInteger operand1 = new BigInteger(stack.pop());
                    BigInteger operand2 = new BigInteger(stack.pop());
                    BigInteger result = operand1.multiply(operand2);
                    String stackString = result.toString();
                    stack.push(stackString);
                }
                if(splittedExpression[i].equals("^"))
                {
                    BigInteger operand1 = new BigInteger(stack.pop());
                    BigInteger operand2 = new BigInteger(stack.pop());
                    BigInteger result = operand1.modPow(operand2, BigInteger.ONE);
                    String stackString = result.toString();
                    stack.push(stackString);
                }

                if(splittedExpression[i].equals("!"))
                {
                    BigInteger operand1 = new BigInteger(stack.pop());
                    BigInteger result = factorial(operand1);

                    String stackString = result.toString();
                    stack.push(stackString);
                }
                else{ //it's an integer
                    stack.push(splittedExpression[i]);
               }
            } // end for splittedExpression.length
        }
    }
}

Ошибка: 

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
        at java.math.BigInteger.subtract(BigInteger.java:1118)
        at polish_calculator.Main.factorial(Main.java:45)
        at polish_calculator.Main.main(Main.java:65)
Java Result: 1

1 Ответ

11 голосов
/ 14 мая 2011

BigInteger.subtract генерирует новый BigInteger, который вы помещаете в стек.

Но исходное число остается прежним, поэтому условие! Number.equals (BigInteger.ONE) никогда не будет истинным.

Таким образом, вы навсегда заполняете стек копиями числа 1, пока не закончится память

Отредактировано (снова):

Обратите внимание, чтоэто также очень требовательный к памяти способ вычисления факториала, так как вам нужно поместить N значений в стек, чтобы вычислить N!Умножать их по мере продвижения было бы лучше, хотя, конечно, вам не нужен большой N, прежде чем факториал действительно станет очень большим.

См. http://en.wikipedia.org/wiki/Factorial для некоторых деталей по эффективному вычислению больших факториалов..

...