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:
Introduction to Spring Data JDBC
Java Program to Implement Hash Tables
Getting Started with GraphQL and Spring Boot
Java Program to Implement Binomial Heap
Giới thiệu JDBC Connection Pool
Spring AMQP in Reactive Applications
Creating Docker Images with Spring Boot
Java Program to Find Minimum Element in an Array using Linear Search
Truyền giá trị và tham chiếu trong java
Implementing a Binary Tree in Java
Merging Streams in Java
Mệnh đề Switch-case trong java
Encode a String to UTF-8 in Java
Registration with Spring Security – Password Encoding
The Dining Philosophers Problem in Java
A Guide to Spring Cloud Netflix – Hystrix
Tránh lỗi NullPointerException trong Java như thế nào?
Autoboxing và Unboxing trong Java
A Guide to JUnit 5 Extensions
Base64 encoding và decoding trong Java 8
Từ khóa this và super trong Java
Java Program to Perform Naive String Matching
Java Program to Implement Maximum Length Chain of Pairs
Java Program to Implement the String Search Algorithm for Short Text Sizes
Finding Max/Min of a List or Collection
Java List UnsupportedOperationException
Period and Duration in Java
Java Program to Evaluate an Expression using Stacks
Java 8 Stream API Analogies in Kotlin
Java Program to Implement Rope
Java Program to Perform Insertion in a BST
Java Program to Implement Tarjan Algorithm