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

З пляцоўкі Вікіпедыя
Jump to navigation Jump to search

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

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

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

Зноскі[правіць | правіць зыходнік]

  1. Дональд Кнут "Искусство программирования" п. 4.5.2 задача 39

Гл. таксама[правіць | правіць зыходнік]

Літаратура[правіць | правіць зыходнік]

Спасылкі[правіць | правіць зыходнік]