2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 число сочетаний, алгоритм
Сообщение18.10.2019, 09:29 
Всем привет! Такой вопрос: по какому алгоритму можно быстро посчитать число сочетаний $\binom{n}{k}$ по некоторому не очень большому модулю? Значение $n$ предполагается около миллиона, $k$ - примерно вдвое меньше. На треугольник Паскаля не хватает памяти, рекуррентные вычисления получаются слишком медленными.

 
 
 
 Posted automatically
Сообщение18.10.2019, 09:46 
 i  Тема перемещена из форума «Программирование» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы).

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

 
 
 
 Posted automatically
Сообщение19.10.2019, 18:36 
 i  Тема перемещена из форума «Карантин» в форум «Программирование»

 
 
 
 Re: число сочетаний, алгоритм
Сообщение19.10.2019, 19:07 
Что можно сделать для простого модуля, разобрали здесь:
https://stackoverflow.com/questions/10118137/fast-n-choose-k-mod-p-for-large-n

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

 
 
 
 Re: число сочетаний, алгоритм
Сообщение19.10.2019, 23:32 
Аватара пользователя
mihatel в сообщении #1421375 писал(а):
... быстро посчитать число сочетаний $\binom{n}{k}$ по некоторому не очень большому модулю? Значение $n$ предполагается около миллиона

$\binom{n}{k} \mod m$
Степень вхождения простого модуля в факториал определить легко (см. Википедию). Если $m$ простое, первое что приходит в голову – определить степень вхождения $m$ в $n!,k!,n-k!$ и вычесть из первого второе и третье, получив с большой вероятностью нечто $>0$ (если $m$ действительно не очень большое). Тогда вопрос закрыт. Если же $\binom{n}{k}$ не делится на $m$, приходится то же проделать с остальными простыми делителями факториалов, то есть факторизовать $\binom{n}{k}$. Алгоритм возведения в степень по заданному модулю (уже не обязательно простому) можно посмотреть например у Ишмуратова (Методы факторизации натуральных чисел, стр. 13). Вычислить степени и перемножить по модулю. А как быстрее? Я по ссылке arseniiv не ходил, там всё по-английски), но возможно то и имеется в виду.

 
 
 
 Re: число сочетаний, алгоритм
Сообщение20.10.2019, 10:53 
arseniiv в сообщении #1421639 писал(а):
Что можно сделать для простого модуля, разобрали здесь:
https://stackoverflow.com/questions/10118137/fast-n-choose-k-mod-p-for-large-n

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

Спасибо! Теорема Ферма - это то, что надо. Суть в том, что делить ничего не надо, достаточно один раз найти обратные элементы по простому модулю и перемножать числитель с остатками знаменателя.

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group