The practical implementation of some algorithms related to the problem of number composing

DOI:

Review date:

Publish date:

Abstract: Among combinatorial algorithms of additive number theory the algorithms of the algorithms for listing compositions of natural numbers have a special place. On the one hand, ideologically, they are among the simplest algorithms in mentioned theory. On the other hand, they play a huge role in all applications somehow connected with the polynomial theorem. In recent years, due to the rapid development of the general theory of risk ideas underlying the polynomial theorem were involved to in the challenges of risk measurement in homogeneous systems of high dimensionality. Solving these problems requires providing mass listing compositions numbers of fixed length and calculating the amount of such compositions for sufficiently large values of both number and the length of composition. In these circumstances, the most urgent task is in effective implementation of these algorithms. The presented article is devoted to the questions related with the synthesis of efficient algorithms for listing the compositions of fixed length and calculating the amount of such compositions. As a methodological base of this study authors use certain facts of set theory, approaches of theory of complex algorithms, as well as some basic results of the theory of numbers. Within this paper, the author propose a new efficient implementation of two algorithms: algorithm for listing all the compositions of fixed length based on the idea of multiset representation of the number partitions and algorithm for calculating the amounts of the compositions of given kind, implemented without involvement of high bitness machine arithmetic. The article shows not only an estimate of the complexity of the proposed algorithms but also presents the results of numerical experiments demonstrating the effectiveness of the implementation of the algorithms discussed in the VBA programming language.