Karatsuba Algorithm for fast Multiplication of Large Decimal Numbers represented as Strings - Coding

Given two numeric strings A and B, the task is to find the product of the two numeric strings efficiently.

Example:

Input: A = 5678, B = 1234
Output: 7006652

Input: A = 74638463789, B = 35284567382
Output: 2633585904851937530398

Approach: The given problem can be solved using Karastuba’s Algorithm for Fast Multiplication, the idea is to append zeroes in front of the integers such that both the integers have an equal and even number of digits n. Thereafter, divide the numbers in the following way:

A = Al * 10^n/2 + Ar [Al and Ar contain leftmost and rightmost n/2 digits of A]
B = Bl * 10^n/2 + Br [Bl and Br contain leftmost and rightmost n/2 digits of B]

Therefore, the product A * B can also be represented as follows:

A * B = (Al * 10^n/2 + Ar) * (Bl * 10^n/2 + Br)
=> A * B = 10ⁿ*Al*Bl + 10^n/2*(Al*Br + Bl*Ar) + Ar*Br
=> A * B = 10ⁿ*Al*Bl + 10^n/2*((Al + Ar)*(Bl + Br) – Al*Bl – Ar*Br) + Ar*Br [since Al*Br + Bl*Ar = (Al + Ar)*(Bl + Br) – Al*Bl – Ar*Br]

Notice that the above expression only requires three multiplications Al*Bl, Ar*Br, and (Al + Ar)*(Bl + Br), instead of the standard four. Hence, the recurrence becomes T(n) = 3T(n/2) + O(n) and solution of this recurrence is O(n^1.59). This idea has been discussed more thoroughly in this article. Therefore the above problem can be solved using the steps below:

Create a function findSum(), which finds the sum of two large numbers represented as strings. Similarly, create a function findDiff(), which finds the difference of two large numbers represented as strings.
In the recursive function multiply(A, B), which multiplies the numbers using Karatsuba’s Algorithm, firstly append zeroes in front of A and B to make their digit count equal and even.
Then calculate the values of Al, Ar, Bl, and Br as defined above and recursively find the values of multiply(Al, Bl), multiply(Ar, Br), and multiply((Al + Ar), (Bl + Br)) and plug their values in the above-derived equation.
Print the answer to the equation after removing the leading zeroes from it.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the sum of larger
// numbers represented as a string
string findSum(string str1, string str2)
{
    // Before proceeding further, make
    // sure length of str2 is larger
    if (str1.length() > str2.length())
        swap(str1, str2);
 
    // Stores the result
    string str = "";
 
    // Calculate length of both string
    int n1 = str1.length();
    int n2 = str2.length();
 
    // Reverse both of strings
    reverse(str1.begin(), str1.end());
    reverse(str2.begin(), str2.end());
 
    int carry = 0;
    for (int i = 0; i < n1; i++) {
 
        // Find the sum of the current
        // digits and carry
        int sum
            = ((str1[i] - '0')
               + (str2[i] - '0')
               + carry);
        str.push_back(sum % 10 + '0');
 
        // Calculate carry for next step
        carry = sum / 10;
    }
 
    // Add remaining digits of larger number
    for (int i = n1; i < n2; i++) {
        int sum = ((str2[i] - '0') + carry);
        str.push_back(sum % 10 + '0');
        carry = sum / 10;
    }
 
    // Add remaining carry
    if (carry)
        str.push_back(carry + '0');
 
    // Reverse resultant string
    reverse(str.begin(), str.end());
 
    return str;
}
 
// Function to find difference of larger
// numbers represented as strings
string findDiff(string str1, string str2)
{
    // Stores the result of difference
    string str = "";
 
    // Calculate length of both string
    int n1 = str1.length(), n2 = str2.length();
 
    // Reverse both of strings
    reverse(str1.begin(), str1.end());
    reverse(str2.begin(), str2.end());
 
    int carry = 0;
 
    // Run loop till small string length
    // and subtract digit of str1 to str2
    for (int i = 0; i < n2; i++) {
 
        // Compute difference of the
        // current digits
        int sub
            = ((str1[i] - '0')
               - (str2[i] - '0')
               - carry);
 
        // If subtraction < 0 then add 10
        // into sub and take carry as 1
        if (sub < 0) {
            sub = sub + 10;
            carry = 1;
        }
        else
            carry = 0;
 
        str.push_back(sub + '0');
    }
 
    // Subtract the remaining digits of
    // larger number
    for (int i = n2; i < n1; i++) {
        int sub = ((str1[i] - '0') - carry);
 
        // If the sub value is -ve,
        // then make it positive
        if (sub < 0) {
            sub = sub + 10;
            carry = 1;
        }
        else
            carry = 0;
 
        str.push_back(sub + '0');
    }
 
    // Reverse resultant string
    reverse(str.begin(), str.end());
 
    // Return answer
    return str;
}
 
// Function to remove all leading 0s
// from a given string
string removeLeadingZeros(string str)
{
    // Regex to remove leading 0s
    // from a string
    const regex pattern("^0+(?!$)");
 
    // Replaces the matched value
    // with given string
    str = regex_replace(str, pattern, "");
    return str;
}
 
// Function to multiply two numbers
// using Karatsuba algorithm
string multiply(string A, string B)
{
    if (A.length() > B.length())
        swap(A, B);
 
    // Make both numbers to have
    // same digits
    int n1 = A.length(), n2 = B.length();
    while (n2 > n1) {
        A = "0" + A;
        n1++;
    }
 
    // Base case
    if (n1 == 1) {
 
        // If the length of strings is 1,
        // then return their product
        int ans = stoi(A) * stoi(B);
        return to_string(ans);
    }
 
    // Add zeros in the beginning of
    // the strings when length is odd
    if (n1 % 2 == 1) {
        n1++;
        A = "0" + A;
        B = "0" + B;
    }
 
    string Al, Ar, Bl, Br;
 
    // Find the values of Al, Ar,
    // Bl, and Br.
    for (int i = 0; i < n1 / 2; ++i) {
        Al += A[i];
        Bl += B[i];
        Ar += A[n1 / 2 + i];
        Br += B[n1 / 2 + i];
    }
 
    // Recursively call the function
    // to compute smaller product
 
    // Stores the value of Al * Bl
    string p = multiply(Al, Bl);
 
    // Stores the value of Ar * Br
    string q = multiply(Ar, Br);
 
    // Stores value of ((Al + Ar)*(Bl + Br)
    // - Al*Bl - Ar*Br)
    string r = findDiff(
        multiply(findSum(Al, Ar),
                 findSum(Bl, Br)),
        findSum(p, q));
 
    // Multiply p by 10^n
    for (int i = 0; i < n1; ++i)
        p = p + "0";
 
    // Multiply s by 10^(n/2)
    for (int i = 0; i < n1 / 2; ++i)
        r = r + "0";
 
    // Calculate final answer p + r + s
    string ans = findSum(p, findSum(q, r));
 
    // Remove leading zeroes from ans
    ans = removeLeadingZeros(ans);
 
    // Return Answer
    return ans;
}
 
// Driver Code
int main()
{
    string A = "74638463789";
    string B = "35284567382";
 
    cout << multiply(A, B);
 
    return 0;
}

Java

// Java code for the above approach 
 
import java.io.*;
import java.util.*;
 
class GFG {
   
    // Function to find the sum of larger
    // numbers represented as a string
    public static String findSum(String str1, String str2) {
        // Before proceeding further, make sure length of str2 is larger
        if (str1.length() > str2.length()) {
            String temp = str1;
            str1 = str2;
            str2 = temp;
        }
        // Stores the result
        String str = "";
 
        // Calculate length of both string
        int n1 = str1.length();
        int n2 = str2.length();
 
        // Reverse both of strings
        str1 = new StringBuilder(str1).reverse().toString();
        str2 = new StringBuilder(str2).reverse().toString();
 
        int carry = 0;
        for (int i = 0; i < n1; i++) {
 
            // Find the sum of the current digits and carry
            int sum = ((str1.charAt(i) - '0') + (str2.charAt(i) - '0') + carry);
            str += (char)(sum % 10 + '0');
 
            // Calculate carry for next step
            carry = sum / 10;
        }
 
        // Add remaining digits of larger number
        for (int i = n1; i < n2; i++) {
            int sum = ((str2.charAt(i) - '0') + carry);
            str += (char)(sum % 10 + '0');
            carry = sum / 10;
        }
 
        // Add remaining carry
        if (carry != 0)
            str += (char)(carry + '0');
 
        // Reverse resultant string
        str = new StringBuilder(str).reverse().toString();
 
        return str;
    }
   
    // Function to find difference of larger
    // numbers represented as strings
    static String findDiff(String str1, String str2) {
        // Stores the result of difference
        String str = "";
 
        // Calculate length of both string
        int n1 = str1.length(), n2 = str2.length();
 
        // Reverse both of strings
        StringBuilder sb1 = new StringBuilder(str1);
        StringBuilder sb2 = new StringBuilder(str2);
        sb1 = sb1.reverse();
        sb2 = sb2.reverse();
        str1 = sb1.toString();
        str2 = sb2.toString();
 
        int carry = 0;
 
        // Run loop till small string length
        // and subtract digit of str1 to str2
        for (int i = 0; i < n2; i++) {
 
            // Compute difference of the
            // current digits
            int sub = ((str1.charAt(i) - '0') - (str2.charAt(i) - '0') - carry);
 
            // If subtraction < 0 then add 10
            // into sub and take carry as 1
            if (sub < 0) {
                sub = sub + 10;
                carry = 1;
            } else
                carry = 0;
 
            str += sub;
        }
 
        // Subtract the remaining digits of
        // larger number
        for (int i = n2; i < n1; i++) {
            int sub = ((str1.charAt(i) - '0') - carry);
 
            // If the sub value is -ve,
            // then make it positive
            if (sub < 0) {
                sub = sub + 10;
                carry = 1;
            } else
                carry = 0;
 
            str += sub;
        }
 
        // Reverse resultant string
        str = new StringBuilder(str).reverse().toString();
 
        // Return answer
        return str;
    }
   
    // Function to remove all leading 0s
    // from a given string
    public static String removeLeadingZeros(String str) {
        // Regex to remove leading 0s from a string
        String pattern = "^0+(?!$)";
 
        // Replaces the matched value with given string
        str = str.replaceAll(pattern, "");
        return str;
    }
   
    // Function to multiply two numbers
    // using Karatsuba algorithm
    public static String multiply(String A, String B) {
        if (A.length() > B.length()) {
                String temp = A;
                A = B;
                B = temp;
        }
 
        // Make both numbers to have
        // same digits
        int n1 = A.length(), n2 = B.length();
        while (n2 > n1) {
            A = "0" + A;
            n1++;
        }
 
        // Base case
        if (n1 == 1) {
 
            // If the length of strings is 1,
            // then return their product
            int ans = Integer.parseInt(A) * Integer.parseInt(B);
            return Integer.toString(ans);
        }
 
        // Add zeros in the beginning of
        // the strings when length is odd
        if (n1 % 2 == 1) {
            n1++;
            A = "0" + A;
            B = "0" + B;
        }
 
        String Al = "", Ar = "", Bl = "", Br = "";
 
        // Find the values of Al, Ar,
        // Bl, and Br.
        for (int i = 0; i < n1 / 2; ++i) {
            Al += A.charAt(i);
            Bl += B.charAt(i);
            Ar += A.charAt(n1 / 2 + i);
            Br += B.charAt(n1 / 2 + i);
        }
 
        // Recursively call the function
        // to compute smaller product
 
        // Stores the value of Al * Bl
        String p = multiply(Al, Bl);
 
        // Stores the value of Ar * Br
        String q = multiply(Ar, Br);
 
        // Stores value of ((Al + Ar)*(Bl + Br)
        // - Al*Bl - Ar*Br)
        String r = findDiff( multiply(findSum(Al, Ar), findSum(Bl, Br)), findSum(p, q));
 
        // Multiply p by 10^n
        for (int i = 0; i < n1; ++i)
            p = p + "0";
 
        // Multiply s by 10^(n/2)
        for (int i = 0; i < n1 / 2; ++i)
            r = r + "0";
 
        // Calculate final answer p + r + s
        String ans = findSum(p, findSum(q, r));
 
        // Remove leading zeroes from ans
        ans = removeLeadingZeros(ans);
 
        // Return Answer
        return ans;
    }
 
    public static void main(String[] args) {
        String A = "74638463789";
        String B = "35284567382";
        System.out.println(multiply(A, B));
    }
   
}

Python3

import re
 
# Function to find the sum of larger
# numbers represented as a string
def findSum(str1, str2):
    if len(str1) > len(str2):
        str1, str2 = str2, str1
 
    result = ""
    n1, n2 = len(str1), len(str2)
    str1, str2 = str1.zfill(n2), str2.zfill(n2)
    carry = 0
 
    # Perform addition digit by digit from the right
    for i in range(n2 - 1, -1, -1):
        sum_val = (int(str1[i]) - 0) + (int(str2[i]) - 0) + carry
        result = str(sum_val % 10 + 0) + result
        carry = sum_val // 10
 
    if carry:
        result = str(carry + 0) + result
 
    return result
 
# Function to find the difference of larger
# numbers represented as strings
def findDiff(str1, str2):
    result = ""
    n1, n2 = len(str1), len(str2)
    str1, str2 = str1.zfill(n2), str2.zfill(n2)
    carry = 0
 
    # Perform subtraction digit by digit from the right
    for i in range(n2 - 1, -1, -1):
        sub = (int(str1[i]) - 0) - (int(str2[i]) - 0) - carry
 
        if sub < 0:
            sub += 10
            carry = 1
        else:
            carry = 0
 
        # Append the digit to the result
        result = str(sub + 0) + result
 
    return result
 
# Function to remove all leading 0s
# from a given string
def removeLeadingZeros(s):
    pattern = "^0+(?!$)"
    s = re.sub(pattern, "", s)
    return s
 
# Function to multiply two numbers
# using the Karatsuba algorithm
def multiply(A, B):
    # Base case for small numbers: perform normal multiplication
    if len(A) < 10 or len(B) < 10:
        return str(int(A) * int(B))
 
    n = max(len(A), len(B))
    n2 = n // 2
 
    # Pad the numbers with leading zeros to make them equal in length
    A = A.zfill(n)
    B = B.zfill(n)
 
    # Split the numbers into halves
    Al, Ar = A[:n2], A[n2:]
    Bl, Br = B[:n2], B[n2:]
 
    # Recursively compute partial products and sum using Karatsuba algorithm
    p = multiply(Al, Bl)
    q = multiply(Ar, Br)
    r = multiply(findSum(Al, Ar), findSum(Bl, Br))
    r = findDiff(r, findSum(p, q))
 
    # Combine the partial products to get the final result
    return removeLeadingZeros(findSum(findSum(p + '0' * n, r + '0' * n2), q))
 
 
# Driver Code
if __name__ == "__main__":
    A = "74638463789"
    B = "35284567382"
 
    # Multiply the large numbers A and B using the Karatsuba algorithm
    print(multiply(A, B))

C#

using System;
using System.Linq;
using System.Text;
 
class GFG {
  // Function to find the sum of larger
  // numbers represented as a string
  public static string FindSum(string str1, string str2)
  {
    // Before proceeding further, make sure length of
    // str2 is larger
    if (str1.Length > str2.Length) {
      string temp = str1;
      str1 = str2;
      str2 = temp;
    }
    // Stores the result
    string str = "";
 
    // Calculate length of both string
    int n1 = str1.Length;
    int n2 = str2.Length;
 
    // Reverse both of strings
    str1 = new string(str1.Reverse().ToArray());
    str2 = new string(str2.Reverse().ToArray());
 
    int carry = 0;
    for (int i = 0; i < n1; i++) {
 
      // Find the sum of the current digits and carry
      int sum = ((str1[i] - '0') + (str2[i] - '0')
                 + carry);
      str += (char)(sum % 10 + '0');
 
      // Calculate carry for next step
      carry = sum / 10;
    }
 
    // Add remaining digits of larger number
    for (int i = n1; i < n2; i++) {
      int sum = ((str2[i] - '0') + carry);
      str += (char)(sum % 10 + '0');
      carry = sum / 10;
    }
 
    // Add remaining carry
    if (carry != 0)
      str += (char)(carry + '0');
 
    // Reverse resultant string
    return new string(str.Reverse().ToArray());
  }
 
  // Function to find difference of larger
  // numbers represented as strings
  static string FindDiff(string str1, string str2)
  {
    // Stores the result of difference
    string str = "";
 
    // Calculate length of both string
    int n1 = str1.Length, n2 = str2.Length;
 
    // Reverse both of strings
    str1 = new string(str1.Reverse().ToArray());
    str2 = new string(str2.Reverse().ToArray());
 
    int carry = 0;
 
    // Run loop till small string length
    // and subtract digit of str1 to str2
    for (int i = 0; i < n2; i++) {
 
      // Compute difference of the
      // current digits
      int sub = ((str1[i] - '0') - (str2[i] - '0')
                 - carry);
 
      // If subtraction < 0 then add 10
      // into sub and take carry as 1
      if (sub < 0) {
        sub = sub + 10;
        carry = 1;
      }
      else
        carry = 0;
 
      str += sub;
    }
 
    // Subtract the remaining digits of
    // larger number
    for (int i = n2; i < n1; i++) {
      int sub = ((str1[i] - '0') - carry);
 
      // If the sub value is -ve,
      // then make it positive
      if (sub < 0) {
        sub = sub + 10;
        carry = 1;
      }
      else
        carry = 0;
      str += sub;
    }
 
    return new string(str.Reverse().ToArray());
  }
 
  // Function to remove all leading 0s
  // from a given string
  public static string RemoveLeadingZeros(string input)
  {
    int i = 0;
    while (i < input.Length && input[i] == '0') {
      i++;
    }
 
    return i == input.Length ? "0" : input.Substring(i);
  }
 
  // Function to multiply two numbers
  // using Karatsuba algorithm
  public static string Multiply(string A, string B)
  {
    if (A.Length > B.Length) {
      string temp = A;
      A = B;
      B = temp;
    }
 
    // Make both numbers to have
    // same digits
    int n1 = A.Length, n2 = B.Length;
    while (n2 > n1) {
      A = "0" + A;
      n1++;
    }
 
    // Base case
    if (n1 == 1) {
 
      // If the length of strings is 1,
      // then return their product
      return Convert.ToString(Convert.ToInt32(A)
                              * Convert.ToInt32(B));
    }
 
    // Add zeros in the beginning of
    // the strings when length is odd
    if (n1 % 2 == 1) {
      n1++;
      A = "0" + A;
      B = "0" + B;
    }
 
    string Al = "", Ar = "", Bl = "", Br = "";
 
    // Find the values of Al, Ar,
    // Bl, and Br.
    for (int i = 0; i < n1 / 2; ++i) {
      Al += A[i];
      Bl += B[i];
      Ar += A[n1 / 2 + i];
      Br += B[n1 / 2 + i];
    }
 
    // Recursively call the function
    // to compute smaller product
 
    // Stores the value of Al * Bl
    string p = Multiply(Al, Bl);
 
    // Stores the value of Ar * Br
    string q = Multiply(Ar, Br);
 
    // Stores value of ((Al + Ar)*(Bl + Br)
    // - Al*Bl - Ar*Br)
    string r = FindDiff(
      Multiply(FindSum(Al, Ar), FindSum(Bl, Br)),
      FindSum(p, q));
 
    // Multiply p by 10^n
    for (int i = 0; i < n1; ++i)
      p = p + "0";
 
    // Multiply s by 10^(n/2)
    for (int i = 0; i < n1 / 2; ++i)
      r = r + "0";
 
    // Calculate final answer p + r + s
    string ans = FindSum(p, FindSum(q, r));
 
    // Remove leading zeroes from ans
    ans = RemoveLeadingZeros(ans);
 
    // Return Answer
    return ans;
  }
 
  public static void Main(string[] args)
  {
    string A = "74638463789";
    string B = "35284567382";
    Console.WriteLine(Multiply(A, B));
  }
}

Javascript

// Function to find the sum of larger numbers represented as a string
function findSum(str1, str2) {
    if (str1.length > str2.length) {
        [str1, str2] = [str2, str1]; // Swap strings if str2 is longer
    }
 
    let str = '';
    let n1 = str1.length;
    let n2 = str2.length;
    str1 = str1.split('').reverse().join('');
    str2 = str2.split('').reverse().join('');
 
    let carry = 0;
    for (let i = 0; i < n1; i++) {
        let sum = parseInt(str1[i]) + parseInt(str2[i]) + carry;
        str += (sum % 10).toString();
        carry = Math.floor(sum / 10);
    }
 
    for (let i = n1; i < n2; i++) {
        let sum = parseInt(str2[i]) + carry;
        str += (sum % 10).toString();
        carry = Math.floor(sum / 10);
    }
 
    if (carry) {
        str += carry.toString();
    }
 
    return str.split('').reverse().join('');
}
 
// Function to find the difference of larger numbers represented as strings
function findDiff(str1, str2) {
    let str = '';
    let n1 = str1.length;
    let n2 = str2.length;
    str1 = str1.split('').reverse().join('');
    str2 = str2.split('').reverse().join('');
 
    let carry = 0;
    for (let i = 0; i < n2; i++) {
        let sub = parseInt(str1[i]) - parseInt(str2[i]) - carry;
        if (sub < 0) {
            sub += 10;
            carry = 1;
        } else {
            carry = 0;
        }
        str += sub.toString();
    }
 
    for (let i = n2; i < n1; i++) {
        let sub = parseInt(str1[i]) - carry;
        if (sub < 0) {
            sub += 10;
            carry = 1;
        } else {
            carry = 0;
        }
        str += sub.toString();
    }
 
    return str.split('').reverse().join('');
}
 
// Function to remove all leading 0s from a given string
function removeLeadingZeros(str) {
    return str.replace(/^0+/, '');
}
 
// Function to multiply two numbers using Karatsuba algorithm
function multiply(A, B) {
    if (A.length == 1 || B.length == 1) {
        return (parseInt(A) * parseInt(B)).toString();
    }
 
    let maxLength = Math.max(A.length, B.length);
    let splitPosition = Math.floor(maxLength / 2);
 
    let Al = A.substring(0, A.length - splitPosition);
    let Ar = A.substring(A.length - splitPosition);
    let Bl = B.substring(0, B.length - splitPosition);
    let Br = B.substring(B.length - splitPosition);
 
    let p = multiply(Al, Bl);
    let q = multiply(Ar, Br);
    let r = multiply(findSum(Al, Ar), findSum(Bl, Br));
    r = findDiff(r, findSum(p, q));
 
    for (let i = 0; i < 2 * splitPosition; i++) {
        p += '0';
    }
 
    for (let i = 0; i < splitPosition; i++) {
        r += '0';
    }
 
    let ans = findSum(p, findSum(q, r));
    ans = removeLeadingZeros(ans);
 
    return ans;
}
 
// Driver code
let A = "74638463789";
let B = "35284567382";
console.log(multiply(A, B));

Output

2633585904851937530398

Time Complexity: O(N^{log 3}) or O(N^1.59), where N is the maximum among the lengths given strings A and B.
Auxiliary Space: O(N²)

Reffered: https://www.geeksforgeeks.org

Algorithms

Related
Largest Rectangle Area under Histogram using JavaScript \| Without using Stacks
NL-Completeness and PSPACE-Completeness
Incedo Inc. Interview Experience for SDE/Quality Assurance Engineer \| On-Campus
Indexed Priority Queue with Implementation
FactSet Interview Experience for Software Engineer \| On-Campus 2021

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	13