## Modified GCD

Version 1.0.0.0 (11.7 KB) by
Modification in MATLAB's gcd.m by suppressing calculation of u2, v2 and t2 at intermediate steps

Updated 14 Jul 2005

Functional Description of gcd_SK_GHB.m :
-----------------------------------------------------

This method of finding gcd is a modification over MATLAB's gcd.m ;
it is based on the suppression of calculation of u2, v2 and t2 at
intermediate steps - as observed by Gordon H. Bradley ? and
as given in 4.5.2, P343 of Vol 2, 3rd Ed of D E Knuth's book.

However, when either input a or b is negative, or both are negative,
I have observed that we need to consider absolute values thus :
abs (a(k)) and abs (b(k)) ie, abs(u) and abs(v) as per the book's notation :
ie, u * u1 + v * u2 = u3
in P343 gets modified to :
abs(u) * u1 + abs(v) * u2 = u3
ie, in MATLAB, following gcd.m's notations :
abs (a(k)) * u(1) + abs (b(k)) * u(2) = u(3)

The reason for this "abs " is that within gcd.m, abs (a(k)) and
abs (b(k)) are used in constructing the initial values of
the vectors u and v.

Also, I have not been able to observe any difference in time
between this modified method and the standard Matlab methods ;
it is "even" over several runs involving upto 20000 random numbers.

CMPLX_GCD.m -> CMPLX_GCD_Supr_2.m

and Ch_Rem_Thr_Poly.

Should generally work in R14, R13 and R12.

Similar modifications have also been done for CMPLX_GCD.m -> CMPLX_GCD_Supr_2.m

### Cite As

Sundar Krishnan (2023). Modified GCD (https://www.mathworks.com/matlabcentral/fileexchange/5948-modified-gcd), MATLAB Central File Exchange. Retrieved .

##### MATLAB Release Compatibility
Created with R14
Compatible with any release
##### Platform Compatibility
Windows macOS Linux
##### Categories
Find more on Operators and Elementary Operations in Help Center and MATLAB Answers