[算法系列之九]Karatsuba快速相乘算法
【概述】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 < ) 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) y1, y0 = split_at(num2,0)">) /* 3 calls made to numbers approximately half the size */ z0 = karatsuba(x0,y0) z1 = karatsuba((x1+x0(y1+y0) z2 = karatsuba(x1,y1return (z2*10^(2*m2)+(z1-z2-z0)*(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,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; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |