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 source code of the Java Program to Implement Stein GCD Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
/** ** Java Program to Implement Stein GCD Algorithm **/ import java.util.Scanner; /** Class SteinGcd **/ public class SteinGcd { /** Function to calculate gcd **/ public int gcd(int u, int v) { int shift; if (u == 0) return v; if (v == 0) return u; 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) { int t = v; v = u; u = t; } v = v - u; } while (v != 0); return u << shift; } /** Main function **/ public static void main (String[] args) { Scanner scan = new Scanner(System.in); System.out.println("Stein GCD Algorithm Test\n"); /** Make an object of SteingGcd class **/ SteinGcd sg = new SteinGcd(); /** Accept two integers **/ System.out.println("Enter two integer numbers\n"); int n1 = scan.nextInt(); int n2 = scan.nextInt(); /** Call function gcd of class SteinGcd **/ int gcd = sg.gcd(n1, n2); System.out.println("GCD of "+ n1 +" and "+ n2 +" = "+ gcd); } }
Output:
Stein GCD Algorithm Test Enter two integer numbers 32984 10013 GCD of 32984 and 10013 = 589
Related posts:
Registration with Spring Security – Password Encoding
Java Program to Implement Johnson’s Algorithm
Guide to PriorityBlockingQueue in Java
Java Program to Implement Leftist Heap
Introduction to Using Thymeleaf in Spring
Java Program to Perform Right Rotation on a Binary Search Tree
Convert a Map to an Array, List or Set in Java
Auditing with JPA, Hibernate, and Spring Data JPA
The Dining Philosophers Problem in Java
Generate Spring Boot REST Client with Swagger
Java Program to Implement Maximum Length Chain of Pairs
Java Program to Find Nearest Neighbor for Dynamic Data Set
Java Program to Solve Set Cover Problem assuming at max 2 Elements in a Subset
Spring Webflux with Kotlin
Multi Dimensional ArrayList in Java
Java Program to Implement Floyd-Warshall Algorithm
Hướng dẫn Java Design Pattern – Chain of Responsibility
Java Program to Represent Graph Using Incidence List
Java Program to Implement Ternary Search Algorithm
Lập trình đa luồng với Callable và Future trong Java
Tips for dealing with HTTP-related problems
Spring Boot Annotations
Hướng dẫn Java Design Pattern – Iterator
Find the Registered Spring Security Filters
Sorting Query Results with Spring Data
How to Add a Single Element to a Stream
Java Program to Check if a Given Set of Three Points Lie on a Single Line or Not
Java Program to Perform the Unique Factorization of a Given Number
Java Program to Implement the Vigenere Cypher
Java Program to Create a Minimal Set of All Edges Whose Addition will Convert it to a Strongly Conne...
A Custom Media Type for a Spring REST API
Spring @RequestMapping New Shortcut Annotations