This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.
/*
This is a Java Program to Implement Stein GCD Algorithm. The binary GCD algorithm, also known as Stein’s algorithm, is an algorithm that computes the greatest common divisor of two nonnegative integers. Stein’s algorithm uses simpler arithmetic operations than the conventional Euclidean algorithm. It replaces division with arithmetic shifts, comparisons and subtraction.
Here is the sourc
*/
/**
** Java Program to Implement Stein GCD Algorithm
**/
importjava.util.Scanner;
/** Class SteinGcd **/
publicclassSteinGcd
{
/** Function to calculate gcd **/
publicintgcd(intu,intv)
{
intshift;
if(u==0)
returnv;
if(v==0)
returnu;
for(shift=0;((u|v)&1)==0;++shift)
{
u>>=1;
v>>=1;
}
while((u&1)==0)
u>>=1;
do
{
while((v&1)==0)
v>>=1;
if(u>v)
{
intt=v;
v=u;
u=t;
}
v=v-u;
}
while(v!=0);
returnu<<shift;
}
/** Main function **/
publicstaticvoidmain(String[]args)
{
Scannerscan=newScanner(System.in);
System.out.println("Stein GCD Algorithm Test\n");
/** Make an object of SteingGcd class **/
SteinGcdsg=newSteinGcd();
/** Accept two integers **/
System.out.println("Enter two integer numbers\n");
intn1=scan.nextInt();
intn2=scan.nextInt();
/** Call function gcd of class SteinGcd **/
intgcd=sg.gcd(n1,n2);
System.out.println("GCD of "+n1+" and "+n2+" = "+gcd);