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:
Custom Thread Pools In Java 8 Parallel Streams
Hướng dẫn Java Design Pattern – MVC
Java Program to Implement the Binary Counting Method to Generate Subsets of a Set
Giới thiệu JDBC Connection Pool
Java Program to Find Nearest Neighbor Using Linear Search
Java 14 Record Keyword
Java Program to Implement Knapsack Algorithm
Converting String to Stream of chars
Java Stream Filter with Lambda Expression
Tính đa hình (Polymorphism) trong Java
Spring’s RequestBody and ResponseBody Annotations
Spring @RequestMapping New Shortcut Annotations
Java Program to Implement Hopcroft Algorithm
Java Program to Implement Hash Tables Chaining with Doubly Linked Lists
Java Program to Implement Traveling Salesman Problem using Nearest neighbour Algorithm
Count Occurrences of a Char in a String
Java Program to Find MST (Minimum Spanning Tree) using Kruskal’s Algorithm
Spring Security – Reset Your Password
Reactive Flow with MongoDB, Kotlin, and Spring WebFlux
Spring WebClient vs. RestTemplate
Java Program to Implement Unrolled Linked List
Comparing Arrays in Java
Generating Random Numbers in a Range in Java
Intro to Spring Boot Starters
JUnit 5 for Kotlin Developers
OAuth2 for a Spring REST API – Handle the Refresh Token in Angular
Hướng dẫn sử dụng lớp Console trong java
Java Program to Implement Hash Tables with Linear Probing
Java Program to Implement Hash Trie
Encode a String to UTF-8 in Java
Extract links from an HTML page
Java Program to Implement Nth Root Algorithm