COST (GBP)

6.96

Maths › Combinatorics › Arithmetic ›

karatsuba

Main Karatsuba recursive algorithm

Controller: CodeCogs

Contents

Interface
Karatsuba Mul
Karatsuba
Page Comments

Dependents

Interface

C++

Excel

Overview

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

Authors

Anca Filibiu and Lucian Bentea (September 2005)

Karatsuba Mul

std::stringkaratsuba_mul(	std::string	`a`
	std::string	`b`
	int	`base` `= 10`	)

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 $\inline n$ digit numbers can be done with a bit complexity of less than $\inline 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}$

(2)

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

References:

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

Note

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

Parameters

a	the first factor
b	the second factor
base	Default value = 10

Source Code

Source code is available when you buy a Commercial licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.

Karatsuba

std::stringkaratsuba(	std::string	`a`
	std::string	`b`
	int	`base` `= 10`	)

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)$

(3)

where $\inline |a|$ is the length (number of digits) of a and $\inline |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

a	the first factor
b	the second factor
base	Default value = 10

Returns

a character string corresponding to the multiplication of the given numbers

Source Code

Source code is available when you buy a Commercial licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.

String	cc_arithmeticKaratsuba_mul (String a, String b, Integer base)
String	cc_arithmeticKaratsuba (String a, String b, Integer base)

std::string	`karatsuba_mul` (std::string a, std::string b, int base = 10) Main Karatsuba recursive algorithm
std::string	`karatsuba` (std::string a, std::string b, int base = 10) Performs the multiplication of two long positive integers in the given base.