【概述】
Karatsuba乘法是一种快速乘法。此算法在1960年由Anatolii Alexeevitch Karatsuba 提出,并于1962年得以发表。
此算法主要用于两个大数相乘。普通乘法的复杂度是n2,而Karatsuba算法的复杂度仅为3nlog3≈3n1.585(log3是以2为底的)
【步骤】
Karatsuba算法主要应用于两个大数的相乘,原理是将大数分成两段后变成较小的数位,然后做3次乘法,并附带少量的加法操作和移位操作。
现有两个大数,x,y。
首先将x,y分别拆开成为两部分,可得x1,x0,y1,y0。他们的关系如下:
x = x1 * 10m + x0;
y = y1 * 10m + y0。其中m为正整数,m < n,且x0,y0 小于 10m。
那么
xy = (x1 * 10m + x0)(y1 * 10m
+ y0)
=z2 * 102m
+ z1 * 10m + z0,其中:
z2 = x1 * y1;
z1 = x1 * y0 + x0 * y1;
z0 = x0 * y0。
此步骤共需4次乘法,但是由Karatsuba改进以后仅需要3次乘法。因为:
z1 = x1 * y0+ x0 * y1
z1 = (x1 + x0) * (y1 + y0) - x1 * y1 - x0 * y0,
故x0 * y0 便可以由加减法得到。
所以:
x*y = z2 * 102m+ z1 * 10m
+ z0
z2 = x1 * y1
z1 = (x1 + x0) * (y1 + y0) - x1 * y1 - x0 * y0 =(x1 + x0) * (y1 + y0) - x1 * y1 - z0
z0 = x0 * y0
Recursively computer (x1*y1)
Recursively computer (x1 + x0) * (y1 + y0)
Recursively computer (x0 * y0)
【实例讲解】
设x = 12345,y=6789,令m=3。那么有:
12345 = 12 * 1000 + 345;
6789 = 6 * 1000 + 789。
下面计算:
z2 = 12 * 6 = 72;
z0 = 345 * 789 = 272205;
z1 = (12 + 345) * (6 + 789) - z2 - z0 = 11538。
然后我们按照移位公式(xy = z2 * 102m + z1 * 10m+
z0)可得:
xy = 72 * 10002 + 11538 * 1000 + 272205 = 83810205。
【伪代码】
procedure karatsuba(num1, num2)
if (num1 < 10) or (num2 < 10)
return num1*num2
/* calculates the size of the numbers */
m = max(size_base10(num1), size_base10(num2))
m2 = m/2
/* split the digit sequences about the middle */
x1, x0 = split_at(num1, m2)
y1, y0 = split_at(num2, m2)
/* 3 calls made to numbers approximately half the size */
z0 = karatsuba(x0,y0)
z1 = karatsuba((x1+x0),(y1+y0))
z2 = karatsuba(x1,y1)
return (z2*10^(2*m2))+((z1-z2-z0)*10^(m2))+(z0)
【代码】
/*********************************
* 日期:2015-01-29
* 作者:SJF0115
* 题目: Karatsuba快速相乘算法
* 博客:
**********************************/
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
// given two unequal sized bit strings, converts them to
// same length by adding leading 0s in the smaller string. Returns the
// the new length
int MakeSameLen(string& num1,string& num2){
int len1 = num1.length();
int len2 = num2.length();
if(len1 < len2){
for(int i = 0;i < len2 - len1;++i){
num1 = "0" + num1;
}//for
return len2;
}//if
else{
for(int i = 0;i < len1 - len2;++i){
num2 = "0" + num2;
}//for
return len1;
}//else
}
// big number minus function
string MinusString(string num1, string num2) {
int len1 = num1.length();
int len2 = num2.length();
// 相等
if(num1 == num2){
return "0";
}//if
// 正负
bool positive = true;
if(len1 < len2 || (len1 == len2 && num1 < num2)){
positive = false;
// 交换使之num1 > num2
string tmp = num1;
num1 = num2;
num2 = tmp;
int temp = len1;
len1 = len2;
len2 = temp;
}//if
string result;
int i = len1 - 1,j = len2 - 1;
int a,b,sum,carray = 0;
// 从低位到高位对位做减法
while(i >= 0 || j >= 0){
a = i >= 0 ? num1[i] - '0' : 0;
b = j >= 0 ? num2[j] - '0' : 0;
sum = a - b + carray;
carray = 0;
// 不够减
if(sum < 0){
sum += 10;
carray = -1;
}//if
result.insert(result.begin(),sum + '0');
--i;
--j;
}//while
// 删除前导0
string::iterator it = result.begin();
while(it != result.end() && *it == '0'){
++it;
}//while
result.erase(result.begin(),it);
return positive ? result : "-"+result;
}
// big number add function
string AddString(string num1,string num2){
int len1 = num1.length();
int len2 = num2.length();
// 容错处理
if(len1 <= 0){
return num2;
}//if
if(len2 <= 0){
return num1;
}
string result;
int i = len1-1,j = len2-1;
int a,b,sum,carry = 0;
// 倒序相加
while(i >= 0 || j >= 0 || carry > 0){
a = i >= 0 ? num1[i] - '0' : 0;
b = j >= 0 ? num2[j] - '0' : 0;
// 按位相加并加上进位
sum = a + b + carry;
// 进位
carry = sum / 10;
result.insert(result.begin(),sum % 10 + '0');
--i;
--j;
}//while
return result;
}
// 移位
string ShiftString(string num,int len){
if(num == "0"){
return num;
}//if
for(int i = 0;i < len;++i){
num += "0";
}//for
return num;
}
// Karatsuba快速相乘算法
string KaratsubaMultiply(string num1, string num2) {
int len = MakeSameLen(num1,num2);
if(len == 0){
return 0;
}//if
// all digit are one
if(len == 1){
return to_string((num1[0] - '0')*(num2[0] - '0'));
}//if
int mid = len / 2;
// Find the first half and second half of first string.
string x1 = num1.substr(0,mid);
string x0 = num1.substr(mid,len - mid);
// Find the first half and second half of second string
string y1 = num2.substr(0,mid);
string y0 = num2.substr(mid,len - mid);
// Recursively computer
string z0 = KaratsubaMultiply(x0,y0);
string z1 = KaratsubaMultiply(AddString(x1,x0),AddString(y1,y0));
string z2 = KaratsubaMultiply(x1,y1);
// (z2*10^(2*m))+((z1-z2-z0)*10^(m))+(z0)
// z2*10^(2*m)
string r1 = ShiftString(z2,2*(len - mid));
// (z1-z2-z0)*10^(m)
string r2 = ShiftString(MinusString(MinusString(z1,z2),z0),len - mid);
return AddString(AddString(r1,r2),z0);
}
int main(){
string num1("12345001");
string num2("1006789");
string result = KaratsubaMultiply(num1,num2);
// 输出
cout<<result<<endl;
return 0;
}
分享到:
相关推荐
两个Toeplitz矩阵相乘的一种快速算法
矩阵相乘FOX并行算法,矩阵相乘FOX并行算法
两个矩阵相乘,经典算法(C),超级好用。
矩阵相乘快速算法 矩阵相乘快速算法 矩阵相乘快速算法
算法课程的学习,有很多的帮助,算法设计与分析矩阵链相乘形象的描述
矩阵相乘的快速算法,O(n2)的时间复杂度
1、熟悉快速排序的串行算法 2、熟悉快速排序的并行算法 3、实现快速排序的并行算法 3.2 实验环境及软件 单台或联网的多台PC机,Linux操作系统,MPI系统。 3.3实验内容 1、快速排序的基本思想 2、单处理机上快速...
利用动态分治思想解决一些如下问题:Strassen矩阵乘法Karatsuba快速乘法最近点对问题源代码(有C/C++程序)
Toeplitz矩阵相乘快速算法,在很多领域有重要应用,可以看看。
算法系列之二十:计算中国农历
矩阵相乘的快速算法.doc
用C++实现的矩阵链相乘算法,并包含大量的注释,对理解程序很有帮助
Strassen 算法 C++ 实现 任意矩阵相乘 用Command line 输入编制好的两个矩阵,输出相乘的结果矩阵。如果需要手动输入,删除程序里的相关语句,添加输入命令即可。
其中,包括两种算法,一个是surf算法的图像拼接,一种是新提出的快速拼接算法。
使用Hadoop MapReduce实现两个矩阵相乘算法
《国际信息工程先进技术译丛·快速傅里叶变换:算法与应用》深入浅出地阐述了快速傅里叶变换(FFT)的原理,系统地总结了各类FFT算法,并广泛精辟地介绍了FFT在视频和音频信号处理中的各种应用。《国际信息工程先进...
大数相乘,算法源码分析,以及相关的实现
并行算法的稠密矩阵相乘,有相应的串行算法和并行算法以及相对应的的程序结果.
算法设计实验报告,包括:快速排序和归并排序两种算法各自的基本思想、时间复杂度分析,C++实现代码,两种算法运行时间的比较,运行截图,实验心得。
算法分析PPT(分治法-大整数、矩阵相乘).ppt)