亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

Python 實現大整數乘法算法

系統 2194 0

我們平時接觸的長乘法,按位相乘,是一種時間復雜度為 O(n ^ 2) 的算法。今天,我們來介紹一種時間復雜度為 O (n ^ log 3) 的大整數乘法(log 表示以 2 為底的對數)。

介紹原理

karatsuba 算法要求乘數與被乘數要滿足以下幾個條件,第一,乘數與被乘數的位數相同; 第二,乘數與被乘數的位數應為 ?2 次冪,即為 2 ^ 2, ?2 ^ 3, 2 ^ 4, 2 ^ n 等數值。

下面我們先來看幾個簡單的例子,并以此來了解 karatsuba 算法的使用方法。

兩位數相乘

我們設被乘數 A = 85,乘數 B = 41。 下面來看我們的操作步驟:

將 A, B 一分為二,令 p = A 的前半部分 = 8,q = A 的后半部分 = 5 , r = B 的前半部分 = 4 ,s = B 的后半部分 = ?1,n = 2。 通過簡單的數學運算:

A * B = pq * rs? = (p * 10 + q) * (r * 10 + s) ?=? p * r * 10 ^ 2 + (p * s + q * r ) * 10 + q * s。

令 u = p * r,v = (p - q) * (s - r),w = q * s。所以 A * B = ?u * 10 ^ 2 + (u + v + w) * 10 + w。

換成數值求解的過程如下:

A * B = 85 * 41 = (8 * 10 + 5) * ( 4 * 10 + 1) = 8 * 4 * 10 * 10 + (8 * 1 + 5 * 4) * 10 + 5 * 1。

其中 u = 8 * 4 = 32,v = (8 - 5) (1 - 4) = -9,w = 5 * 1 = 5。

所以,A * B = 32 * 100 + (32 - 9 + 5) * 10 + 5 = 3485。 與長乘法所得結果一致。

四位數相乘

我們設被乘數 A = 8537,乘數 B = 4123。 下面來看我們的操作步驟:

將 A, B 一分為二,令 p = A 的前半部分 = 85,q = A 的后半部分 = 37 , r = B 的前半部分 = 41 ,s = B 的后半部分 = ?23,n = 4。

==> 其中,u = 85 * 41, v = (85 - 37) * (23 - 41), w = 37 * 23。

==> A * B = 8537 * 4123 = u * 10 ^ 4 + (u + v + w) * 10 ^ 2 + w = ?3485_0000 +34_7200 + 851 = 35198051。

在我們計算 u, v, ?w 的過程中又會涉及兩位數的乘法,我們繼續使用 Karatsuba 算法得出兩位數相乘的結果。

N 位數相乘

我們令 n 為 乘數與被乘數的位數,令 p = A 的前半部分,q = A 的后半部分, r = B 的前半部分 ,s = B 的后半部分。

==> 其中, u = p * r,v = (p - q) * (s - r),w = q * s。

所以 A * B = ?u * 10 ^ n + (u + v + w) * 10 ^ (n / 2) + w。

而 u, v, w 則是兩個 n / 2 位的乘法運算。 我們繼續調用 Karatsuba 算法計算 u, v, w 的數值。 接著,我們在計算 n / 2 乘法的過程中又會遇到 n / 4 位的乘法運算……以此類推,直到我們遇到兩個個位數的乘法,我們就直接返回這兩個個位數乘法的結果。 層層返回,最終得到 N 位數的乘法結果。

時間復雜度

我們平常使用的長乘法,是 O (n ^ 2) 的時間復雜度。 比如兩個 N 位數相乘,我們需要將每一位按規則相乘,所以需要計算 ?N * N 次乘法。 而使用 ?Karatsuba 算法每層需要計算三次乘法,兩次加法,以及若干次加法,每使用一次 karatsuba 算法,乘法規模就下降一半。

所以,對于兩個 n = ?2 ^ K 位數乘法運算,我們需要計算 3 ^ k 次乘法運算。 而 K = log n(底數為 2), 3 ^ K = 3 ^ log n = 2 ?^ (log 3 * log n) = 2 ^ (log n * log 3) = n ^ log 3 (底數為 2)。

代碼實現

                
                  from?math?import?log2,?ceil

def?pad(string:?str,?real_len:?int,?max_len:?int)?->?str:
????pad_len:?int?=?max_len?-?real_len
????return?f"{'0'?*?pad_len}{string}"


def?kara(n1:?int,?n2:?int)?->?int:
????if?n1?<?10?or?n2?<?10:
????????return?n1?*?n2
????n1_str:?str?=?str(n1)
????n2_str:?str?=?str(n2)
????n1_len:?int?=?len(n1_str)
????n2_len:?int?=?len(n2_str)
????real_len:?int?=?max(n1_len,?n2_len)
????max_len:?int?=?2?**?ceil(log2(real_len))
????mid_len:?int?=?max_len?>>?1
????n1_pad:?str?=?pad(n1_str,?n1_len,?max_len)
????n2_pad:?str?=?pad(n2_str,?n2_len,?max_len)
????p:?int?=?int(n1_pad[:mid_len])
????q:?int?=?int(n1_pad[mid_len:])
????r:?int?=?int(n2_pad[:mid_len])
????s:?int?=?int(n2_pad[mid_len:])
????u:?int?=?kara(p,?r)
????v:?int?=?kara(q-p,?r-s)
????w:?int?=?kara(q,?s)
????return?u?*?10?**?max_len?+?(u+v+w)?*?10?**?mid_len?+?w

                
              

輸出結果:

==> kara(123456, 9734) == 123456 * 9734

==> kara(1234233456756, 32459734) == 1234233456756 * 32459734


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!??!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 五月天婷婷在线视频 | 欧美成人爽毛片在线视频 | 四虎永久免费网站免费观看 | 一级女人18毛片免费 | 国产成人免费观看在线视频 | 久久精品国产波多野结衣 | 伊人久久大香线焦综合四虎 | 99热成人精品热久久66 | 久久综合给合久久狠狠狠色97 | 毛片机地 | 久青草视频在线 | 99免费观看视频 | 一级毛片一级毛片a毛片欧美 | 日韩高清中文字幕 | 国产精品久久久久久免费播放 | 久久综合图区亚洲综合图区 | 亚洲午夜网 | 激情五月综合综合久久69 | 日日搞夜夜操 | 久久国产精品免费看 | 亚洲精品国产字幕久久不卡 | 亚洲综合一 | 97影院理论午夜论不卡 | 欧美一区二区三区综合色视频 | 四虎a级欧美在线观看 | 久操视频免费 | 9久re热视频这里只有精品 | 黄色毛片a | 黄色片网站观看 | 色综合网亚洲精品久久 | 欧做爰xxxⅹ性欧美大片孕妇 | 成人18免费网站 | 亚洲精品久久久久久小说 | 影音先锋在线亚洲精品推荐 | 日韩 欧美 亚洲 国产 | 亚洲国产精品一区二区久久 | 精品一区二区久久久久久久网站 | 三级a做爰大乳在线观看 | 久青草视频在线 | 无遮挡一级毛片视频 | 深夜视频免费看 |