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:
Adding Parameters to HttpClient Requests
A Quick JUnit vs TestNG Comparison
A Guide to the finalize Method in Java
Guide to PriorityBlockingQueue in Java
Guide to Java 8’s Collectors
Guide To CompletableFuture
CharSequence vs. String in Java
Java Program to Find Median of Elements where Elements are Stored in 2 Different Arrays
Spring MVC Tutorial
Spring Security and OpenID Connect
Java Program to Implement Hopcroft Algorithm
Beans and Dependency Injection
Introduction to Spring Cloud CLI
Fixing 401s with CORS Preflights and Spring Security
Creating Docker Images with Spring Boot
Java Program to Implement Bucket Sort
Introduction to Spring Method Security
Hướng dẫn Java Design Pattern – DAO
Java Program to Implement RoleList API
Default Password Encoder in Spring Security 5
Class Loaders in Java
Convert String to int or Integer in Java
A Guide to ConcurrentMap
Java – File to Reader
Logging a Reactive Sequence
Hướng dẫn Java Design Pattern – Service Locator
How to Find an Element in a List with Java
Converting Between Byte Arrays and Hexadecimal Strings in Java
Immutable ArrayList in Java
Java Program to Generate Random Numbers Using Probability Distribution Function
Java Program to Check Whether a Directed Graph Contains a Eulerian Cycle
Java Program to Implement Counting Sort