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

Бінарны алгарытм Еўкліда — метад знаходжання найбольшага агульнага дзельніка двух цэлых лікаў. Гэты алгарытм больш хуткі, чым звычайны алгарытм Еўкліда, бо замест павольных аперацый дзялення і множання выкарыстоўваюцца зрухі. Алгарытм быў вядомы яшчэ ў Кітаі 1-га стагоддзя, але апублікаваны быў толькі ў 1967 годзе ізраільскім фізікам і праграмістам Джозэфам Стайнам. Ён заснаваны на выкарыстанні наступных уласцівасцей НАД:

• НАД(2m, 2n) = 2 НАД(m, n),
• НАД(2m, 2n+1) = НАД(m, 2n+1),
• НАД(-m, n) = НАД(m, n).

Алгарытм

1. НАД(0, n) = n; НАД(m, 0) = m; НАД(m, m) = m;
2. НАД(1, n) = 1; НАД(m, 1) = 1;
3. Калі m, n цотныя, то НАД(m, n) = 2*НАД(m/2, n/2);
4. Калі m цотнае, n няцотнае, то НАД(m, n) = НАД(m/2, n);
5. Калі n цотнае, m няцотнае, то НАД(m, n) = НАД(m, n/2);
6. Калі m, n няцотныя і n > m, то НАД(m, n) = НАД((n-m)/2, m);
7. Калі m, n няцотныя і n < m, то НАД(m, n) = НАД((m-n)/2, n);

Паколькі алгарытм з'яўляецца хваставой рэкурсіяй, то рэкурсіі можна замяніць ітэрацыямі.

Існуе таксама бінарная версія абагульненага алгарытму Еўкліда, апісаная ў кнізе Д. Кнута.

Гл. таксама

• Алгарытм Еўкліда
• Найбольшы агульны дзельнік

Літаратура

• Виноградов И. М. Основы теории чисел. М.-Л.: Гос. изд. технико-теоретической литературы, 1952, 180 с.

Спасылкі

У Вікікнігах можна знайсці дадатковыя матэрыялы па тэме:

«Примеры реализации алгоритма Евклида»

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