I have forgotten

• https://me.yahoo.com
COST (GBP)
4.18
6.96
0

# karatsuba

Main Karatsuba recursive algorithm
Controller: CodeCogs

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  digit numbers can be done with a bit complexity of less than  using identities of the form



Proceeding recursively then gives bit complexity , where  (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

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