Бінарны алгарытм Еўкліда — метад знаходжання найбольшага агульнага дзельніка двух цэлых лікаў. Гэты алгарытм больш хуткі, чым звычайны алгарытм Еўкліда, бо замест павольных аперацый дзялення і множання выкарыстоўваюцца зрухі. Алгарытм быў вядомы яшчэ ў Кітаі 1-га стагоддзя, але апублікаваны быў толькі ў 1967 годзе ізраільскім фізікам і праграмістам Джозэфам Стайнам. Ён заснаваны на выкарыстанні наступных уласцівасцей НАД:
НАД(2m, 2n) = 2 НАД(m, n), НАД(2m, 2n+1) = НАД(m, 2n+1), НАД(-m, n) = НАД(m, n).
Алгарытм
НАД(0, n) = n; НАД(m, 0) = m; НАД(m, m) = m; НАД(1, n) = 1; НАД(m, 1) = 1; Калі m, n цотныя, то НАД(m, n) = 2*НАД(m/2, n/2); Калі m цотнае, n няцотнае, то НАД(m, n) = НАД(m/2, n); Калі n цотнае, m няцотнае, то НАД(m, n) = НАД(m, n/2); Калі m, n няцотныя і n > m, то НАД(m, n) = НАД((n-m)/2, m); Калі m, n няцотныя і n < m, то НАД(m, n) = НАД((m-n)/2, n);
Паколькі алгарытм з'яўляецца хваставой рэкурсіяй, то рэкурсіі можна замяніць ітэрацыямі.
Існуе таксама бінарная версія абагульненага алгарытму Еўкліда, апісаная ў кнізе Д. Кнута Дональд Кнут "Искусство программирования" п. 4.5.2 задача 39.
Зноскі
Гл. таксама Алгарытм Еўкліда Найбольшы агульны дзельнік
Літаратура Виноградов И. М. Основы теории чисел. М.-Л.: Гос. изд. технико-теоретической литературы, 1952, 180 с.
Спасылкі
Бинарный алгоритм Евклида
Катэгорыя:Тэорыя лікаў Катэгорыя:Крыптаграфія Катэгорыя:Алгарытмы