Modified GCD

Modification in MATLAB's gcd.m by suppressing calculation of u2, v2 and t2 at intermediate steps
Updated 14 Jul 2005

No License

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.

See also my code(s) for finding GCD of Complex Nos :

See also my code(s) Poly_GCD, Poly_POWER
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 (2024). Modified GCD (, MATLAB Central File Exchange. Retrieved .

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

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Version Published Release Notes

Readme file added.