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

Question

我在探索 Fork/Join 框架及其通过阶乘计数可能带来的速度优势时发现我的顺序递归算法在某个点中断。准确地说，当我尝试计算 46342! 时，RecursiveCounter 的结果是错误的，但在该值之前它总是正确的，并且与 ParallelCounter 和 [=16= 的结果相同].有谁知道为什么会发生这种情况？

这里是类:

递归计数器：

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 的递归任务：

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

Answer 2

发生这种情况是因为 int 的数值溢出，而不是因为递归深度，这由您的算法很好地控制，它需要 O(log₂n ) 用于递归的堆栈帧。

溢出发生在这里：

new BigInteger(String.valueOf((middle + 1) * to))

当to为高时，这个值可以溢出int。具体来说，当 middle 在第二个 "leg" 递归调用中接近 to 时，您将 46341 乘以 46342，这会产生 -2147432674，因为溢出 (demo).

您可以通过仅使用 BigInteger 进行 "payload" 乘法来解决此问题，即

BigInteger.valueOf(middle+1).multiply(BigInteger.valueOf(to))

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

Recursive algorithm stops working after certain depth

java

math

recursion

integer

biginteger