Fonction GCD dans matlab

Question

Je suis à la recherche d'un moyen d'implémenter la fonction "gcd" utilisée dans matlab dans une autre langue mais je ne comprends vraiment pas comment cela fonctionne.

il est dit dans http://www.mathworks.com/access/helpdesk/help/techdoc/ref/gcd.html que:

« [G, C, D] = gcd (A, B) retourne à la fois le plus grand réseau de diviseur commun G, et les tableaux C et D, qui satisfont à l'équation: A (i). * C (i) + B (i). * D (i) = G (i). "

mais il ne dit rien sur la façon dont il calcule C et D.

Je vous serais reconnaissant si quelqu'un a une idée plus claire sur ce sujet! remerciements

Answer 1

La documentation Matlab fait référence à

Knuth, Donald, L'art de la programmation informatique, vol. 2, Addison-Wesley: Lecture MA, 1973. Section 4.5.2, Algorithme X.

Je n'ai pas la témérité de paraphraser cela pour vous, mais tout est là.

Answer 2

Le extended Euclidean algorithm.

("Section 4.5.2 algorithme X" étant ce qui peut être montré dans http://www.fitc.unc.edu.ar/javadev/math/previous/algorithms.html.)

Answer 3

Il suffit de jeter un oeil à la source en tapant

edit gcd 

qui ouvre la fonction dans l'éditeur. Vous pouvez ensuite parcourir la fonction ligne par ligne.

Avec les références dans les deux autres messages, cela devrait vous donner la réponse.

Answer 4

Il utiliserait l'un des schémas de base trouvés dans ce lien sur The extended Euclidean algorithm.