Задание 3: вариации алгоритма Евклида

  1. Используя операции с длинными целыми числами, реализованными в задании 1, реализовать следующие вариации алгоритма Евклида:
    • классический алгоритм;
    • вариация классического алгоритма для нахождения наименьшего общего кратного;
    • двоичная версия (используются вычитание и сдвиги - "умножение/деление на 2k";
    • расширенный классический алгоритм: для заданных a, bZ найти d, s, tZ, такие, что d = gcd(a, b) и a⋅s + b⋅t = d;
    • двоичная версия расширенного алгоритма.
  2. Разработать и реализовать серию тестов, определяющих корректность реализованных алгоритмов.
  3. Реализовать серию тестов быстродействия реализованных алгоритмов. Построить зависимости времени выполнения от длины (длин) входных данных, сохранить их в файле, пригодном для построения графиков при помощи ПО GNUPlot, Octave, Maple, Excel, ...