Как использовать все потоки процессора при вычислении числа Фибоначчи в C#?

Question

[Solid1Goose]

Вопрос: У меня есть программа, которая вычисляет число Фибоначчи. Когда я устанавливаю большое количество проходов, он работает очень медленно, потому что работает только с 1 ядром процессора, я хочу знать, как заставить его потреблять 100% процессора?

Я уже знаю про Parallel.For, но такой подход не позволяет мне сохранить результат предыдущих номеров, по крайней мере я пробовал, и у меня абсолютно ничего не получилось! Я использую этот код для вычисления:

static public class Operations
{
    static public BigInteger calculateFib(int iterations)
    {
        BigInteger a = 0;
        BigInteger b = 1;
        for (int i = 0; i < iterations; i++)
        {
            BigInteger temp = a;
            a = b;
            b = temp + b;
        }
        return a;
    }
}
}

Я хочу получить количество пользовательских ядер и распределить нагрузку между ними, пожалуйста, помогите.

Answer 1

[Василий Банников]

Чтобы код можно было распараллелить - в нём должны быть шаги, которые можно распараллелить.

По аналогии с примером из реальной жизни - ну никак ты не распараллелишь:
1. Достать банку с огурчиками
2. Открыть крышку
3. Достать огурчик
4. Нарезать огурчик на маленькие кругляши
5. Положить кругляши на бутерброд

У тебя каждый следующий шаг требует результат работы всех предыдущих шагов.

В твоём варианте можно попробовать оптимизировать, добавив кэширование уже посчитанных значений (смотри OrderedDictionary). Чтобы какие-то можно было достать сразу из кэша или начать рассчитывать с 50%, а не с самого начала.

Comments

[Solid1Goose]

Спасибо, кэш отличная идея! Конечно первичные вычисления не получаться такими какие хотел, но лучше чем ничего.

Answer 2

[GavriKos]

Я уже знаю про Parallel.For, но такой подход не позволяет мне сохранить результат предыдущих номеров

Ну вот в этом и смысл параллельных вычислений ))) Ваш алгоритм не может работать в несколько потоков в этом виде, именно потому что каждому следующему результату нужен предыдущий. Избавляйтесь от этого условия - и получится распараллелить

Comments

[Solid1Goose]

Спасибо, обязательно учту

Answer 3

[mayton2019]

Я вижу следующие пути оптимизации.
1) Мемоизировать (запомнить в массив) хотя-б первую сотню чисел. Тогда например для 120 чиссла
все считать не надо и можно делать перемотку вперед. Или мемоизировать с шагом. Тоже экономия.

2) Можно попробовать считать через золотое сечение (приближенно) если этого достаточно для
ответа.

3) Можно отказаться от java в пользу С++/GMP библиотек. Возможно расчет суммы будет быстрее.

Но вообще фибоначчи действительно не параллелится. В этом главная проблема.