Бінарны алгарытм вылічэння НАД

Бінарны алгарытм Еўкліда — метад знаходжання найбольшага агульнага дзельніка двух цэлых лікаў. Гэты алгарытм больш хуткі, чым звычайны алгарытм Еўкліда, бо замест павольных аперацый дзялення і множання выкарыстоўваюцца зрухі. Алгарытм быў вядомы яшчэ ў Кітаі 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 с.

 Спасылкі 

 Бинарный алгоритм Евклида 

Катэгорыя:Тэорыя лікаў
Катэгорыя:Крыптаграфія
Катэгорыя:Алгарытмы