A new algorithm for generating integer partitions and its parallel implementations on CPU and FPGA

• Autorzy: Nałęcz Marek , Mazurek Gustaw

Identyfikatory

DOI

10.24425/ijet.2025.155467

• Języki publikacji: EN

Abstrakty

EN

In this paper, the long-known bit representation of integer partitions was used in a novel way to develop an algorithm for generating the next partition of an integer n. This algorithm is both loopless and conditionless (and therefore has strictly constant execution time). These features lead to an efficient and highly scalable parallel implementation on a modern multi-core CPU processor or a modern FPGA chip. In the CPU case, just 30 processor clock cycles are required to generate the next partition when n < 128. In the latter case, a single one of the parallel instances uses only 1,595 look-up tables and 962 registers for n < 128. It can produce the next partition in just 6 clock cycles. Even cost-effective FPGAs can hold a few dozen such instances.

Słowa kluczowe

EN

parallel combinatorial algorithms; integer partitions; field-programmable gate array; bitwise operations

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2025
• Tom: Vol. 71, No. 4
• Strony: 13
• Opis fizyczny: Bibliogr., 24 poz., rys.

Twórcy

autor

Nałęcz Marek

• Warsaw University of Technology, Poland

autor

Mazurek Gustaw

• Warsaw University of Technology, Poland

Bibliografia

• [1] D. E. Knuth, The art of computer programming. Upper Saddle River, NJ, USA: Addison-Wesley Professional, Jan. 2011, vol. 4A / Combinatorial algorithms, Part 1.
• [2] J. T. Butler and T. Sasao, “High-speed hardware partition generation,” ACM Transactions on Reconfigurable Technology and Systems, vol. 7, no. 4, pp. 1-17, Dec. 2014. [Online]. Available: https://doi.org/10.1145/2629472
• [3] T. B. Preußer and M. R. Engelhardt, “Putting queens in carry chains, №27,” Journal of Signal Processing Systems, vol. 88, no. 2, pp. 185-201, Aug. 2017. [Online]. Available: https://doi.org/10.1007/s11265-016-1176-8
• [4] P. Erdős and J. Lehner, “The distribution of the number of summands in the partitions of a positive integer,” Duke Mathematical Journal, vol. 8, no. 2, pp. 335-345, Jun. 1941. [Online]. Available: https://doi.org/10.1215/s0012-7094-41-00826-8
• [5] L. Comtet, Advanced combinatorics. The art of finite and infinite expansions, Revised and enlarged ed. Dordrecht, Holland: D. Reidel Publishing Company, 1974. [Online]. Available: https://doi.org/10.1007/978-94-010-2196-8
• [6] H. Gupta, C. E. Gwyther, and J. C. P. Miller, Tables of partitions, ser. Royal Society Mathematical Tables. Cambridge: Cambridge University Press, 1962, vol. 4.
• [7] J. K. S. McKay, “Algorithm 371: Partitions in natural order,” Communications of the ACM, vol. 13, no. 1, p. 52, Jan. 1970. [Online]. Available: https://doi.org/10.1145/361953.361980
• [8] A. Zoghbi and I. Stojmenović, “Fast algorithms for genegrating integer partitions,” International Journal of Computer Mathematics, vol. 70, no. 2, pp. 319-332, Jan. 1998. [Online]. Available: https://doi.org/10.1080/00207169808804755
• [9] A. Curiel and A. Genitrini, “Lexicographic unranking algorithms for the twelvefold way,” in 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024), ser. Leibniz International Proceedings in Informatics (LIPIcs), C. Mailler and S. Wild, Eds., vol. 302. Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Jul. 2024, pp. 17:1-17:14. [Online]. Available: https://doi.org/10.4230/LIPICS.AOFA.2024.17
• [10] M. B. Wells, Elements of combinatorial computing. Oxford, UK: Pergamon Press, 1971. [Online]. Available: https://doi.org/10.1016/c2013-0-05582-X
• [11] S. G. Akl and I. Stojmenović, Parallel computing: paradigms and appli-cations. London, UK: International Thomoson Computer Press, 1996, ch. Generating combinatorial objects on a linear array of processors, pp. 639-670.
• [12] F. Stockmal, “Algorithm 95: Generation of partitions in part-count form,” Communications of the ACM, vol. 5, no. 6, p. 344, Jun. 1962. [Online]. Available: https://doi.org/10.1145/367766.368163
• [13] E. M. Klimko, “An algorithm for calculating indices in Faà di Bruno’s formula,” BIT Numerical Mathematics, vol. 13, no. 1, pp. 38-49, 1973. [Online]. Available: https://doi.org/10.1007/bf01933522
• [14] E. M. Reingold, J. Nievergelt, and N. Deo, Combinatorial algorithms: Theory and practice. Englewood Cliffs, NJ, USA: Prentice Hall, Jun. 1977.
• [15] S. Comét, “On the machine calculation of characters of the symmetric group,” in Tolfte Skandinaviska Matematikerkongressen, Comptes rendus, Lund, Sweden, Aug., 10-15 1953, pp. 18-23.
• [16] ——, “Notations for partitions,” Mathematical Tables and Other Aids to Computation, vol. 9, no. 52, pp. 143-146, Oct. 1955. [Online]. Available: https://doi.org/10.2307/2002049
• [17] E. S. Page and L. B. Wilson, An introduction to computational combi-natorics, ser. Cambridge Computer Science Texts. London: Cambridge University Press, 1979, no. 9.
• [18] G. E. Andrews, The theory of partitions, ser. Encyclopedia of Mathematics and its Applications. Cambridge University Press, Dec. 1984, vol. 2. [Online]. Available: https://doi.org/10.1017/cbo9780511608650
• [19] D. Stanton and D. White, Constructive combinatorics, ser. Undergraduate Texts in Mathematics. New York, USA: Springer, 1986. [Online]. Available: https://doi.org/10.1007/978-1-4612-4968-9
• [20] I. Stojmenović, “Listing combinatorial objects in parallel,” International Journal of Parallel, Emergent and Distributed Systems, vol. 21, no. 2, pp. 127-146, Apr. 2006. [Online]. Available: https://doi.org/10.1080/17445760500355777
• [21] J. K. S. McKay, “Algorithm 263: Partition generator,” Communications of the ACM, vol. 8, no. 8, p. 493, Aug. 1965. [Online]. Available: https://doi.org/10.1145/365474.366063
• [22] Z. Kokosiński and P. Halesiak, “FPGA generators of combinatorial configurations in a linear array model,” in 2008 International Symposium on Parallel and Distributed Computing. Kraków, Poland: IEEE, Jul. 2008, pp. 223-227. [Online]. Available: https://doi.org/10.1109/ispdc.2008.48
• [23] Digilent, “Nexys A7 reference manual,” Online, accessed May 21, 2025. [Online]. Available: https://digilent.com/reference/programmable-logic/nexys-a7/reference-manual
• [24] A. Zahir, A. Ullah, P. Reviriego, and S. R. U. Hassnain, “Efficient leading zero zount (LZC) implementations for Xilinx FPGAs,” IEEE Embedded Systems Letters, vol. 14, no. 1, pp. 35-38, Mar. 2022. [Online]. Available: https://doi.org/10.1109/les.2021.3101688