CodeCogs

Main Karatsuba recursive algorithm

You're viewing an older version of this page (#232). View the current version.

Interface

#include <codecogs/maths/combinatorics/arithmetic/karatsuba.h>

using namespace Maths::Combinatorics::Arithmetic;

std::string karatsuba_mul(std::string a, std::string b, int base = 10)
std::string karatsuba(std::string a, std::string b, int base = 10)

Overview

This module performs multiplication of two long positive integers using the Karatsuba algorithm, in the given numerical base.

FUNCTION

karatsuba_mul

It is possible to perform multiplication of large numbers in (many) fewer operations than the usual brute-force technique of "long multiplication". As discovered by Karatsuba (Karatsuba and Ofman 1962), multiplication of two $n$ digit numbers can be done with a bit complexity of less than $n^2$ using identities of the form

$(a + b \cdot 10^n)(c + d \cdot 10^n) = ac + [(a + b)(c + d) - ac - bd] \cdot 10^n + bd \cdot 10^{2n}$

(1)

Proceeding recursively then gives bit complexity $O(n^{\mathrm{lg} 3)$ , where $\mathrm{lg} 3 = 1.58 \ldots < 2$ (Borwein et al. 1989).

References

http://mathworld.wolfram.com/KaratsubaMultiplication.html

Parameters

base

Default value = 10

When the length of either the factors is less than a certain threshold, the school multiplication algorithm is used.

Interactive Calculator

base

Result –

FUNCTION

karatsuba

This function calculates the multiplication of two long <em> positive </em> integers stored as character strings, in the given numerical base. The maximum number of digits of either the numbers is only limited by the amount of memory available. The algorithm used is Karatsuba multiplication which has time complexity

$O(n^{\mathrm{lg} 3}) \qquad n = \ceil \left( \mathrm{log}_2 Max \{\, |a|, |b| \,\} \right)$

(2)

where $|a|$ is the length (number of digits) of a and $|b|$ is the length of b.

Because of the way it is designed, the Karatsuba algorithm executes faster when the length of either the numbers is a power of 2.

Example:

#include <codecogs/maths/arithmetic/karatsuba.h>
#include <iostream>

int main()
{
  std::string a("6312341234324335"), b("346632"),
  c = Maths::Arithmetic::karatsuba(a, b, 8);
  std::cout << "The following is a base 8 operation" << std::endl;
  std::cout << a << " * " << b << " = " << c << std::endl;
  return 0;
}

Output:

The following is a base 8 operation
6312341234324335 * 346632 = 2704037244536535306762

Parameters

the first factor

the second factor

base

Default value = 10

Returns

a character string corresponding to the multiplication of the given numbers

Interactive Calculator

base

Result –