Skip to main content

karatsuba algorithm for fast multiplication

Karatsuba algorithm is a fast multiplication algorithm that was developed by Anatolii Alexeevitch Karatsuba in 1960. The algorithm uses a divide-and-conquer approach to recursively break down a multiplication problem into smaller subproblems and then combines the solutions to these subproblems to obtain the final product.

Here given code implementation process.

/*
    Java Program for
    karatsuba algorithm for fast multiplication
*/
public class Multiplication
{
	public String prefixZero(int n)
	{
		String zero = "";
		for (int i = 0; i < n; i++)
		{
			zero += "0";
		}
		return zero;
	}
	String addBitStrings(String a, String b)
	{
		String result = "";
		int carry = 0;
		String first = a;
		String second = b;
		if (first.length() < second.length())
		{
			first = prefixZero(second.length() - first.length()) + first;
		}
		if (second.length() < first.length())
		{
			second = prefixZero(first.length() - second.length()) + second;
		}
		int length = first.length();
		for (int i = length - 1; i >= 0; --i)
		{
			int firstBit = first.charAt(i) - '0';
			int secondBit = second.charAt(i) - '0';
			int sum = (firstBit ^ secondBit ^ carry) + '0';
			result = (char) sum + result;
			carry = (firstBit & secondBit) | 
                    (secondBit & carry) | 
                    (firstBit & carry);
		}
		if (carry != 0)
		{
			result = '1' + result;
		}
		return result;
	}
	public long multiply(String a, String b)
	{
		// Collecting given string binary value
		String v1 = a;
		String v2 = b;
		// Converting the both strings in equal 
		// length by adding some  prefix zero.
		if (v1.length() > v2.length())
		{
			v2 = prefixZero(v1.length() - v2.length()) + v2;
		}
		if (v2.length() > v1.length())
		{
			v1 = prefixZero(v2.length() - v1.length()) + v1;
		}
		// Get the size of equal string
		int size = v1.length();
		if (size == 0)
		{
			// When string is empty
			return 0;
		}
		else if (size == 1)
		{
			// When single character exists in both string
			return (v1.charAt(0) - '0') * (v2.charAt(0) - '0');
		}
		// Get length of first half
		//
		//   Example
		//              
		//   ₓ = 13
		//   ₓ
		//   ─ = 6
		//  2 
		//
		//   Index start with zero, So here 6 index at 7th position
		//   ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ 
		//   |<─────────>|
		//    firstHalf
		//
		int firstHalf = size / 2;
		// Example of second half
		//
		//   Example
		//               
		//   ₓ = 13
		//   ₓ
		//   ─ = 6 <- first half
		//   2 
		//   
		//   13 - 6 = 7
		//  Index start with zero, So here 7 index at 8th position
		//   ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ 
		//   |<───────────>|
		//     Second half
		//
		int secondHalf = (size - firstHalf);
		// Get prefix of v1 of size first half
		String leftA = v1.substring(0, firstHalf);
		// Get remaining character v1
		String rightA = v1.substring(firstHalf);
		// Get prefix of v2 of size first half
		String leftB = v2.substring(0, firstHalf);
		// Get remaining character of v2
		String rightB = v2.substring(firstHalf);
		// Get three products
		long p1 = multiply(leftA, leftB);
		long p2 = multiply(rightA, rightB);
		long p3 = multiply(
          addBitStrings(leftA, rightA), 
          addBitStrings(leftB, rightB)
        );
		return p1 * (1 << (2 * secondHalf)) + 
          (p3 - p1 - p2) * (1 << secondHalf) + p2;
	}
	public void multiplyBinary(String a, String b)
	{
		// Display given binary value
		// Assume that given a and b contain 0 and 1s
		System.out.println(" Given Binary A : " + a);
		System.out.println(" Given Binary B : " + b);
		// Display multiply value
		System.out.println(" Result : " + multiply(a, b));
	}
	public static void main(String[] args)
	{
		Multiplication task = new Multiplication();
		// Test A
		//   a = 1011 => 11
		//   b = 101  => 5
		//   11 * 5 => 55 
		//   55 = [110111] 
		// Result = 55
		task.multiplyBinary("1011", "101");
		// Test B
		//   a = 1111 => 15
		//   b = 1010  => 10
		//   15 * 10 => 150 
		//   150 = [10010110] 
		//  Result = 150
		task.multiplyBinary("1111", "1010");
	}
}

Output

 Given Binary A : 1011
 Given Binary B : 101
 Result : 55
 Given Binary A : 1111
 Given Binary B : 1010
 Result : 150
// Include header file
#include <iostream>
#include <string>

using namespace std;
/*
    C++ Program for
    karatsuba algorithm for fast multiplication
*/
class Multiplication
{
    public: string prefixZero(int n)
    {
        string zero = "";
        for (int i = 0; i < n; i++)
        {
            zero += "0";
        }
        return zero;
    }
    string addBitStrings(string a, string b)
    {
        string result = "";
        int carry = 0;
        string first = a;
        string second = b;
        if (first.length() < second.length())
        {
            first = this->prefixZero(second.length() - 
                                     first.length())  +  first;
        }
        if (second.length() < first.length())
        {
            second = this->prefixZero(first.length() - 
                                      second.length())  +  second;
        }
        int length = first.length();
        for (int i = length - 1; i >= 0; --i)
        {
            int firstBit = first[i] - '0';
            int secondBit = second[i] - '0';
            int sum = (firstBit ^ secondBit ^ carry) + '0';
            result = ((char)sum)  +  result;
            carry = (firstBit &secondBit) | 
                    (secondBit &carry) | 
                    (firstBit &carry);
        }
        if (carry != 0)
        {
            result = "1"  +  result;
        }
        return result;
    }
    long multiply(string a, string b)
    {
        // Collecting given string binary value
        string v1 = a;
        string v2 = b;
        // Converting the both strings in equal 
        // length by adding some  prefix zero.
        if (v1.length() > v2.length())
        {
            v2 = this->prefixZero(v1.length() - v2.length())  +  v2;
        }
        if (v2.length() > v1.length())
        {
            v1 = this->prefixZero(v2.length() - v1.length())  +  v1;
        }
        // Get the size of equal string
        int size = v1.length();
        if (size == 0)
        {
            // When string is empty
            return 0;
        }
        else if (size == 1)
        {
            // When single character exists in both string
            return (v1[0] - '0') *(v2[0] - '0');
        }
        // Get length of first half
        //
        //   Example
        //              
        //   ₓ = 13
        //   ₓ
        //   ─ = 6
        //  2 
        //
        //   Index start with zero, So here 6 index at 7th position
        //   ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ 
        //   |<─────────>|
        //    firstHalf
        //
        int firstHalf = size / 2;
        // Example of second half
        //
        //   Example
        //               
        //   ₓ = 13
        //   ₓ
        //   ─ = 6 <- first half
        //   2 
        //   
        //   13 - 6 = 7
        //  Index start with zero, So here 7 index at 8th position
        //   ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ 
        //   |<───────────>|
        //     Second half
        //
        int secondHalf = (size - firstHalf);
        // Get prefix of v1 of size first half
        string leftA = v1.substr(0, firstHalf);
        // Get remaining character v1
        string rightA = v1.substr(firstHalf);
        // Get prefix of v2 of size first half
        string leftB = v2.substr(0, firstHalf);
        // Get remaining character of v2
        string rightB = v2.substr(firstHalf);
        // Get three products
        long p1 = this->multiply(leftA, leftB);
        long p2 = this->multiply(rightA, rightB);
        long p3 = this->multiply(
            this->addBitStrings(leftA, rightA), 
            this->addBitStrings(leftB, rightB)
        );
        return p1 *(1 << (2 *secondHalf)) + 
          (p3 - p1 - p2) *(1 << secondHalf) + p2;
    }
    void multiplyBinary(string a, string b)
    {
        // Display given binary value
        // Assume that given a and b contain 0 and 1s
        cout << " Given Binary A : " << a << endl;
        cout << " Given Binary B : " << b << endl;
        // Display multiply value
        cout << " Result : " << this->multiply(a, b) << endl;
    }
};
int main()
{
    Multiplication *task = new Multiplication();
    // Test A
    //   a = 1011 => 11
    //   b = 101  => 5
    //   11 *5 => 55 
    //   55 = [110111] 
    // Result = 55
    task->multiplyBinary("1011", "101");
    // Test B
    //   a = 1111 => 15
    //   b = 1010  => 10
    //   15 *10 => 150 
    //   150 = [10010110] 
    //  Result = 150
    task->multiplyBinary("1111", "1010");
    return 0;
}

Output

 Given Binary A : 1011
 Given Binary B : 101
 Result : 55
 Given Binary A : 1111
 Given Binary B : 1010
 Result : 150
// Include namespace system
using System;
/*
    Csharp Program for
    karatsuba algorithm for fast multiplication
*/
public class Multiplication
{
	public String prefixZero(int n)
	{
		String zero = "";
		for (int i = 0; i < n; i++)
		{
			zero += "0";
		}
		return zero;
	}
	String addBitStrings(String a, String b)
	{
		String result = "";
		int carry = 0;
		String first = a;
		String second = b;
		if (first.Length < second.Length)
		{
			first = this.prefixZero(
              second.Length - first.Length
            ) + first;
		}
		if (second.Length < first.Length)
		{
			second = this.prefixZero(
              first.Length - second.Length
            ) + second;
		}
		int length = first.Length;
		for (int i = length - 1; i >= 0; --i)
		{
			int firstBit = first[i] - '0';
			int secondBit = second[i] - '0';
			int sum = (firstBit ^ secondBit ^ carry) + '0';
			result = (char) sum + result;
			carry = (firstBit & secondBit) | 
              (secondBit & carry) | 
              (firstBit & carry);
		}
		if (carry != 0)
		{
			result = '1' + result;
		}
		return result;
	}
	public long multiply(String a, String b)
	{
		// Collecting given string binary value
		String v1 = a;
		String v2 = b;
		// Converting the both strings in equal 
		// length by adding some  prefix zero.
		if (v1.Length > v2.Length)
		{
			v2 = this.prefixZero(v1.Length - v2.Length) + v2;
		}
		if (v2.Length > v1.Length)
		{
			v1 = this.prefixZero(v2.Length - v1.Length) + v1;
		}
		// Get the size of equal string
		int size = v1.Length;
		if (size == 0)
		{
			// When string is empty
			return 0;
		}
		else if (size == 1)
		{
			// When single character exists in both string
			return (v1[0] - '0') * (v2[0] - '0');
		}
		// Get length of first half
		//
		//   Example
		//              
		//   ₓ = 13
		//   ₓ
		//   ─ = 6
		//  2 
		//
		//   Index start with zero, So here 6 index at 7th position
		//   ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ 
		//   |<─────────>|
		//    firstHalf
		//
		int firstHalf = size / 2;
		// Example of second half
		//
		//   Example
		//               
		//   ₓ = 13
		//   ₓ
		//   ─ = 6 <- first half
		//   2 
		//   
		//   13 - 6 = 7
		//  Index start with zero, So here 7 index at 8th position
		//   ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ 
		//   |<───────────>|
		//     Second half
		//
		int secondHalf = (size - firstHalf);
		// Get prefix of v1 of size first half
		String leftA = v1.Substring(0, firstHalf);
		// Get remaining character v1
		String rightA = v1.Substring(firstHalf);
		// Get prefix of v2 of size first half
		String leftB = v2.Substring(0, firstHalf);
		// Get remaining character of v2
		String rightB = v2.Substring(firstHalf);
		// Get three products
		long p1 = this.multiply(leftA, leftB);
		long p2 = this.multiply(rightA, rightB);
		long p3 = this.multiply(
          this.addBitStrings(leftA, rightA), 
          this.addBitStrings(leftB, rightB));
		return p1 * (1 << (2 * secondHalf)) + 
          (p3 - p1 - p2) * (1 << secondHalf) + p2;
	}
	public void multiplyBinary(String a, String b)
	{
		// Display given binary value
		// Assume that given a and b contain 0 and 1s
		Console.WriteLine(" Given Binary A : " + a);
		Console.WriteLine(" Given Binary B : " + b);
		// Display multiply value
		Console.WriteLine(" Result : " + this.multiply(a, b));
	}
	public static void Main(String[] args)
	{
		Multiplication task = new Multiplication();
		// Test A
		//   a = 1011 => 11
		//   b = 101  => 5
		//   11 * 5 => 55 
		//   55 = [110111] 
		// Result = 55
		task.multiplyBinary("1011", "101");
		// Test B
		//   a = 1111 => 15
		//   b = 1010  => 10
		//   15 * 10 => 150 
		//   150 = [10010110] 
		//  Result = 150
		task.multiplyBinary("1111", "1010");
	}
}

Output

 Given Binary A : 1011
 Given Binary B : 101
 Result : 55
 Given Binary A : 1111
 Given Binary B : 1010
 Result : 150
package main

import "fmt"
/*
    Go Program for
    karatsuba algorithm for fast multiplication
*/
type Multiplication struct {}
func getMultiplication() * Multiplication {
	var me *Multiplication = &Multiplication {}
	return me
}
func(this Multiplication) prefixZero(n int) string {
	var zero string = ""
	for i := 0 ; i < n ; i++ {
		zero += "0"
	}
	return zero
}
func(this Multiplication) addBitStrings(a, b string) string {
	var result string = ""
	var carry int = 0
	var first string = a
	var second string = b
	if len(first) < len(second) {
		first = this.prefixZero(len(second) - len(first)) + first
	}
	if len(second) < len(first) {
		second = this.prefixZero(len(first) - len(second)) + second
	}
	var length int = len(first)
	for i := length - 1 ; i >= 0 ; i-- {
		var firstBit int = int(first[i]) - 48
		var secondBit int = int(second[i]) - 48
		var sum int = (firstBit ^ secondBit ^ carry) + 48
		result = string(byte(sum)) + result
		carry = (firstBit & secondBit) | (secondBit & carry) | (firstBit & carry)
	}
	if carry != 0 {
		result = "1" + result
	}
	return result
}
func(this Multiplication) multiply(a, b string) int64 {
	// Collecting given string binary value
	var v1 string = a
	var v2 string = b
	// Converting the both strings in equal 
	// length by adding some  prefix zero.
	if len(v1) > len(v2) {
		v2 = this.prefixZero(len(v1) - len(v2)) + v2
	}
	if len(v2) > len(v1) {
		v1 = this.prefixZero(len(v2) - len(v1)) + v1
	}
	// Get the size of equal string
	var size int = len(v1)
	if size == 0 {
		// When string is empty
		return 0
	} else if size == 1 {
		// When single character exists in both string
		return   (int64(v1[0]) - 48) * (int64(v2[0]) - 48)
	}
	// Get length of first half
	//
	//   Example
	//              
	//   ₓ = 13
	//   ₓ
	//   ─ = 6
	//  2 
	//
	//   Index start with zero, So here 6 index at 7th position
	//   ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ 
	//   |<─────────>|
	//    firstHalf
	//
	var firstHalf int = size / 2
	// Example of second half
	//
	//   Example
	//               
	//   ₓ = 13
	//   ₓ
	//   ─ = 6 <- first half
	//   2 
	//   
	//   13 - 6 = 7
	//  Index start with zero, So here 7 index at 8th position
	//   ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ 
	//   |<───────────>|
	//     Second half
	//
	var secondHalf int = (size - firstHalf)
	// Get prefix of v1 of size first half
	var leftA string = v1[0 : firstHalf]
	// Get remaining character v1
	var rightA string = v1[firstHalf : len(v1)]

	// Get prefix of v2 of size first half
	var leftB string = v2[0 : firstHalf]
	// Get remaining character of v2
	var rightB string = v2[firstHalf:len(v2)]
	// Get three products
	var p1 int64 = this.multiply(leftA, leftB)
	var p2 int64 = this.multiply(rightA, rightB)
	var p3 int64 = this.multiply(this.addBitStrings(leftA, rightA), 
		this.addBitStrings(leftB, rightB))
	return p1 * (1 << (2 * secondHalf)) + (p3 - p1 - p2) * (1 << secondHalf) + p2
}
func(this Multiplication) multiplyBinary(a, b string) {
	// Display given binary value
	// Assume that given a and b contain 0 and 1s
	fmt.Println(" Given Binary A : ", a)
	fmt.Println(" Given Binary B : ", b)
	// Display multiply value
	fmt.Println(" Result : ", this.multiply(a, b))
}
func main() {
	var task * Multiplication = getMultiplication()
	// Test A
	//   a = 1011 => 11
	//   b = 101  => 5
	//   11 * 5 => 55 
	//   55 = [110111] 
	// Result = 55
	task.multiplyBinary("1011", "101")
	// Test B
	//   a = 1111 => 15
	//   b = 1010  => 10
	//   15 * 10 => 150 
	//   150 = [10010110] 
	//  Result = 150
	task.multiplyBinary("1111", "1010")
}

Output

 Given Binary A : 1011
 Given Binary B : 101
 Result : 55
 Given Binary A : 1111
 Given Binary B : 1010
 Result : 150
<?php
/*
    Php Program for
    karatsuba algorithm for fast multiplication
*/
class Multiplication
{
	public	function prefixZero($n)
	{
		$zero = "";
		for ($i = 0; $i < $n; $i++)
		{
			$zero .= "0";
		}
		return $zero;
	}

	function addBitStrings($a, $b)
	{
		$result = "";
		$carry = 0;
		$first = $a;
		$second = $b;
		if (strlen($first) < strlen($second))
		{
			$first = $this->prefixZero(
              strlen($second) - strlen($first)).$first;
		}
		if (strlen($second) < strlen($first))
		{
			$second = $this->prefixZero(
              strlen($first) - strlen($second)).$second;
		}
		$length = strlen($first);
		for ($i = $length - 1; $i >= 0; --$i)
		{
			$firstBit = ord($first[$i]) - ord('0');
			$secondBit = ord($second[$i]) - ord('0');
			$sum = ($firstBit ^ $secondBit ^ $carry) + ord('0');
			$result = strval(chr($sum)).$result;
			$carry = ($firstBit & $secondBit) | 
              ($secondBit & $carry) | 
              ($firstBit & $carry);
		}
		if ($carry != 0)
		{
			$result = "1".$result;
		}
		return $result;
	}
	public	function multiply($a, $b)
	{
		// Collecting given string binary value
		$v1 = $a;
		$v2 = $b;
		// Converting the both strings in equal 
		// length by adding some  prefix zero.
		if (strlen($v1) > strlen($v2))
		{
			$v2 = $this->prefixZero(strlen($v1) - strlen($v2)).$v2;
		}
		if (strlen($v2) > strlen($v1))
		{
			$v1 = $this->prefixZero(strlen($v2) - strlen($v1)).$v1;
		}
		// Get the size of equal string
		$size = strlen($v1);
		if ($size == 0)
		{
			// When string is empty
			return 0;
		}
		else if ($size == 1)
		{
			// When single character exists in both string
			return (ord($v1[0]) - ord('0')) * (ord($v2[0]) - ord('0'));
		}
		// Get length of first half
		//
		//   Example
		//              
		//   ₓ = 13
		//   ₓ
		//   ─ = 6
		//   2 
		//
		//   Index start with zero, So here 6 index at 7th position
		//   ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ 
		//   |<─────────>|
		//    firstHalf
		//
		$firstHalf = (int)($size / 2);
		// Example of second half
		//
		//   Example
		//               
		//   ₓ = 13
		//   ₓ
		//   ─ = 6 <- first half
		//   2 
		//   
		//   13 - 6 = 7
		//  Index start with zero, So here 7 index at 8th position
		//   ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ 
		//   |<───────────>|
		//     Second half
		//
		$secondHalf = ($size - $firstHalf);
		// Get prefix of v1 of size first half
		$leftA = substr($v1, 0, $firstHalf);
		// Get remaining character v1
		$rightA = substr($v1, $firstHalf);
		// Get prefix of v2 of size first half
		$leftB = substr($v2, 0, $firstHalf);
		// Get remaining character of v2
		$rightB = substr($v2, $firstHalf);
		// Get three products
		$p1 = $this->multiply($leftA, $leftB);
		$p2 = $this->multiply($rightA, $rightB);
		$p3 = $this->multiply(
          $this->addBitStrings($leftA, $rightA), 
          $this->addBitStrings($leftB, $rightB));
		return $p1 * (1 << (2 * $secondHalf)) + 
          ($p3 - $p1 - $p2) * (1 << $secondHalf) + $p2;
	}
	public	function multiplyBinary($a, $b)
	{
		// Display given binary value
		// Assume that given a and b contain 0 and 1s
		echo(" Given Binary A : ".$a."\n");
		echo(" Given Binary B : ".$b."\n");
		// Display multiply value
		echo(" Result : ".$this->multiply($a, $b)."\n");
	}
}

function main()
{
	$task = new Multiplication();
	// Test A
	//   a = 1011 => 11
	//   b = 101  => 5
	//   11 * 5 => 55 
	//   55 = [110111] 
	// Result = 55
	$task->multiplyBinary("1011", "101");
	// Test B
	//   a = 1111 => 15
	//   b = 1010  => 10
	//   15 * 10 => 150 
	//   150 = [10010110] 
	//  Result = 150
	$task->multiplyBinary("1111", "1010");
}
main();

Output

 Given Binary A : 1011
 Given Binary B : 101
 Result : 55
 Given Binary A : 1111
 Given Binary B : 1010
 Result : 150
/*
    Node JS Program for
    karatsuba algorithm for fast multiplication
*/
class Multiplication
{
	prefixZero(n)
	{
		var zero = "";
		for (var i = 0; i < n; i++)
		{
			zero += "0";
		}
		return zero;
	}
	addBitStrings(a, b)
	{
		var result = "";
		var carry = 0;
		var first = a;
		var second = b;
		if (first.length < second.length)
		{
			first = this.prefixZero(
              second.length - first.length
            ) + first;
		}
		if (second.length < first.length)
		{
			second = this.prefixZero(
              first.length - second.length
            ) + second;
		}
		var length = first.length;
		for (var i = length - 1; i >= 0; --i)
		{
			var firstBit = first.charCodeAt(i) - '0'.charCodeAt(0);
			var secondBit = second.charCodeAt(i) - '0'.charCodeAt(0);
			var sum = (firstBit ^ secondBit ^ carry) + '0'.charCodeAt(0);
			result = String.fromCharCode(sum) + result;
			carry = (firstBit & secondBit) | 
              		(secondBit & carry) | 
              		(firstBit & carry);
		}
		if (carry != 0)
		{
			result = '1' + result;
		}
		return result;
	}
	multiply(a, b)
	{
		// Collecting given string binary value
		var v1 = a;
		var v2 = b;
		// Converting the both strings in equal 
		// length by adding some  prefix zero.
		if (v1.length > v2.length)
		{
			v2 = this.prefixZero(v1.length - v2.length) + v2;
		}
		if (v2.length > v1.length)
		{
			v1 = this.prefixZero(v2.length - v1.length) + v1;
		}
		// Get the size of equal string
		var size = v1.length;
		if (size == 0)
		{
			// When string is empty
			return 0;
		}
		else if (size == 1)
		{
			// When single character exists in both string
			return (v1.charCodeAt(0) - '0'.charCodeAt(0)) * 
              (v2.charCodeAt(0) - '0'.charCodeAt(0));
		}
		// Get length of first half
		//
		//   Example
		//              
		//   ₓ = 13
		//   ₓ
		//   ─ = 6
		//   2 
		//
		//   Index start with zero, So here 6 index at 7th position
		//   ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ 
		//   |<─────────>|
		//    firstHalf
		//
		var firstHalf = parseInt(size / 2);
		// Example of second half
		//
		//   Example
		//               
		//   ₓ = 13
		//   ₓ
		//   ─ = 6 <- first half
		//   2 
		//   
		//   13 - 6 = 7
		//  Index start with zero, So here 7 index at 8th position
		//   ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ 
		//   |<───────────>|
		//     Second half
		//
		var secondHalf = (size - firstHalf);
		// Get prefix of v1 of size first half
		var leftA = v1.substring(0, firstHalf);
		// Get remaining character v1
		var rightA = v1.substring(firstHalf);
		// Get prefix of v2 of size first half
		var leftB = v2.substring(0, firstHalf);
		// Get remaining character of v2
		var rightB = v2.substring(firstHalf);
		// Get three products
		var p1 = this.multiply(leftA, leftB);
		var p2 = this.multiply(rightA, rightB);
		var p3 = this.multiply(
          this.addBitStrings(leftA, rightA), 
          this.addBitStrings(leftB, rightB)
        );
		return p1 * (1 << (2 * secondHalf)) + 
          (p3 - p1 - p2) * (1 << secondHalf) + p2;
	}
	multiplyBinary(a, b)
	{
		// Display given binary value
		// Assume that given a and b contain 0 and 1s
		console.log(" Given Binary A : " + a);
		console.log(" Given Binary B : " + b);
		// Display multiply value
		console.log(" Result : " + this.multiply(a, b));
	}
}

function main()
{
	var task = new Multiplication();
	// Test A
	//   a = 1011 => 11
	//   b = 101  => 5
	//   11 * 5 => 55 
	//   55 = [110111] 
	// Result = 55
	task.multiplyBinary("1011", "101");
	// Test B
	//   a = 1111 => 15
	//   b = 1010  => 10
	//   15 * 10 => 150 
	//   150 = [10010110] 
	//  Result = 150
	task.multiplyBinary("1111", "1010");
}
main();

Output

 Given Binary A : 1011
 Given Binary B : 101
 Result : 55
 Given Binary A : 1111
 Given Binary B : 1010
 Result : 150
#    Python 3 Program for
#    karatsuba algorithm for fast multiplication
class Multiplication :
	def prefixZero(self, n) :
		zero = ""
		i = 0
		while (i < n) :
			zero += "0"
			i += 1
		
		return zero
	
	def addBitStrings(self, a, b) :
		result = ""
		carry = 0
		first = a
		second = b
		if (len(first) < len(second)) :
			first = self.prefixZero(len(second) - len(first)) + first
		
		if (len(second) < len(first)) :
			second = self.prefixZero(len(first) - len(second)) + second
		
		length = len(first)
		i = length - 1
		while (i >= 0) :
			firstBit = ord(first[i]) - ord('0')
			secondBit = ord(second[i]) - ord('0')
			sum = (firstBit ^ secondBit ^ carry) + ord('0')
			result = str(chr(sum)) + result
			carry = (firstBit & secondBit) | (secondBit & carry) | (firstBit & carry)
			i -= 1
		
		if (carry != 0) :
			result = str('1') + result
		
		return result
	
	def multiply(self, a, b) :
		#  Collecting given string binary value
		v1 = a
		v2 = b
		#  Converting the both strings in equal 
		#  length by adding some  prefix zero.
		if (len(v1) > len(v2)) :
			v2 = self.prefixZero(len(v1) - len(v2)) + v2
		
		if (len(v2) > len(v1)) :
			v1 = self.prefixZero(len(v2) - len(v1)) + v1
		
		#  Get the size of equal string
		size = len(v1)
		if (size == 0) :
			#  When string is empty
			return 0
		elif (size == 1) :
			#  When single character exists in both string
			return (ord(v1[0]) - ord('0')) * (ord(v2[0]) - ord('0'))
		
		#  Get length of first half
		#    Example
		#    ₓ = 13
		#    ₓ
		#    ─ = 6
		#    2 
		#    Index start with zero, So here 6 index at 7th position
		#    ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ 
		#    |<─────────>|
		#     firstHalf
		firstHalf = int(size / 2)
		#  Example of second half
		#    Example
		#    ₓ = 13
		#    ₓ
		#    ─ = 6 <- first half
		#    2 
		#    13 - 6 = 7
		#   Index start with zero, So here 7 index at 8th position
		#    ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ 
		#    |<───────────>|
		#      Second half
		secondHalf = (size - firstHalf)
		#  Get prefix of v1 of size first half
		leftA = v1[0: firstHalf]
		#  Get remaining character v1
		rightA = v1[firstHalf: ]
		#  Get prefix of v2 of size first half
		leftB = v2[0: firstHalf]
		#  Get remaining character of v2
		rightB = v2[firstHalf: ]
		#  Get three products
		p1 = self.multiply(leftA, leftB)
		p2 = self.multiply(rightA, rightB)
		p3 = self.multiply(
          self.addBitStrings(leftA, rightA), 
          self.addBitStrings(leftB, rightB))
		return p1 * (1 << (2 * secondHalf)) + (p3 - p1 - p2) * (1 << secondHalf) + p2
	
	def multiplyBinary(self, a, b) :
		#  Display given binary value
		#  Assume that given a and b contain 0 and 1s
		print(" Given Binary A : ", a)
		print(" Given Binary B : ", b)
		#  Display multiply value
		print(" Result : ", self.multiply(a, b))
	

def main() :
	task = Multiplication()
	#  Test A
	#    a = 1011 => 11
	#    b = 101  => 5
	#    11 * 5 => 55 
	#    55 = [110111] 
	#  Result = 55
	task.multiplyBinary("1011", "101")
	#  Test B
	#    a = 1111 => 15
	#    b = 1010  => 10
	#    15 * 10 => 150 
	#    150 = [10010110] 
	#   Result = 150
	task.multiplyBinary("1111", "1010")

if __name__ == "__main__": main()

Output

 Given Binary A :  1011
 Given Binary B :  101
 Result :  55
 Given Binary A :  1111
 Given Binary B :  1010
 Result :  150
#    Ruby Program for
#    karatsuba algorithm for fast multiplication
class Multiplication 
	def prefixZero(n) 
		zero = ""
		i = 0
		while (i < n) 
			zero += "0"
			i += 1
		end

		return zero
	end

	def addBitStrings(a, b) 
		result = ""
		carry = 0
		first = a
		second = b
		if (first.length < second.length) 
			first = self.prefixZero(second.length - first.length) + first
		end

		if (second.length < first.length) 
			second = self.prefixZero(first.length - second.length) + second
		end

		length = first.length
		i = length - 1
		while (i >= 0) 
			firstBit = first[i].ord - '0'.ord
			secondBit = second[i].ord - '0'.ord
			sum = (firstBit ^ secondBit ^ carry) + '0'.ord
			result = (sum).chr.to_s + result
			carry = (firstBit & secondBit) | 
              (secondBit & carry) | 
              (firstBit & carry)
			i -= 1
		end

		if (carry != 0) 
			result = '1'.to_s + result
		end

		return result
	end

	def multiply(a, b) 
		#  Collecting given string binary value
		v1 = a
		v2 = b
		#  Converting the both strings in equal 
		#  length by adding some  prefix zero.
		if (v1.length > v2.length) 
			v2 = self.prefixZero(v1.length - v2.length) + v2
		end

		if (v2.length > v1.length) 
			v1 = self.prefixZero(v2.length - v1.length) + v1
		end

		#  Get the size of equal string
		size = v1.length
		if (size == 0) 
			#  When string is empty
			return 0
		elsif (size == 1) 
			#  When single character exists in both string
			return (v1[0].ord - '0'.ord) * (v2[0].ord - '0'.ord)
		end

		#  Get length of first half
		#    Example
		#    ₓ = 13
		#    ₓ
		#    ─ = 6
		#    2 
		#    Index start with zero, So here 6 index at 7th position
		#    ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ 
		#    |<─────────>|
		#     firstHalf
		firstHalf = size / 2
		#  Example of second half
		#    Example
		#    ₓ = 13
		#    ₓ
		#    ─ = 6 <- first half
		#    2 
		#    13 - 6 = 7
		#   Index start with zero, So here 7 index at 8th position
		#    ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ 
		#    |<───────────>|
		#      Second half
		secondHalf = (size - firstHalf)
		#  Get prefix of v1 of size first half
		leftA = v1[0...firstHalf]
		#  Get remaining character v1
		rightA = v1[firstHalf...(v1.length)]
		#  Get prefix of v2 of size first half
		leftB = v2[0...firstHalf]
		#  Get remaining character of v2
		rightB = v2[firstHalf...(v2.length)]
		#  Get three products
		p1 = self.multiply(leftA, leftB)
		p2 = self.multiply(rightA, rightB)
		p3 = self.multiply(self.addBitStrings(leftA, rightA), self.addBitStrings(leftB, rightB))
		return p1 * (1 << (2 * secondHalf)) + 
          (p3 - p1 - p2) * (1 << secondHalf) + p2
	end

	def multiplyBinary(a, b) 
		#  Display given binary value
		#  Assume that given a and b contain 0 and 1s
		print(" Given Binary A : ", a, "\n")
		print(" Given Binary B : ", b, "\n")
		#  Display multiply value
		print(" Result : ", self.multiply(a, b), "\n")
	end

end

def main() 
	task = Multiplication.new()
	#  Test A
	#    a = 1011 => 11
	#    b = 101  => 5
	#    11 * 5 => 55 
	#    55 = [110111] 
	#  Result = 55
	task.multiplyBinary("1011", "101")
	#  Test B
	#    a = 1111 => 15
	#    b = 1010  => 10
	#    15 * 10 => 150 
	#    150 = [10010110] 
	#   Result = 150
	task.multiplyBinary("1111", "1010")
end

main()

Output

 Given Binary A : 1011
 Given Binary B : 101
 Result : 55
 Given Binary A : 1111
 Given Binary B : 1010
 Result : 150

/*
    Scala Program for
    karatsuba algorithm for fast multiplication
*/
class Multiplication()
{
	def prefixZero(n: Int): String = {
		var zero: String = "";
		var i: Int = 0;
		while (i < n)
		{
			zero += "0";
			i += 1;
		}
		return zero;
	}
	def addBitStrings(a: String, b: String): String = {
		var result: String = "";
		var carry: Int = 0;
		var first: String = a;
		var second: String = b;
		if (first.length() < second.length())
		{
			first = prefixZero(
              second.length() - first.length()
            ) + first;
		}
		if (second.length() < first.length())
		{
			second = prefixZero(
              first.length() - second.length()
            ) + second;
		}
		var length: Int = first.length();
		var i: Int = length - 1;
		while (i >= 0)
		{
			var firstBit: Int = first.charAt(i).toInt - '0'.toInt;
			var secondBit: Int = second.charAt(i).toInt - '0'.toInt;
			var sum: Int = (firstBit ^ secondBit ^ carry) + '0'.toInt;
			result = sum.toChar.toString() + result;
			carry = (firstBit & secondBit) | 
              (secondBit & carry) | 
              (firstBit & carry);
			i -= 1;
		}
		if (carry != 0)
		{
			result = '1'.toString() + result;
		}
		return result;
	}
	def multiply(a: String, b: String): Long = {
		// Collecting given string binary value
		var v1: String = a;
		var v2: String = b;
		// Converting the both strings in equal 
		// length by adding some  prefix zero.
		if (v1.length() > v2.length())
		{
			v2 = prefixZero(v1.length() - v2.length()) + v2;
		}
		if (v2.length() > v1.length())
		{
			v1 = prefixZero(v2.length() - v1.length()) + v1;
		}
		// Get the size of equal string
		var size: Int = v1.length();
		if (size == 0)
		{
			// When string is empty
			return 0;
		}
		else if (size == 1)
		{
			// When single character exists in both string
			return (v1.charAt(0).toInt - '0'.toInt) * 
              (v2.charAt(0).toInt - '0'.toInt);
		}
		// Get length of first half
		//
		//   Example
		//              
		//   ₓ = 13
		//   ₓ
		//   ─ = 6
		//  2 
		//
		//   Index start with zero, So here 6 index at 7th position
		//   ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ 
		//   |<─────────>|
		//    firstHalf
		//
		var firstHalf: Int = size / 2;
		// Example of second half
		//
		//   Example
		//               
		//   ₓ = 13
		//   ₓ
		//   ─ = 6 <- first half
		//   2 
		//   
		//   13 - 6 = 7
		//  Index start with zero, So here 7 index at 8th position
		//   ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ 
		//   |<───────────>|
		//     Second half
		//
		var secondHalf: Int = (size - firstHalf);
		// Get prefix of v1 of size first half
		var leftA: String = v1.substring(0, firstHalf);
		// Get remaining character v1
		var rightA: String = v1.substring(firstHalf);
		// Get prefix of v2 of size first half
		var leftB: String = v2.substring(0, firstHalf);
		// Get remaining character of v2
		var rightB: String = v2.substring(firstHalf);
		// Get three products
		var p1: Long = multiply(leftA, leftB);
		var p2: Long = multiply(rightA, rightB);
		var p3: Long = multiply(
          addBitStrings(leftA, rightA), 
          addBitStrings(leftB, rightB));
		return p1 * (1 << (2 * secondHalf)) + 
          (p3 - p1 - p2) * (1 << secondHalf) + p2;
	}
	def multiplyBinary(a: String, b: String): Unit = {
		// Display given binary value
		// Assume that given a and b contain 0 and 1s
		println(" Given Binary A : " + a);
		println(" Given Binary B : " + b);
		// Display multiply value
		println(" Result : " + multiply(a, b));
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Multiplication = new Multiplication();
		// Test A
		//   a = 1011 => 11
		//   b = 101  => 5
		//   11 * 5 => 55 
		//   55 = [110111] 
		// Result = 55
		task.multiplyBinary("1011", "101");
		// Test B
		//   a = 1111 => 15
		//   b = 1010  => 10
		//   15 * 10 => 150 
		//   150 = [10010110] 
		//  Result = 150
		task.multiplyBinary("1111", "1010");
	}
}

Output

 Given Binary A : 1011
 Given Binary B : 101
 Result : 55
 Given Binary A : 1111
 Given Binary B : 1010
 Result : 150
/*
    Kotlin Program for
    karatsuba algorithm for fast multiplication
*/
class Multiplication
{
	fun prefixZero(n: Int): String
	{
		var zero: String = "";
		var i: Int = 0;
		while (i < n)
		{
			zero += "0";
			i += 1;
		}
		return zero;
	}
	fun addBitStrings(a: String, b: String): String
	{
		var result: String = "";
		var carry: Int = 0;
		var first: String = a;
		var second: String = b;
		if (first.length < second.length)
		{
			first = this.prefixZero(
              second.length - first.length
            ) + first;
		}
		if (second.length < first.length)
		{
			second = this.prefixZero(
              first.length - second.length
            ) + second;
		}
		val length: Int = first.length;
		var i: Int = length - 1;
		while (i >= 0)
		{
			val firstBit: Int = first.get(i).toInt() - '0'.toInt();
			val secondBit: Int = second.get(i).toInt() - '0'.toInt();
			val sum: Int = (firstBit xor secondBit xor carry) + '0'.toInt();
			result = sum.toChar().toString() + result;
			carry = (firstBit and secondBit) or 
            (secondBit and carry) or 
            (firstBit and carry);
			i -= 1;
		}
		if (carry != 0)
		{
			result = '1'.toString() + result;
		}
		return result;
	}
	fun multiply(a: String, b: String): Long
	{
		// Collecting given string binary value
		var v1: String = a;
		var v2: String = b;
		// Converting the both strings in equal 
		// length by adding some  prefix zero.
		if (v1.length > v2.length)
		{
			v2 = this.prefixZero(v1.length - v2.length) + v2;
		}
		if (v2.length > v1.length)
		{
			v1 = this.prefixZero(v2.length - v1.length) + v1;
		}
		// Get the size of equal string
		val size: Int = v1.length;
		if (size == 0)
		{
			// When string is empty
			return 0;
		}
		else if (size == 1)
		{
			// When single character exists in both string
			return (v1.get(0).toInt() - '0'.toInt()) * 
              (v2.get(0).toInt() - '0'.toInt()).toLong();
		}
		// Get length of first half
		//
		//   Example
		//              
		//   ₓ = 13
		//   ₓ
		//   ─ = 6
		//   2 
		//
		//   Index start with zero, So here 6 index at 7th position
		//   ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ 
		//   |<─────────>|
		//    firstHalf
		//
		val firstHalf: Int = size / 2;
		// Example of second half
		//
		//   Example
		//               
		//   ₓ = 13
		//   ₓ
		//   ─ = 6 <- first half
		//   2 
		//   
		//   13 - 6 = 7
		//  Index start with zero, So here 7 index at 8th position
		//   ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ ₓ 
		//   |<───────────>|
		//     Second half
		//
		val secondHalf: Int = (size - firstHalf);
		// Get prefix of v1 of size first half
		val leftA: String = v1.substring(0, firstHalf);
		// Get remaining character v1
		val rightA: String = v1.substring(firstHalf);
		// Get prefix of v2 of size first half
		val leftB: String = v2.substring(0, firstHalf);
		// Get remaining character of v2
		val rightB: String = v2.substring(firstHalf);
		// Get three products
		val p1: Long = this.multiply(leftA, leftB);
		val p2: Long = this.multiply(rightA, rightB);
		val p3: Long = this.multiply(
          this.addBitStrings(leftA, rightA), 
          this.addBitStrings(leftB, rightB));
		return p1 * (1 shl(2 * secondHalf)) + 
          (p3 - p1 - p2) * (1 shl secondHalf) + p2;
	}
	fun multiplyBinary(a: String, b: String): Unit
	{
		// Display given binary value
		// Assume that given a and b contain 0 and 1s
		println(" Given Binary A : " + a);
		println(" Given Binary B : " + b);
		// Display multiply value
		println(" Result : " + this.multiply(a, b));
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Multiplication = Multiplication();
	// Test A
	//   a = 1011 => 11
	//   b = 101  => 5
	//   11 * 5 => 55 
	//   55 = [110111] 
	// Result = 55
	task.multiplyBinary("1011", "101");
	// Test B
	//   a = 1111 => 15
	//   b = 1010  => 10
	//   15 * 10 => 150 
	//   150 = [10010110] 
	//  Result = 150
	task.multiplyBinary("1111", "1010");
}

Output

 Given Binary A : 1011
 Given Binary B : 101
 Result : 55
 Given Binary A : 1111
 Given Binary B : 1010
 Result : 150
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment