0 votes
430 views
in Computer Architecture by
Section 15.4 includes a C program that calculates the greatest common divisor of two integers. Describe the algorithm in words and show how the program does implement the Euclid algorithm approach to calculating the greatest common divisor.

1 Answer

0 votes
by
Euclid’s Algorithm to find GCD of two numbers:-

*Euclid’s algorithm (or Euclidean algorithm) is a method for efficiently finding the greatest common divisor (GCD) of two numbers. The GCD of two integers, X and Y, is the largest number that divides both X and Y without leaving a remainder.

For example,

Euclid(30, 50) = 10

 

Euclid(2740, 1760) = 20

The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number.

For example, 21 is the GCD of 252 and 105 (252 = 21 × 12 and 105 = 21 × 5), and the same number 21 is also the GCD of 105 and 147 (147 = 252 - 105).

 

Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, they are the GCD of the original two numbers.

The following C program demonstrates it:

#include <stdio.h>

 

// Iterative function to calculate gcd of two numbers

// using Euclid’s algorithm (basic version)

int euclid(int a, int b)

{

    // do until the two numbers become equal

    while (a != b)

    {

        // replace the larger number by its difference with the smaller number

        if (a > b) {

            a = a - b;

        }

        else {

            b = b - a;

        }

    }

 

    return a; // or `b` (since both are equal)

}

 

int main()

{

    int a = 30;

    int b = 50;

 

    printf("Euclid(%d, %d) = %d", a, b, euclid(a, b));

 

    return 0;

}

Output:

Euclid(30, 50) = 10

The only problem with the above version is that it can take several subtraction steps to find the GCD if one of the given numbers is much bigger than the other.

 

A more efficient version of the algorithm replaces the larger of the two numbers by its remainder when divided by the smaller one. The algorithm stops when reaching a zero remainder, and now the algorithm never requires more steps than five times the number of digits (base 10) of the smaller integer.

Related questions

+1 vote
1 answer 342 views
Welcome to CPENTalk.com
Solution-oriented students of computer engineering on one platform to get you that

ONE SOLUTION

...