A Fast Algorithm for Computing Binomial Coefficients Modulo Powers of Two
I present a new algorithm for computing binomial coefficients modulo . The proposed method has an preprocessing time, after which a binomial coefficient with can be computed modulo in time. denotes the time complexity of multiplying two -bit numbers, which can range from to or better. Thus,...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2013-01-01
|
| Series: | The Scientific World Journal |
| Online Access: | http://dx.doi.org/10.1155/2013/751358 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832558825233711104 |
|---|---|
| author | Mugurel Ionut Andreica |
| author_facet | Mugurel Ionut Andreica |
| author_sort | Mugurel Ionut Andreica |
| collection | DOAJ |
| description | I present a new algorithm for computing binomial coefficients modulo . The proposed method has an preprocessing time, after which a binomial coefficient with can be computed modulo in time. denotes the time complexity of multiplying two -bit numbers, which can range from to or better. Thus, the
overall time complexity for evaluating binomial coefficients modulo with is . After preprocessing, we can actually compute binomial coefficients modulo any with . For larger values of and , variations
of Lucas’ theorem must be used first in order to reduce the computation to
the evaluation of multiple binomial coefficients (or restricted types of factorials ) modulo with . |
| format | Article |
| id | doaj-art-be8b75fe49a34ab4ae9522af13610e96 |
| institution | Kabale University |
| issn | 1537-744X |
| language | English |
| publishDate | 2013-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | The Scientific World Journal |
| spelling | doaj-art-be8b75fe49a34ab4ae9522af13610e962025-02-03T01:31:29ZengWileyThe Scientific World Journal1537-744X2013-01-01201310.1155/2013/751358751358A Fast Algorithm for Computing Binomial Coefficients Modulo Powers of TwoMugurel Ionut Andreica0Computer Science Department, Politehnica University of Bucharest, Splaiul Independentei 313, Sector 6, 060042 Bucharest, RomaniaI present a new algorithm for computing binomial coefficients modulo . The proposed method has an preprocessing time, after which a binomial coefficient with can be computed modulo in time. denotes the time complexity of multiplying two -bit numbers, which can range from to or better. Thus, the overall time complexity for evaluating binomial coefficients modulo with is . After preprocessing, we can actually compute binomial coefficients modulo any with . For larger values of and , variations of Lucas’ theorem must be used first in order to reduce the computation to the evaluation of multiple binomial coefficients (or restricted types of factorials ) modulo with .http://dx.doi.org/10.1155/2013/751358 |
| spellingShingle | Mugurel Ionut Andreica A Fast Algorithm for Computing Binomial Coefficients Modulo Powers of Two The Scientific World Journal |
| title | A Fast Algorithm for Computing Binomial Coefficients Modulo Powers of Two |
| title_full | A Fast Algorithm for Computing Binomial Coefficients Modulo Powers of Two |
| title_fullStr | A Fast Algorithm for Computing Binomial Coefficients Modulo Powers of Two |
| title_full_unstemmed | A Fast Algorithm for Computing Binomial Coefficients Modulo Powers of Two |
| title_short | A Fast Algorithm for Computing Binomial Coefficients Modulo Powers of Two |
| title_sort | fast algorithm for computing binomial coefficients modulo powers of two |
| url | http://dx.doi.org/10.1155/2013/751358 |
| work_keys_str_mv | AT mugurelionutandreica afastalgorithmforcomputingbinomialcoefficientsmodulopowersoftwo AT mugurelionutandreica fastalgorithmforcomputingbinomialcoefficientsmodulopowersoftwo |