This is a Java Program to Implement Karatsuba Multiplication Algorithm. The Karatsuba algorithm is a fast multiplication algorithm. It was discovered by Anatolii Alexeevitch Karatsuba in 1960 and published in 1962. The Karatsuba algorithm was the first multiplication algorithm asymptotically faster than the quadratic “grade school” algorithm. It reduces the multiplication of two n-digit numbers to at most 3 n log 2 3 approx 3 n 1.585 single-digit multiplications in general.
Here is the source code of the Java Program to Implement Karatsuba Multiplication Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
/** * Java Program to Implement Karatsuba Multiplication Algorithm **/ import java.util.Scanner; /** Class Karatsuba **/ public class Karatsuba { /** Function to multiply two numbers **/ public long multiply(long x, long y) { int size1 = getSize(x); int size2 = getSize(y); /** Maximum of lengths of number **/ int N = Math.max(size1, size2); /** for small values directly multiply **/ if (N < 10) return x * y; /** max length divided, rounded up **/ N = (N / 2) + (N % 2); /** multiplier **/ long m = (long)Math.pow(10, N); /** compute sub expressions **/ long b = x / m; long a = x - (b * m); long d = y / m; long c = y - (d * N); /** compute sub expressions **/ long z0 = multiply(a, c); long z1 = multiply(a + b, c + d); long z2 = multiply(b, d); return z0 + ((z1 - z0 - z2) * m) + (z2 * (long)(Math.pow(10, 2 * N))); } /** Function to calculate length or number of digits in a number **/ public int getSize(long num) { int ctr = 0; while (num != 0) { ctr++; num /= 10; } return ctr; } /** Main function **/ public static void main (String[] args) { Scanner scan = new Scanner(System.in); System.out.println("Karatsuba Multiplication Algorithm Test\n"); /** Make an object of Karatsuba class **/ Karatsuba kts = new Karatsuba(); /** Accept two integers **/ System.out.println("Enter two integer numbers\n"); long n1 = scan.nextLong(); long n2 = scan.nextLong(); /** Call function multiply of class Karatsuba **/ long product = kts.multiply(n1, n2); System.out.println("\nProduct : "+ product); } }
Output:
Karatsuba Multiplication Algorithm Test Enter two integer numbers 24061994 28563 Product : 687282734622
Related posts:
Partition a List in Java
Hướng dẫn Java Design Pattern – Object Pool
Hashing a Password in Java
Chuyển đổi từ HashMap sang ArrayList
Java Program to Represent Graph Using Adjacency Matrix
Spring WebFlux Filters
Java Program to Implement Bellman-Ford Algorithm
Java Program to Implement LinkedBlockingQueue API
HttpClient Basic Authentication
Java Program to Find Transpose of a Graph Matrix
A Guide to the ResourceBundle
Java Program to Implement CopyOnWriteArraySet API
Reversing a Linked List in Java
Chuyển đổi giữa các kiểu dữ liệu trong Java
Từ khóa static và final trong java
Spring Webflux and CORS
Java Optional as Return Type
Running Spring Boot Applications With Minikube
Format ZonedDateTime to String
Java Program to Print only Odd Numbered Levels of a Tree
Posting with HttpClient
Rest Web service: Filter và Interceptor với Jersey 2.x (P1)
Examine the internal DNS cache
Convert String to Byte Array and Reverse in Java
Netflix Archaius with Various Database Configurations
String Processing with Apache Commons Lang 3
Java Program to Find Nearest Neighbor for Static Data Set
Java Program to Implement Hash Tables Chaining with Binary Trees
Java Program to Implement K Way Merge Algorithm
A Quick Guide to Spring Cloud Consul
Java Program to Perform Arithmetic Operations on Numbers of Size
Hướng dẫn Java Design Pattern – Flyweight