highest common factor Algorithm
The Highest Common Factor (HCF), also known as the Greatest Common Divisor (GCD), is an algorithm that determines the largest positive integer that evenly divides two or more numbers without leaving a remainder. This concept is widely used in various mathematical applications such as simplifying fractions, solving Diophantine equations, and finding the lowest common multiple (LCM) of numbers. The HCF algorithm finds its roots in the ancient Greek mathematical text, the Elements, written by Euclid around 300 BCE. Over time, it has been refined and adapted into various techniques, such as the Euclidean algorithm, the Binary GCD algorithm, and the Extended Euclidean algorithm, all of which are widely used in modern computational mathematics.
The most popular method for finding the HCF is the Euclidean algorithm, which is based on the principle of repeated subtraction. The algorithm begins by dividing the larger number by the smaller number and calculating the remainder. Then, the smaller number becomes the divisor, and the remainder becomes the dividend. This process is repeated until the remainder becomes zero. At this point, the last non-zero remainder is the HCF of the given numbers. The Binary GCD algorithm is a more efficient variation of the Euclidean algorithm, which uses bitwise operations for faster computation. In addition, the Extended Euclidean algorithm not only computes the HCF of two numbers but also provides their Bézout coefficients, which are useful in solving Diophantine equations and modular inverses.
ffunction HCF = mini (x, y)
%This function searches for highest common factor
%It first checks if any of the numbers equal to zero, if so the non zero number is the HCF
%If the numbers are different, you minus the bigger number by the smaller one and this is done by recursion.
if x==0
HCF = y;
elseif y==0
HCF == x;
elseif (y == x)
HCF = x;
elseif (y>x)
HCF = mini(y-x,x);
else
HCF = mini(x-y,y);
end
