Точна арифметика цілих чисел

** Лабораторна робота № 2 **

Написати клас, що реалізує динамічне подання “довгих” цілих чисел. Довжина (розрядність) і основа позиційного числення (якщо алгоритм передбачає) вводяться як параметр. Передбачити в класі такі методи, кожного разу оцінюючи швидкість їх виконання шляхом обчислення кількості тактів таймера. Результати ділення в пп. 4 і 5 подати у вигляді числа з плаваючою точкою.

1. Множення невід’ємних цілих чисел методом Карацуби [Кнут, т.2, с. 336].
2. Множення невід’ємних цілих чисел методом Тоома-Кука [Кнут, т.2, с. 340].
3. Множення невід’ємних цілих чисел методом Шенхаге [Кнут, т.2, с. 344].
4. Множення невід’ємних цілих чисел методом Штрассена [Кнут, т.2, с. 347–350].
5. Обчислення оберненої величини з високою точністю (алгоритм Кука) [Кнут, т.2, с. 340].
6. Ділення цілих чисел алгоритмом Кука [Кнут, т.2, с. 340].
7. Перевірка простоти числа методом Лемера [Шнайер, с. 297].
8. Перевірка простоти числа методом Рабіна–Міллера [Шнайер, с. 298].
9. Перевірка простоти числа методом Соловея–Штрассена [Шнайер, с. 298].
10. Перевірка простоти числа методом Фробеніуса (https://en.wikipedia.org/wiki/Quadratic_Frobenius_test).