[算法系列之九]Karatsuba快速相乘算法

比眉伴天荒 2023-05-31 10:22 6阅读 0赞

### 【概述】 ###

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;
    }

本文原文地址：[https://blog.csdn.net/SunnyYoona/article/details/43234889][https_blog.csdn.net_SunnyYoona_article_details_43234889]

[https_blog.csdn.net_SunnyYoona_article_details_43234889]: https://blog.csdn.net/SunnyYoona/article/details/43234889