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:
Java Program to Generate Randomized Sequence of Given Range of Numbers
Hướng dẫn Java Design Pattern – Prototype
Functional Interfaces in Java 8
Java Program to Check whether Graph is a Bipartite using BFS
Spring – Injecting Collections
Guide to CountDownLatch in Java
HttpClient Basic Authentication
Spring @Primary Annotation
Java Program to Implement Max Heap
Convert XML to JSON Using Jackson
Java Program to find the maximum subarray sum O(n^2) time(naive method)
Apache Commons Collections BidiMap
Java Program to Perform Postorder Recursive Traversal of a Given Binary Tree
JUnit 5 @Test Annotation
Giới thiệu thư viện Apache Commons Chain
Java Program to Implement VList
Java Program to Implement ConcurrentSkipListMap API
Java Program for Douglas-Peucker Algorithm Implementation
Java Scanner hasNext() vs. hasNextLine()
Optional trong Java 8
Java Program to Implement Ternary Search Algorithm
DistinctBy in the Java Stream API
Java Program to Implement Coppersmith Freivald’s Algorithm
Java 8 Predicate Chain
Intro to the Jackson ObjectMapper
How to Read a Large File Efficiently with Java
Introduction to Spring Data JPA
Changing Annotation Parameters At Runtime
Check If a File or Directory Exists in Java
Spring Cloud AWS – EC2
Java Program to Perform Arithmetic Operations on Numbers of Size
Hướng dẫn sử dụng lớp Console trong java