Question

Скажите, а чем отличается обычный алгоритм Евклида от модифицированного алгоритма Евклида?

Answer 1

Отличается скоростью

В обычном алгоритме Евклида мы последовательно вычитаем из большего меньшее, пока они не станут равны.

В модифицированном мы берем остаток от деления большего на меньшее, пока одна из переменных не станет равной 0.

То есть если взять числа 36 и 48, то

Обычный алгоритм Евклида:

1) 48 - 36 = 12

2) 36 - 12 = 24

3) 24 - 12 = 12

4) Вывод 12

Модифицированный:

1) 48 %(mod) 36 = 12

2) 36 %(mod) 12 = 0

3) Вывод 12

Разница в 1 шаг из-за того, что числа маленькие, с большими числами разница в количестве шагов больше.