Розробка швидкодіючого алгоритму біноміального арифметичного складання
DOI:
https://doi.org/10.15587/2706-5448.2024.301309Ключові слова:
двійкові біноміальні числа, арифметичне додавання, алгоритми біноміального арифметичного складання, динамічний масивАнотація
Об'єктом дослідження є метод та алгоритм арифметичного складання біноміальних чисел, що генеруються двійковими біноміальними системами числення. Відсутність біноміальної арифметики, зокрема операції додавання двійкових біноміальних чисел, певним чином перешкоджає їх впровадженню в інформаційні системи та побудові на їх основі інформаційно-комунікаційних технологій з комбінаторної оптимізації, генерування комбінаторних об'єктів, стиснення та шифрування даних.
У рамках підходу, який пропонується, замість оперування біноміальними коефіцієнтами проводяться тільки операції з їх верхніми та нижніми параметрами. При цьому вагові коефіцієнти двійкових біноміальних чисел, які додаються один до одного, представляються у вигляді двокомпонентних кортежів. З врахуванням цього в даній роботі представлений алгоритм біноміального арифметичного складання із застосуванням динамічних масивів.
Основна ідея, яка покладена в будову алгоритму біноміального арифметичного складання на основі динамічних масивів, полягає в тому, що здійснюється перехід від двомірної моделі підсумовування до одномірної. При цьому у динамічному масиві розміщуються тільки наявні, існуючі біноміальні коефіцієнти. Відповідно пошук рівних або більших за кількісним еквівалентом біноміальних коефіцієнтів відбувається у значно менших областях. У порівнянні з алгоритмом на основі матричних моделей це досить суттєво знижує обсяг часових витрат при проведенні операції підсумовування, а також зменшує вимоги до обсягу пам'яті, необхідної для розміщення двокомпонентних кортежів масиву складання.
У ході дослідження практично підтверджено зниження у декілька разів кількості машинних тактів, що потребується для проведення операцій пошуку необхідних елементів в динамічному масиві. Це призводить до підвищення швидкодії представленого алгоритму біноміального арифметичного складання на основі динамічних масивів. У свою чергу це обумовлює пришвидшення розв'язання інформаційних завдань з комбінаторної оптимізації, генерування комбінаторних об'єктів, стиснення та шифрування даних, для вирішення яких застосовується операція складання двійкових біноміальних чисел
Посилання
- Stakhov, A. P. (2014). A History, the Main Mathematical Results and Applications for the Mathematics of Harmony. Applied Mathematics, 5 (3), 363–386. doi: https://doi.org/10.4236/am.2014.53039
- Borysenko, O. A. (2007). Chyslo i systemy chyslennia v elektronnykh tsyfrovykh systemakh. Visnyk SumDU, 4, 71–76.
- Butler, T. J., Tsutomu, S. (1997). Redundant Multiple-Valued Number Systems: Report. Defense Technical Information center. Naval Postgraduate School Monterey CA Dept of Electrical and Computer engineering, 10. Available at: https://apps.dtic.mil/sti/pdfs/ADA599946.pdf Last accessed: 10.02.2024
- Borisenko, A. A. (2004). Binomialnyi schet. Teoriia i praktika. Sumy: ITD «Universitetskaia kniga», 170.
- Mezmaz, M., Leroy, R., Melab, N., Tuyttens, D. (2014). A Multi-core Parallel Branch-and-Bound Algorithm Using Factorial Number System. 2014 IEEE 28th International Parallel and Distributed Processing Symposium. Phoenix, 1203–1212. doi: https://doi.org/10.1109/ipdps.2014.124
- Cui, X., Cui, X., Ni, Y., Miao, M., Yufeng, J. (2017). An Enhancement of Crosstalk Avoidance Code Based on Fibonacci Numeral System for Through Silicon Vias. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 25 (5), 1601–1610. doi: https://doi.org/10.1109/tvlsi.2017.2651141
- Borysenko, O., Matsenko, S., Bobrovs, V. (2021). Binomial Number System. Applied Sciences, 11 (23), 11110. doi: https://doi.org/10.3390/app112311110
- Kulik, І. A., Shevchenko, M. S., Grinenko, V. V. (2022). Algoritm skladannia dvіikovikh bіnomіalnikh chisel. Sistemi obrobki іnformatcіi, 2 (169), 49–57.
- Kulyk, I. A., Shevchenko, M. S. (2021). Matrychna model skladannia dviikovykh binomialnykh chysel. Systemy obrobky informatsii, 1 (164), 45–54.
- Anderson, Ja. A. (2001). Discrete mathematics with combinatorics. Prentice-Hall, Inc., 960.
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2024 Igor Kulyk, Maryna Shevchenko, Anatolii Melnyk, Tetyana Protasova
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.
