Алгоритм умножения чисел в двоичной лунной арифметике с использованием быстрого преобразования Фурье и некоторые его применения
DOI:
https://doi.org/10.32603/2071-2340-2026-2-34-42Ключевые слова:
задача о рюкзаке, лунная арифметика, быстрое преобразование ФурьеАннотация
В статье рассматривается алгоритм умножения многозначных чисел в двоичной лунной арифметике. Алгоритмы умножения и сложения многозначных чисел в лунной арифметике имеют сходство с обычными алгоритмами сложения и умножения многозначных чисел. Различие заключается в том, что при поразрядном сложении выполняется выбор максимального из слагаемых, а при поразрядном умножении — выбор минимального. Эти операции могут быть реализованы с использованием быстрого преобразования Фурье (БПФ). Как показали исследования, в двоичном случае это существенно влияет на скорость программной реализации алгоритма. Существует множество вариантов распараллеливания соответствующих вычислений для алгоритма БПФ, и один из них рассмотрен в данной работе. Также в статье обсуждается применение умножения многозначных двоичных чисел в лунной арифметике к решению задачи о неограниченном рюкзаке. Задача о неограниченном рюкзаке представляет собой простое обобщение классической задачи о рюкзаке, когда любой предмет можно выбирать произвольное количество раз. Рассмотренные алгоритмы применимы к частному случаю этой задачи, когда требуется взять фиксированное количество предметов.
Библиографические ссылки
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.
Загрузки
Опубликован
Выпуск
Раздел
Лицензия
Copyright (c) 2026 Svetlana Korabelshchikova, Boris Melnikov, Van Vinh Dang
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
