Функция GCD в matlab

Question

Я ищу способ реализовать функцию «gcd», используемую в Matlab на другом языке, но я действительно не могу понять, как она функционирует.

это говорит в http://www.mathworks.com/access/helpdesk/help/techdoc/ref/gcd.html что:

«[G, С, D] = НОД (A, B) возвращает как наибольший общий делитель массива G, а массивы С и D, которые удовлетворяют уравнению: A (i). * C (i) + B (i). * D (i) = G (i). "

, но ничего не говорит о том, как он вычисляет C и D.

я был бы признателен, если кто-то имеет более четкое представление об этом предмете! спасибо :)

Answer 1

документация Matlab относится к

Кнут, Дональд, Искусство программирования, Vol. 2, Addison-Wesley: Reading MA, 1973. Раздел 4.5.2, Алгоритм X.

У меня нет смелости перефразировать это для вас, но это все.

Answer 2

extended Euclidean algorithm.

(«Раздел 4.5.2 Алгоритм X» время это может быть показано на http://www.fitc.unc.edu.ar/javadev/math/previous/algorithms.html.)

Answer 3

Просто взгляните на источник, набрав

edit gcd 

, который открывает функцию в редакторе. Затем вы можете просматривать функцию по строкам.

Вместе со ссылками на другие две должности, это должно дать вам ответ.

Answer 4

Он использовал бы одну из основных схем, найденных по этой ссылке: The extended Euclidean algorithm.