Быстрый алгоритм Евклида вычисления НОД
Запись от Thinker размещена 10.07.2013 в 10:03
Заинтересовал вопрос о различных реализациях алгоритма Евклида для неотрицательных целых чисел. Ниже привожу алгоритмы, собственноручно написанные, исходя из теоретического материала. Каждый алгоритм можно модифицировать в ту или иную сторону. Считается, что бинарный алгоритм работает быстрее, но тесты показывают, что во многих случаях два первых алгоритма работают быстрее бинарного. 1. обычный алгоритм Евклида через остатки Кликните здесь для просмотра всего текста
2. алгоритм Евклида через разности Кликните здесь для просмотра всего текста
3. бинарный алгоритм Евклида Кликните здесь для просмотра всего текста
4. еще один бинарный алгоритм Кликните здесь для просмотра всего текста
|