Рекурсивный алгоритм перестает работать после определенной глубины - PullRequest
Новая
       40

Рекурсивный алгоритм перестает работать после определенной глубины

0 голосов
/ 20 мая 2018

Я изучал среду 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);
    }
}

LoopCounter: 

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;
    }
}

ARecursiveTask для 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);
    }
}

Ответы [ 2 ]

0 голосов
/ 20 мая 2018

Это происходит из-за числового переполнения int, а не из-за рекурсивной глубины, которая хорошо контролируется вашим алгоритмом, которому для рекурсии требуется O (log 2 n) стековых фреймов.

Здесь происходит переполнение: 

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

Когда значение to высокое, это значение может переполниться int.В частности, когда middle приближается к to во втором "отрезке" рекурсивных вызовов, вы умножаете 46341 на 46342, что приводит к -2147432674 из-за переполнения ( demo ).

Вы можете исправить это, используя только BigInteger для умножения "полезной нагрузки", то есть 

BigInteger.valueOf(middle+1).multiply(BigInteger.valueOf(to))
0 голосов
/ 20 мая 2018

В 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
...