zbMATH — the first resource for mathematics

Fast computation of binomial coefficients. (English) Zbl 1460.65019
Summary: One problem that arises in computation involving large numbers is precision. In certain situations, the result might be represented by the standard data type, but arithmetic precision might be compromised when dealing with large numbers in the course to the result. Binomial coefficients are an example that suffer from this torment. In the present paper, we review numerical methods to compute the binomial coefficients: Pascal’s recursive method; prime factorization to cancel out terms; gamma function approximation; and a simplified iterative method that avoids loss in precision. Acknowledging that the binomial coefficients might be obtained by a successive convolution of a simple discrete rectangular function, we propose a different approach based on the discrete Fourier transform and another based on its fast implementation. We analyze and compare performance and precision of all of them. The proposed methods overcome the previous ones when computing all coefficients for a given level $$n$$, attaining better precision for large values of $$n$$.
MSC:
 65D20 Computation of special functions and constants, construction of tables 65T50 Numerical methods for discrete and fast Fourier transforms
Software:
WolframAlpha; Matlab; SumTools; Octave
Full Text:
References:
 [1] Eaton, J.W.: Gnu octave (version 5.1.0). https://octave.org/doc/v5.1.0/Numeric-Data-Types.html (2018) [2] Goetgheluck, P., Computing binomial coefficients, Am. Math. Mon., 94, 4, 360 (1987) · Zbl 0617.05004 [3] Wolfram Research, Inc. Wolfram—alpha. https://www.wolframalpha.com/ [4] Keprt, A.: Simple and fast computation of binomial coefficients. In: Wofex 2006, pp. 346-351, VŠB Technical University, Ostrava, Czech Republic, ISBN 80-248-1152-9 (2006) [5] Knuth, D.E.: The Art of Computer Programming: Volume 1: Fundamental Algorithms. Addison Wesley. ISBN 0-201-89683-4 (1997) · Zbl 0895.68055 [6] Koepf, W.: Hypergeometric Summation: An Algorithmic Approach to Summation and Special Function Identities (Advanced Lectures in Mathematics). Vieweg Teubner Verlag. ISBN 3528069503 (1998) · Zbl 0909.33001 [7] Manolopoulos, Y., Binomial coefficient computation: recursion or iteration?, ACM SIGCSE Bullet., 34, 4, 65 (2002) [8] McKeeman, B.: Matlab performance measurement. Technical report, Mathworks. https://www.mathworks.com/matlabcentral/fileexchange/18510-matlab-performance-measurement. [Online; accessed 03-Feb-2020] (2008) [9] Rolfe, T., Binomial coefficient recursion, ACM SIGCSE Bullet., 33, 2, 35 (2001) [10] Wells, D.: The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books. ISBN 0140080295 (1987) [11] Widrow, B., Kollár, I.: Quantization Noise: Roundoff Error in Digital Computation, Signal Processing, Control, and Communications. Cambridge University Press. ISBN 9780521886710 (2008) [12] Wikipedia contributors. Double-precision floating-point format - Wikipedia, the free encyclopedia. https://en.wikipedia.org/wiki/Double-precision_floating-point_format. [Online; accessed 17-May-2019] (2019)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.