Andreica Mugurel Ionut
Computer Science Department, Politehnica University of Bucharest, Splaiul Independentei 313, Sector 6, 060042 Bucharest, Romania.
ScientificWorldJournal. 2013 Nov 6;2013:751358. doi: 10.1155/2013/751358. eCollection 2013.
I present a new algorithm for computing binomial coefficients modulo 2N. The proposed method has an O(N3·Multiplication(N)+N4) preprocessing time, after which a binomial coefficient C(P, Q) with 0≤Q≤P≤2N-1 can be computed modulo 2N in O(N2·log(N)·Multiplication(N)) time. Multiplication(N) denotes the time complexity of multiplying two N-bit numbers, which can range from O(N2) to O(N·log(N)·log(log(N))) or better. Thus, the overall time complexity for evaluating M binomial coefficients C(P, Q) modulo 2N with 0≤Q≤P≤2N-1 is O((N3+M·N2·log(N))·Multiplication(N)+N4). After preprocessing, we can actually compute binomial coefficients modulo any 2R with R≤N. For larger values of P and Q, variations of Lucas' theorem must be used first in order to reduce the computation to the evaluation of multiple (O(log(P))) binomial coefficients C(P', Q') (or restricted types of factorials P'!) modulo 2N with 0≤Q'≤P'≤2N-1.
我提出了一种用于计算模(2^N)二项式系数的新算法。所提出的方法预处理时间为(O(N^3·\text{乘法}(N)+N^4))，在此之后，对于(0\leq Q\leq P\leq2^N - 1)的二项式系数(C(P, Q))，可以在(O(N^2·\log(N)·\text{乘法}(N)))时间内计算模(2^N)的值。(\text{乘法}(N))表示两个(N)位数字相乘的时间复杂度，其范围可以从(O(N^2))到(O(N·\log(N)·\log(\log(N))))或更低。因此，对于评估(0\leq Q\leq P\leq2^N - 1)的(M)个模(2^N)的二项式系数(C(P, Q))，总的时间复杂度为(O((N^3 + M·N^2·\log(N))·\text{乘法}(N)+N^4))。预处理之后，我们实际上可以计算模任何(2^R)（(R\leq N)）的二项式系数。对于更大的(P)和(Q)值，必须首先使用卢卡斯定理的变体，以便将计算简化为评估多个（(O(\log(P)))）模(2^N)的二项式系数(C(P', Q'))（或受限类型的阶乘(P'!)），其中(0\leq Q'\leq P'\leq2^N - 1)。
