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:
Truyền giá trị và tham chiếu trong java
Handling URL Encoded Form Data in Spring REST
Getting Started with Custom Deserialization in Jackson
Java Program to Check the Connectivity of Graph Using DFS
Java Program to Implement Meldable Heap
Arrays.asList vs new ArrayList(Arrays.asList())
Apache Commons Collections SetUtils
Guide to Mustache with Spring Boot
Java Program to Implement Sieve Of Atkin
Guide to Character Encoding
Hướng dẫn sử dụng Java Generics
Java Program to Check for balanced parenthesis by using Stacks
Java Program to Find Whether a Path Exists Between 2 Given Nodes
Hướng dẫn Java Design Pattern – Strategy
Spring Boot Security Auto-Configuration
Quick Intro to Spring Cloud Configuration
Cachable Static Assets with Spring MVC
Java Switch Statement
Derived Query Methods in Spring Data JPA Repositories
Chuyển đổi Array sang ArrayList và ngược lại
Base64 encoding và decoding trong Java 8
Java Program to Implement Bit Array
Using JWT with Spring Security OAuth (legacy stack)
Using the Not Operator in If Conditions in Java
Working with Kotlin and JPA
Java Program to Check whether Graph is a Bipartite using BFS
Java Program to Implement Binomial Heap
Introduction to Spring Data JPA
Java Program to Implement Cubic convergence 1/pi Algorithm
LinkedList trong java
Java 8 StringJoiner
HttpClient Basic Authentication