作者：程序員小灰
來源：程序員小灰

前一段時間，小灰髮布了一篇有關大整數相加的漫畫，沒看過的小夥伴可以先看一看：

漫畫：如何實現大整數相加？（修訂版）

那麼，大整數相乘又是如何實現的呢？

起初，小灰認爲只要按照大整數相加的思路稍微做一下變形，就可以輕鬆實現大整數相乘。但是隨着深入的學習，小灰才發現事情並沒有那麼簡單......

————— 第二天 —————

怎樣列出這個乘法豎式呢？以 93281 X 2034 爲例，豎式如下：

在程序中，我們可以利用int型數組，把兩個大整數按位進行存儲，再把數組中的元素像小學豎式那樣逐個進行計算。

這個乘法豎式的計算過程可以大體分爲兩步：

1.整數B的每一個數位和整數A所有數位依次相乘，得到中間結果。

2.所有中間結果相加，得到最終結果。

————————————

下面，我們的推導會有一些燒腦，請大家坐穩扶好~~

大整數從高位到低位，被平分成了兩部分。設整數1的高位部分是A，低位部分是B；整數2的高位部分是C，低位部分是D，那麼有如下等式：

如果把大整數的長度抽象爲n，那麼：

因此，整數1與整數2 的乘積可以寫成下面的形式：

如此一來，原本長度爲n的大整數的1次乘積，被轉化成了長度爲n/2的大整數的4次乘積（AC，AD，BC，BD）。

什麼是master定理呢？

master定理的英語名稱是master theorem，它爲許多由分治法得到的遞推關係式提供了漸進時間複雜度分析。

設常數a >= 1，b > 1，如果一個算法的整體計算規模 T(n) = a T(n / b) + f(n)，那麼則有如下規律：

假設兩個長度爲n的大整數相乘，整體運算規模是T(n) 。

根據剛纔得到的結論，兩個大整數相乘被拆分成四個較小的乘積：

所以在第一次分治時，T(n)和T(n/2)有如下關係：

T(n) = 4T(n/2) + f(n)

其中f(n)是4個乘積結果相加的運算規模，f(n)的漸進時間複雜度很明顯是O(n)。

把這個關係帶入到master定理的公式 T(n) = a T(n / b) + f(n) 當中，

此時 a=4， b=2。

此時，把a和b的值，以及f(n)的時間複雜度帶入到master定理的第一個規律，也就是下面的規律：

發現正好符合條件。

怎麼符合呢？推導過程如下：

所以我們的平均時間複雜度是：

如何做調整呢？其實很簡單，連小學生都會：

這樣一來，原本的4次乘法和3次加法，轉變成了3次乘法和6次加法。

這樣一來，時間複雜度是多少呢？

假設兩個長度爲n的大整數相乘，整體運算規模是T(n) 。

剛纔我們說過，兩個大整數相乘可以被拆分成三個較小的乘積，

所以在第一次分治時，T(n)和T(n/2)有如下關係：

T(n) = 3T(n/2) + f(n)

其中f(n)是6次加法的運算規模，f(n)的漸進時間複雜度很明顯是O(n)。

此時讓我們回顧一下master定理：

設常數a >= 1，b > 1，如果一個算法的整體計算規模 T(n) = a T(n / b) + f(n)，那麼則有如下規律：

對於T(n) = 3T(n/2) + f(n)這個關係式來說， a=3， b=2。

把a和b的值，以及f(n)的時間複雜度帶入到master定理的第一個規律，也就是下面的規律：

發現正好符合條件。

怎麼符合條件呢？推導過程如下：

所以我們的平均時間複雜度是：

2 和 1.59 之間的差距看似不大，但是當整數長度非常大的時候，兩種方法的性能將是天壤之別。

下面展示一下實現代碼。我們的代碼非常複雜，在這裏只作爲參考，最重要的還是解決問題的思路：

需要注意的是，這段實現代碼只適用於兩個大整數長度相等的情況。如果想求解長度不等的整數相乘，只需要對代碼做微小的改動，有興趣的小夥伴沒有試一試。

幾點補充：

1. 文章最後的代碼，經由網上技術博客的代碼改動而來，僅做參考。

2. 關於快速傅里葉變換，有興趣深入研究的小夥伴們可以參考《算法導論》第30章的內容。