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:
Java Program to Implement Rolling Hash
Java Program to Implement Min Hash
Java Program to Implement Patricia Trie
Spring RestTemplate Request/Response Logging
Spring Boot - Quick Start
Java Program to Implement Ternary Heap
Spring Cloud Series – The Gateway Pattern
Spring Boot - Building RESTful Web Services
Java Program to Use rand and srand Functions
Giới thiệu Design Patterns
Guide to Spring @Autowired
Runnable vs. Callable in Java
Giới thiệu Json Web Token (JWT)
Implementing a Binary Tree in Java
Java Program to Implement Segment Tree
How to Round a Number to N Decimal Places in Java
Kết hợp Java Reflection và Java Annotations
Java Program to Implement Quick sort
Tạo số và chuỗi ngẫu nhiên trong Java
Testing in Spring Boot
Logout in an OAuth Secured Application
Java Program to Implement Strassen Algorithm
Hướng dẫn Java Design Pattern – Composite
File Upload with Spring MVC
Biến trong java
Tiêu chuẩn coding trong Java (Coding Standards)
Java Program to Implement the Monoalphabetic Cypher
Using a Spring Cloud App Starter
An Intro to Spring Cloud Security
Marker Interface trong Java
Spring Boot - Batch Service
Different Ways to Capture Java Heap Dumps