I have forgotten
my Password

Or login with:

  • Facebookhttp://facebook.com/
  • Googlehttps://www.google.com/accounts/o8/id
  • Yahoohttps://me.yahoo.com
COST (GBP)
this unit 4.18
sub units 6.96
+
0

karatsuba

Main Karatsuba recursive algorithm
Controller: CodeCogs

add cart

Dependents

Info

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_mulstd::stringa
std::stringb
intbase = 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 n digit numbers can be done with a bit complexity of less than n^2 using identities of the form

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

Note

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

Parameters

athe first factor
bthe second factor
baseDefault 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::stringkaratsubastd::stringa
std::stringb
intbase = 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 |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

athe first factor
bthe second factor
baseDefault 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.