У даній роботі представлені результати обчислювального експерименту, метою якого є уточнення реальної швидкодії арифметичних алгоритмів з використанням арифметики довільної точності при реалізації на мовах програмування C++ та Python. Як математичну модель для арифметичних алгоритмів обрана цілочисельна «машина, що складає». «Машина, що складає» - це математична абстракція, введена Р. Флойдом та Д. Кнутом, суть якої полягає у тому, що лише за допомогою операцій додавання, віднімання, порівняння, присвоювання та обмеженої кількості регістрів можна з прийнятною обчислювальною ефективністю виразити більш складні операції, такі як знаходження лишку за модулем, множення, знаходження найбільшого спільного дільника, піднесення до степеня за модулем. Особливістю даної реалізації є використання арифметики довільної точності, що може бути корисним для використання у криптографічних алгоритмах. Ключові слова: C++, Python, GMP, додавання, віднімання, найбільший спільний дільник, піднесення до степеня, числа Фібоначчі. В данной работе представлены результаты вычислительного эксперимента, целью которого является уточнение реальной производительности арифметических алгоритмов с использованием арифметики произвольной точности при реализации на языках программирования C++ и Python. Как математическая модель для арифметических алгоритмов выбрана целочисленная «складывающая машина». «Складывающая машина» - это математическая абстракция, введённая Р. Флойдом и Д. Кнутом, суть которой заключается в том, что с помощью только операций сложения, вычитания, сравнения, присваивания и ограниченного количества регистров можно с приемлемой вычислительной эффективностью выразить более сложные операции, такие как нахождение остатка по модулю, умножение, нахождение наибольшего общего делителя, возведение в степень по модулю. Особенностью данной реализации является использование арифметики произвольной точности, что может быть полезным для использования в криптографических алгоритмах. Ключевые слова: C++, Python, GMP, сложение, вычитание, наибольший общий делитель, возведение в степень, числа Фибоначчи. This paper presents the results of the numerical experiment, which aims to clarify the actual performance of arithmetic algorithms implemented in C ++ and Python programming languages using arbitrary precision arithmetic. "Addition machine" has been chosen as a mathematical model for integer arithmetic algorithms. "Addition machine" is a mathematical abstraction, introduced by R. Floyd and D. Knuth. The essence of "addition machine" is the following: using only operations of addition, subtraction, comparison, assignment and a limited number of registers it is possible to calculate more complex operations such as finding the residue modulo, multiplication, finding the greatest common divisor, exponentiation modulo with reasonable computational efficiency. One of the features of this implementation is the use of arbitrary precision arithmetic, which may be useful in cryptographic algorithms.
1) введення: read x; «Машини, що складають» можуть працювати як з цілими числами, так і з дійсними. У даній роботі усі операції вважаємо такими, що здійснюються над цілими числами, тому описаний пристрій називається цілочисельною «машиною, що складає».
Метою даної роботи є дослідження ефективності алгоритмів цілочисельної «машини, що складає» при її реалізації за допомогою мов програмування С++ і Python, використовуючи арифметику довільної точності. Використання арифметики довільної точності було вибране у зв'язку із можливим подальшим застосуванням результатів даного дослідження у криптографії. Методика дослідження У даній роботі обмежимося розглядом і порівнянням таких операцій над цілими числами: 1) множення двох чисел; 2) піднесення до степеня за модулем; 3) знаходження лишку за модулем; 4) знаходження найбільшого спільного дільника (НСД).
У роботі [
Основною ідеєю алгоритму знаходження лишку від цілочисельного ділення, який був запропонований
Р. Флойдом та Д. Кнутом у [
P3: read x; read y; { вважається, що x > 0, y ≥ 0 } z ← y; z ← z + z; while not y >= z do begin while x >= z do <y, z> ← <z, y + z> repeat if x >= y then x ← x - y; <y, z> ← <z - y, y> until y >= z; <x, y> ← <y, x>; z ← y; z ← z + z; end; write x.
Алгоритм обчислення найбільшого спільного дільника НСД(x,y) (P3) у командах регістрової машини
виглядає наступним чином [
І, нарешті, останній важливий алгоритм обчислення xy mod z (P5) за допомогою «машини, що складає»
виконується наступним чином, враховуючи допоміжний алгоритм P4 [
P5: read x; read y; read z; <r, s, t> ← <Fλy, Fλy+1, yR> { x = xl, w = xl+1, l = 1 } x ← x mod z; w ← x; u ← 1; repeat if t >= r then begin t ← t - r; u ← (uw) mod z; end; <r, s> ← <s - r, r>; <x, w> ← <w, (xw) mod z>; { l = l + 1 } until r >= s; write u. Результати дослідження
Для реалізації алгоритмів були використані мови програмування С++ з бібліотекою арифметики
довільної точності GMP [
Характеристики персонального комп'ютера, на якому було проведене тестування реалізованих алгоритмів, такі: процесор Intel Pentium Duo 2.8 ГГц, 4 Гб оперативної пам’яті, ОС Ubuntu 14.04 LTS x64. Версії програмного забезпечення: GCC 4.8.4, GMP 5.1.3, Python 2.7.6.
На рис. 1 показано результати порівняння швидкодії алгоритму P1 (x mod y) на персональному комп’ютері при реалізації його за допомогою мов програмування С++ та Python. Рис. 1. Порівняння часу виконання операції знаходження лишку від ділення при реалізації на мовах програмування C++ та Python На рис. 2 показано результати порівняння швидкодії алгоритму P2 (x[y/z]) на персональному комп’ютері при реалізації його за допомогою мов програмування С++ та Python.
Рис. 2. Порівняння часу виконання операції множення до степеня при реалізації
на мовах програмування C++ та Python На рис. 3 показано результати порівняння швидкодії алгоритму P3 (НСД(x, y)) на персональному комп’ютері при реалізації його за допомогою мов програмування С++ та Python.
Рис. 3. Порівняння часу виконання операції знаходження найбільшого спільного дільника при реалізації на мовах програмування C++ та Python
В результаті дослідження були отримані чисельні характеристики ефективності алгоритмів «машини,
що складає» та побудовані відповідні графіки, що дозволило на практиці підтвердити та уточнити теоретичні
оцінки складності даних алгоритмів, виведені Р. Флойдом та Д. Кнутом. Одним із практичних застосувань
розглянутих алгоритмів може бути їх ефективне використання на спеціально побудованому апаратному
забезпеченні, наприклад, для схеми RSA [
Експериментальним шляхом були отримані такі основні результати: • для C++/GMP середня швидкодія вбудованих складних операцій є у 47 разів більшою, ніж їх аналогів, реалізованих за допомогою «машини, що складає»;
• для Python середня швидкодія вбудованих складних операцій є у 228 разів більшою, ніж їх аналогів, реалізованих за допомогою «машини, що складає»;
• реалізація на C++/GMP арифметичних алгоритмів «машини, що складає» є у 3,8 разу швидшою за аналогічну реалізацію на Python.
Цікавим фактом є те, що швидкодія алгоритму НСД(x,y) на C++ є повністю однаковою як для
вбудованої операції mpz_gcd() з бібліотеки GMP [
Отже, результати експериментального порівняння надають можливість зробити висновок про те, що реалізація арифметичних алгоритмів над цілими числами довільної точності на С++/GMP є в середньому у 3,8 раз швидшою за Python-реалізацію, але у той же час процес програмування на С++ є складнішим.
Загалом, інтерпретатор Python показав досить високу швидкодію, що разом з вбудованою арифметикою довільної точності, зручністю програмування та різноманіттям програмних модулів робить мову Python одним з перспективних інструментів для дослідників в області інформатики та математики. У той же час, є клас задач, які можуть бути ефективно вирішені тільки за допомогою мов C/C++ (відповідно, і за допомогою мови Assembler), наприклад, написання драйверів пристроїв, програмування мікроконтролерів. Тому для кожного класу задач необхідно правильно вибирати інструменти з урахуванням пріоритетів та уникати суперечок з приводу «найкращої» або «ідеальної» мови програмування.