2
Кто-нибудь знает, как параллельно выполнять вычисление биномиального коэффициента? Любой ресурс для многоядерных процессоров или CUDA был бы полезен, спасибо.Параллельное вычисление биномиального коэффициента
A
ответ
1
Я хотел бы начать с следующего.
- Создайте массив размера (n + 1) и заполните его 1, 1, 2, 3, .... n.
- Выполняйте инклюзивное сканирование этого массива с помощью операции с продуктом. На этот момент у вас будет массив [n] = n !. т. е. массив [0] = 0 !, массив 1 = 1! array [100] = 100! и так далее.
- Теперь, когда у вас есть все факториалы от 0! к n !, вы можете выполнить (n!/p! * (n - p)!) очень легко.
Для первой и последней операций могут потребоваться специальные ядра. Вторая операция может быть выполнена с использованием тяги и операции inclusive_scan.
РЕДАКТИРОВАТЬ
Что касается недостатков, как упоминался выше в комментариях, будет Precison проблемы даже с 64-битными целыми числами по разумным большим размерам п. Но это основной алгоритм, который вам нужно будет использовать.
Смежные вопросы
- 1. Java: вычисление биномиального коэффициента
- 2. Псевдокод биномиального коэффициента
- 3. Вычисление биномиального MCMC
- 4. Рекурсивное решение для биномиального коэффициента в C
- 5. Умный алгоритм для нахождения делителей биномиального коэффициента
- 6. Алгоритм биномиального коэффициента (Ncr) в Рубине
- 7. Понимания рекурсивного метода для нахождения биномиального коэффициента
- 8. Параллельное вычисление в Haskell
- 9. Параллельное максимальное вычисление
- 10. Вычисление коэффициента определения в Python
- 11. Параллельное вычисление рекурсивной древовидной структуры
- 12. Нахождение биномиального коэффициента при больших п и к модулю м
- 13. Является ли рост функции биномиального коэффициента факториальным или полиномиальным
- 14. Функция биномиального коэффициента C++ неверный ответ n> 13
- 15. алгоритм биномиального коэффициента с использованием динамического программирования и одномерного массива
- 16. Разработка алгоритма биномиального коэффициента с использованием одномерного массива
- 17. Вычисление коэффициента усиления информации для текстового файла?
- 18. Вычисление коэффициента корреляции между двумя многомерными массивами
- 19. вычисление коэффициента Джини в Python/numpy
- 20. Параллельное вычисление квадратичной формы в RcppParallel
- 21. Параллельное вычисление функции с doSMP в Windows
- 22. Параллельное вычисление Haskell с использованием STArray
- 23. Параллельное вычисление с нереальным двигателем 4
- 24. Параллельное вычисление элементов массива в ржавчине
- 25. Неправильное количество измерений - параллельное вычисление R
- 26. Параллельное вычисление элементов массива на GPU
- 27. Вычисление коэффициента достоверности при обнаружении лица Viola-Jones?
- 28. Зацикливание по списку кадров данных и вычисление коэффициента корреляции
- 29. вычисление коэффициента GLM матрица, диагональные и среднеквадратическая ошибка
- 30. Вычисление коэффициента загрузки в хеш-таблице, которая объединяет дубликаты?
Вы знаете, что 'nCp = n!/(p! * (n - p)!) ', правильно? Так зачем вам распараллеливать? – tom
Я думаю, что этот вопрос является хорошей отправной точкой: http://stackoverflow.com/questions/4256188/binomial-coefficient –
@tom просто хочет быстрый способ вычисления этих коэффициентов, скажем, n или p очень бит? – Ang