Алгоритм умножения чисел в двоичной лунной арифметике с использованием быстрого преобразования Фурье и некоторые его применения
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. DOI: https://doi.org/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. DOI: https://doi.org/10.5220/0001317002720279
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. DOI: https://doi.org/10.35470/2226-4116-2024-13-4-288-295
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. DOI: https://doi.org/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. DOI: https://doi.org/10.1007/s10958-011-0487-3
Загрузки
Опубликован
Выпуск
Раздел
Лицензия
Copyright (c) 2026 Svetlana Korabelshchikova, Boris Melnikov, Van Vinh Dang
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
