karatsuba algorithm for fast multiplication
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 : 150package 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
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