Calculating Greatest Common Divisor using While loop

Instead of using built in 'GCD' function, I am to devise code to calculate the GCD of two numbers using a while loop. I cannot figure out how to code it. Requesting some help!

%% Input two numbers.
% There is no error checking so put in positive integers of bad things may
% happen - MC
x = input('Enter an integer > 0: ');
y = input('Enter another integer > 0: ');
if x >= y
    numerator = x;
    denominator = y;
else
    numerator = y;
    denominator = x;
end
%% Calculates the GCD
% ------------ Replace this piece of the code with a while loop -----------
r = rem(numerator, denominator);
while r > 0
    if r == 0
        GCD = denominator;
        break;
    end
end
fprintf('The GCD of %d and %d is %d: it took calculations\n',x,y,GCD)

[Voss]

Here are some references that may help:

https://sites.math.rutgers.edu/~greenfie/gs2004/euclid.html

https://en.wikipedia.org/wiki/Euclidean_algorithm#Description

Answer 1

[Lokesh]

Hi Dylan,

I understand that you are working on implementing the GCD of two numbers using a while loop, aiming to apply the Euclidean algorithm.

To ensure the algorithm functions as intended, it is crucial to update the values being used to calculate the remainder within each iteration of the loop.This process involves treating the current denominator as the new numerator and the current remainder as the new denominator, then recalculating the remainder for the next iteration. This cycle continues until the remainder is zero, at which point the last non-zero denominator is the GCD.

Here is how you can modify your loop to correctly implement the algorithm:

%% Calculates the GCD
r = rem(numerator, denominator); % Initial remainder
while r > 0
    numerator = denominator; % The previous denominator becomes the new numerator
    denominator = r; % The remainder becomes the new denominator
    r = rem(numerator, denominator); % Calculate the new remainder
end

GCD = denominator; % The last non-zero remainder
fprintf('The GCD of %d and %d is %d.\n', x, y, GCD);

Hope this helps!