An Algorithm for Multiplying Numbers in Binary Lunar Arithmetic Using the Fast Fourier Transform and Some of Its Applications
DOI:
https://doi.org/10.32603/2071-2340-2026-2-34-42Keywords:
knapsack problem, lunar arithmetic, fast Fourier transformAbstract
The article considers an algorithm for multiplying multi-digit numbers in binary lunar arithmetic. The algorithms for multiplication and addition of multi-digit numbers in lunar arithmetic are similar to the usual algorithms for addition and multiplication of multi-digit numbers. The difference is that when adding digitwise, the maximum of the addends is selected, and when multiplying digitwise, the minimum is selected. These operations can be implemented using the fast Fourier transform (FFT). As studies have shown, in the binary case this significantly affects the speed of the software implementation of the algorithm. There are many variants of parallelizing the corresponding computations for the FFT algorithm, and one of them is considered in this paper. The article also discusses the application of multiplication of multi-digit binary numbers in lunar arithmetic to solving the unbounded knapsack problem. The unbounded knapsack problem is a simple generalization of the classical knapsack problem, where any item can be taken any number of times. The considered algorithms are applicable to a special case of this problem, when it is required to take a fixed number of items.
References
D. Applegate, M. LeBrun, and N. J. A. Sloane, "Dismal Arithmetic," 2011, arxiv.org/pdf/1107.1130v2.pdf.
A. Shen, Programming: theorems and problems, 6th ed., Moscow: Moscow Center for Continuing Mathematical Education, 2017, (in Russian).
B. F. Melnikov, "Heuristics in programming of nondeterministic games," Programming and Computer Software, vol. 27, no. 5, pp. 277-288, 2001, doi: 10.1023/A:1012345111076.
B. Melnikov, A. Radionov, A. Moseev, and E. Melnikova, "Some specific heuristics for situation clustering problems," in ICSOFT 2006 - 1st International Conference on Software and Data Technologies, Proceedings, Setubal, Portugal: Polytechnic Institute of Setubal, 2006, pp. 272-279.
B. F. Melnikov and A. G. Panin, "Parallel implementation of the multi-heuristic approach in the task of comparing genetic sequences," Vector of Science of Togliatti State University, no. 4(22), pp. 83-86, 2012, (in Russian).
B. Melnikov, "New algorithms for restoring DNA matrix and their statistical study," Cybernetics and Physics, no. 4, pp. 288-295, 2024, doi: 10.35470/2226-4116-2024-13-4-288-29.
B. F. Melnikov, S. Yu. Korabelshchikova, and V. N. Dolgov, "On the task of extracting the root from the language," International Journal of Open Information Technologies, vol. 7, no. 3, pp. 1-6, 2019.
S. Yu. Korabelshchikova, "Semilattice of roots from formal languages of a special kind," International Journal of Open Information Technologies, vol. 8, no. 2, pp. 1-6, 2020, (in Russian).
L. V. Zyablitseva, S. Yu. Korabelshchikova, and T. V. Danilova, "Representation of semigroups of right zeros and their semilattices by a transformation semigroup," University proceedings. Volga region. Physical and mathematical sciences, no. 1 (61), pp. 33-44, 2022, (in Russian), doi: 10.21685/2072-3040-2022-1-4.
G. G. Ryabov, "Hausdorff metric on faces of the n-cube," Journal of Mathematical Sciences, vol. 177, no. 4, pp. 619-622, 2011, doi: 10.1007/s10958-011-0487-3.
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Svetlana Korabelshchikova, Boris Melnikov, Van Vinh Dang
This work is licensed under a Creative Commons Attribution 4.0 International License.
