Java Program to Implement Karatsuba Multiplication Algorithm

«
»
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.

  1. /**
  2.  *    Java Program to Implement Karatsuba Multiplication Algorithm
  3.  **/
  4.  
  5. import java.util.Scanner;
  6.  
  7. /** Class Karatsuba **/
  8. public class Karatsuba
  9. {
  10.     /** Function to multiply two numbers **/
  11.     public long multiply(long x, long y)
  12.     {
  13.         int size1 = getSize(x);
  14.         int size2 = getSize(y);
  15.         /** Maximum of lengths of number **/
  16.         int N = Math.max(size1, size2);
  17.         /** for small values directly multiply **/        
  18.         if (N < 10)
  19.             return x * y;
  20.         /** max length divided, rounded up **/    
  21.         N = (N / 2) + (N % 2);    
  22.         /** multiplier **/
  23.         long m = (long)Math.pow(10, N);
  24.  
  25.         /** compute sub expressions **/        
  26.         long b = x / m;
  27.         long a = x - (b * m);
  28.         long d = y / m;
  29.         long c = y - (d * N);
  30.         /** compute sub expressions **/
  31.         long z0 = multiply(a, c);
  32.         long z1 = multiply(a + b, c + d);
  33.         long z2 = multiply(b, d);          
  34.  
  35.         return z0 + ((z1 - z0 - z2) * m) + (z2 * (long)(Math.pow(10, 2 * N)));        
  36.     }
  37.     /** Function to calculate length or number of digits in a number **/
  38.     public int getSize(long num)
  39.     {
  40.         int ctr = 0;
  41.         while (num != 0)
  42.         {
  43.             ctr++;
  44.             num /= 10;
  45.         }
  46.         return ctr;
  47.     }
  48.     /** Main function **/
  49.     public static void main (String[] args) 
  50.     {
  51.         Scanner scan = new Scanner(System.in);
  52.         System.out.println("Karatsuba Multiplication Algorithm Test\n");
  53.         /** Make an object of Karatsuba class **/
  54.         Karatsuba kts = new Karatsuba();
  55.  
  56.         /** Accept two integers **/
  57.         System.out.println("Enter two integer numbers\n");
  58.         long n1 = scan.nextLong();
  59.         long n2 = scan.nextLong();
  60.         /** Call function multiply of class Karatsuba **/
  61.         long product = kts.multiply(n1, n2);
  62.         System.out.println("\nProduct : "+ product);
  63.     }
  64. }

advertisement
Karatsuba Multiplication Algorithm Test
 
Enter two integer numbers
 
24061994 28563
 
Product : 687282734622

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter