Category Archives: Known Algorithms Implementation

Multiplication in less time and space : using Karatsuba

This program demonstrates the multiplication of two numbers in less time and space : using Karatsuba in Java.
The Operation implemented :
1. Multiplication

Idea :

Karatsuba Multiplication

Karatsuba Multiplication

Implementation :


import java.util.Scanner;

/*
* This class demonstrates multiplication in less no. of CPU cycles.
* @author : Madan Gopal Singh
* @version : 1.0
* @date : 6th December, 2014
*/
class KaratsubaMultiplier{

/**
* The karatsubaMultiply method
* @param long n1
* @param long n2
* @return long.
*/
private long karatsubaMultiply(long n1, long n2){
int len1 = length(n1);
int len2 = length(n2);

int N = maximum(len1, len2);

if (N < 2)
return n1 * n2;

N = (N / 2) + (N % 2);

long m = (long)Math.pow(10, N);

long b = n1 / m;
long a = n1 - (b * m);
long d = n2 / m;
long c = n2 - (d * m);
long z1 = karatsubaMultiply(a, c);
long z2 = karatsubaMultiply(a + b, c + d);
long z3 = karatsubaMultiply(b, d);

return z1 + ((z2 - z1 - z3) * m) + (z3 * (long)(Math.pow(10, 2 * N)));
}

/**
* The maximum method
* @param int len1
* @param int len2
* @return int.
*/
private int maximum(int len1, int len2){
return Math.max(len1, len2);
}

/**
* The length method
* @param long number
* @return int.
*/
private int length(long number){
int count = 0;
while (number != 0){
count++;
number = number / 10;
}
return count;
}

/**
* The multiply method
* @param long x
* @param long y
* @return long.
*/
public long multiply(long x,long y) throws InvalidMethodArgumentException{
if(x<0 || y<0)
throw new InvalidMethodArgumentException("Invalid Argument");
return karatsubaMultiply(x, y);
}
}

class InvalidMethodArgumentException extends Exception{
private static final long serialVersionUID = 1L;

public InvalidMethodArgumentException(String message) {
super(message);
}
}

public class KaratsubaMultiplicationApp {

/**
* The main method
* @param void
* @return Sting[].
*/
public static void main (String[] args)
{
Scanner sc = new Scanner(System.in);
System.out.println("Enter integer number one");
long num1 = sc.nextLong();
System.out.println("Enter integer number two");
long num2 = sc.nextLong();
try {
System.out.println("\nMuliplication is : "+ new KaratsubaMultiplier().multiply(num1, num2));
} catch (InvalidMethodArgumentException e) {
System.out.println(e.getMessage());
}
sc.close();
}

}

I appreciate all your feed backs.