Биномиальный коэффициент

Question

Простой вопрос: какой самый быстрый способ вычислить биномиальный коэффициент? - какой-то многопоточный алгоритм?

Я ищу подсказки :) - а не реализации :)

Answer 1

Ну, я считаю, что самым быстрым способом было бы читать их из таблицы, а не вычислять их.

Ваши требования к целочисленной точности из-за использования двойного представления означают, что C (60,30) слишком велико и составляет около 1e17, так что (при условии, что вы хотите иметь C (m, n) для всех m до некоторый предел, и все n <= m), ваша таблица будет иметь только около 1800 записей. Что касается заполнения таблицы, я думаю, что треугольник Паскаля - путь. </p>

Answer 2

Согласно приведенному ниже уравнению (из википедии ) самым быстрым способом было бы разделить диапазон i = 1, k на количество потоков, дать каждому потоку один сегмент диапазона, и каждый поток обновляет Конечный результат в замке. «Академическим способом» будет разделить диапазон на задачи, каждая задача состоит в том, чтобы вычислить (n - k + i) / i, а затем, независимо от того, сколько у вас потоков, все они запускаются в цикле, запрашивая следующую задачу. Первый быстрее, второй ... академический.

РЕДАКТИРОВАТЬ: дальнейшее объяснение - в обоих случаях у нас есть произвольное количество потоков. Обычно количество потоков равно количеству процессорных ядер, поскольку добавление большего количества потоков не дает никаких преимуществ. Разница между двумя способами заключается в том, что делают эти потоки.

В первом случае каждому потоку присваиваются N, K, I1 и I2, где I1 и I2 - сегмент в диапазоне 1..K. Затем каждый поток имеет все данные, в которых он нуждается, поэтому он вычисляет свою часть результата и по окончании обновляет окончательный результат.

Вторым способом каждому потоку дается N, K и доступ к некоторому синхронизированному счетчику, который считает от 1 до K. Затем каждый поток получает одно значение из этого общего счетчика, вычисляет одну долю результата, обновляет конечный результат, и повторяется до тех пор, пока счетчик не сообщит потоку, что больше нет элементов. Если случится так, что некоторые процессорные ядра будут быстрее, чем другие, тогда этот второй способ позволит максимально использовать все ядра. Недостатком второго способа является слишком большая синхронизация, которая эффективно блокирует, скажем, 20% потоков.

Answer 3

Подсказка: вы хотите сделать как можно меньше умножений. Формула n! / (k! * (n-k)!). Вы должны сделать не более 2m умножений, где m - это минимум k и n-k. Если вы хотите работать с (достаточно) большими числами, вы должны использовать специальный класс для представления чисел (например, в Java есть BigInteger).

Answer 4

Вот способ, который никогда не будет переполнен, если конечный результат в машинном выражении изначально не выражен, не требует умножения / факторизации, легко распараллеливается и обобщается до типов BigInteger:

Первое замечание: биномиальные коэффициенты удовлетворяют следующему:

.

Это дает прямую рекурсию для вычисления коэффициента: базовые случаи и , оба из которых равны 1.

Отдельные результаты вложенных вызовов являются целыми числами, и если \ binom {n} {k} может быть представлен целым числом, они тоже могут; Итак, переполнение не является проблемой.

Наивно реализованная рекурсия приводит к повторным вызовам и экспоненциальному времени выполнения.

Это можно исправить путем кэширования промежуточных результатов. Есть n ^ 2 подзадач, которые можно объединить за время O (1), что дает оценку сложности O (n ^ 2).