递归算法在一定深度后停止工作

Question

当我发现我的顺序递归算法在某一点上断时,我正在探索Fork/Join框架及其可能的速度优势,通过因子计数.准确地说,当我尝试计数46342!从结果RecursiveCounter是错误的,但该值才永远是对的是,从产生的同ParallelCounter和LoopCounter.有谁知道为什么会发生这种情况？

以下是课程:

RecursiveCounter:

public class RecursiveCounter implements FactorialCounter, RangeFactorialCounter {
    @Override
    public BigInteger count(int number) {
        return count(1, number);
    }

    @Override
    public BigInteger count(int from, int to) {
        int middle = (from + to) >> 1;
        BigInteger left;
        BigInteger right;
        if (middle - from > 1)
            left = count(from, middle);
        else
            left = new BigInteger(String.valueOf(from * middle));
        if (to - (middle + 1) > 1)
            right = count(middle + 1, to);
        else
            right = to == middle + 1 ? new BigInteger(String.valueOf(to)) : new BigInteger(String.valueOf((middle + 1) * to));
        return left.multiply(right);
    }
}

循环计数器:

public class LoopCounter implements FactorialCounter, RangeFactorialCounter {
    @Override
    public BigInteger count(final int number) {
        return count(1, number);
    }

    @Override
    public BigInteger count(final int from, final int to) {
        BigInteger result = new BigInteger("1");
        for (int i = from; i < to + 1; i++) {
            result = result.multiply(new BigInteger(String.valueOf(i)));
        }
        return result;
    }
}

ParallelCounter的RecursiveTask:

public class FactorialTask extends RecursiveTask<BigInteger> {
    private static final int THRESHOLD = 1000;
    private RangeFactorialCounter iterativeCounter = new LoopCounter();

    private Integer firstVal;
    private Integer lastVal;

    public FactorialTask(Integer from, Integer to) {
        super();
        this.firstVal = from;
        this.lastVal = to;
    }

    @Override
    protected BigInteger compute() {
        return count(firstVal, lastVal);
    }

    private BigInteger count(int from, int to) {
        int middle = (from + to) >> 1;
        if (to - from > THRESHOLD) {
            List<FactorialTask> tasks = Arrays.asList(new FactorialTask(from, middle), new FactorialTask(middle + 1, to));
            tasks.forEach(RecursiveTask::fork);
            return tasks.stream()
                    .map(RecursiveTask::join)
                    .map(BigInteger.class::cast)
                    .reduce(new BigInteger("1"), BigInteger::multiply);
        } else {
            return (from != to) ? countSequential(from, to) : new BigInteger(String.valueOf(from));
        }
    }

    private BigInteger countSequential(int from, int to) {
        return iterativeCounter.count(from, to);
    }
}

Answer 1

在RecursiveCounter,from * middle并且(middle + 1) * to可能溢出,您需要使用BigInteger它们来操纵它们:

...
left = BigInteger.valueOf(from).multiply(BigInteger.valueOf(middle));
...
right = to == middle + 1 ? BigInteger.valueOf(to) : BigInteger.valueOf(to).multiply(BigInteger.valueOf(middle + 1));

然后你就可以得到同样的结果RecursiveCounter和LoopCounter:

LoopCounter loopCounter = new LoopCounter();
RecursiveCounter recursiveCounter = new RecursiveCounter();
BigInteger loopResult = loopCounter.count(46342);
BigInteger recursiveResult = recursiveCounter.count(46342);
System.out.println(loopResult.equals(recursiveResult)); // true