Cargando…
A Fast Algorithm for Computing Binomial Coefficients Modulo Powers of Two
I present a new algorithm for computing binomial coefficients modulo 2(N). The proposed method has an O(N (3) · Multiplication(N) + N (4)) preprocessing time, after which a binomial coefficient C(P, Q) with 0 ≤ Q ≤ P ≤ 2(N) − 1 can be computed modulo 2(N) in O(N (2) · log(N) · Multiplication(N)) tim...
| Autor principal: | |
|---|---|
| Formato: | Online Artículo Texto |
| Lenguaje: | English |
| Publicado: |
Hindawi Publishing Corporation
2013
|
| Materias: | |
| Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3856163/ https://www.ncbi.nlm.nih.gov/pubmed/24348186 http://dx.doi.org/10.1155/2013/751358 |