A Fast Algorithm for Computing Binomial Coefficients Modulo Powers of Two
المؤلف
المصدر
العدد
المجلد 2013، العدد 2013 (31 ديسمبر/كانون الأول 2013)، ص ص. 1-7، 7ص.
الناشر
Hindawi Publishing Corporation
تاريخ النشر
2013-11-06
دولة النشر
مصر
عدد الصفحات
7
التخصصات الرئيسية
الطب البشري
تكنولوجيا المعلومات وعلم الحاسوب
الملخص EN
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 OlogP binomial coefficients C(P′,Q′) (or restricted types of factorials P′!) modulo 2N with 0≤Q′≤P′≤2N-1.
نمط استشهاد جمعية علماء النفس الأمريكية (APA)
Andreica, Mugurel Ionut. 2013. A Fast Algorithm for Computing Binomial Coefficients Modulo Powers of Two. The Scientific World Journal،Vol. 2013, no. 2013, pp.1-7.
https://search.emarefa.net/detail/BIM-1033268
نمط استشهاد الجمعية الأمريكية للغات الحديثة (MLA)
Andreica, Mugurel Ionut. A Fast Algorithm for Computing Binomial Coefficients Modulo Powers of Two. The Scientific World Journal No. 2013 (2013), pp.1-7.
https://search.emarefa.net/detail/BIM-1033268
نمط استشهاد الجمعية الطبية الأمريكية (AMA)
Andreica, Mugurel Ionut. A Fast Algorithm for Computing Binomial Coefficients Modulo Powers of Two. The Scientific World Journal. 2013. Vol. 2013, no. 2013, pp.1-7.
https://search.emarefa.net/detail/BIM-1033268
نوع البيانات
مقالات
لغة النص
الإنجليزية
الملاحظات
Includes bibliographical references
رقم السجل
BIM-1033268
قاعدة معامل التأثير والاستشهادات المرجعية العربي "ارسيف Arcif"
أضخم قاعدة بيانات عربية للاستشهادات المرجعية للمجلات العلمية المحكمة الصادرة في العالم العربي
تقوم هذه الخدمة بالتحقق من التشابه أو الانتحال في الأبحاث والمقالات العلمية والأطروحات الجامعية والكتب والأبحاث باللغة العربية، وتحديد درجة التشابه أو أصالة الأعمال البحثية وحماية ملكيتها الفكرية. تعرف اكثر