利用Python怎么實(shí)現(xiàn)一個(gè)大整數(shù)乘法算法？針對(duì)這個(gè)問題，這篇文章詳細(xì)介紹了相對(duì)應(yīng)的分析和解答，希望可以幫助更多想解決這個(gè)問題的小伙伴找到更簡(jiǎn)單易行的方法。

創(chuàng)新互聯(lián)公司專業(yè)為企業(yè)提供花垣網(wǎng)站建設(shè)、花垣做網(wǎng)站、花垣網(wǎng)站設(shè)計(jì)、花垣網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁(yè)設(shè)計(jì)與制作、花垣企業(yè)網(wǎng)站模板建站服務(wù)，10余年花垣做網(wǎng)站經(jīng)驗(yàn)，不只是建網(wǎng)站，更提供有價(jià)值的思路和整體網(wǎng)絡(luò)服務(wù)。

介紹原理

karatsuba 算法要求乘數(shù)與被乘數(shù)要滿足以下幾個(gè)條件，第一，乘數(shù)與被乘數(shù)的位數(shù)相同；第二，乘數(shù)與被乘數(shù)的位數(shù)應(yīng)為  2 次冪，即為 2 ^ 2,  2 ^ 3, 2 ^ 4， 2 ^ n 等數(shù)值。

下面我們先來看幾個(gè)簡(jiǎn)單的例子，并以此來了解 karatsuba 算法的使用方法。

兩位數(shù)相乘

我們?cè)O(shè)被乘數(shù) A = 85，乘數(shù) B = 41。下面來看我們的操作步驟：

將 A, B 一分為二，令 p = A 的前半部分 = 8，q = A 的后半部分 = 5 ， r = B 的前半部分 = 4 ，s = B 的后半部分 =  1，n = 2。通過簡(jiǎn)單的數(shù)學(xué)運(yùn)算：

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。

換成數(shù)值求解的過程如下：

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。與長(zhǎng)乘法所得結(jié)果一致。

四位數(shù)相乘

我們?cè)O(shè)被乘數(shù) A = 8537，乘數(shù) 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。

在我們計(jì)算 u， v,  w 的過程中又會(huì)涉及兩位數(shù)的乘法，我們繼續(xù)使用 Karatsuba 算法得出兩位數(shù)相乘的結(jié)果。

N 位數(shù)相乘

我們令 n 為 乘數(shù)與被乘數(shù)的位數(shù)，令 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 則是兩個(gè) n / 2 位的乘法運(yùn)算。我們繼續(xù)調(diào)用 Karatsuba 算法計(jì)算 u, v, w 的數(shù)值。接著，我們?cè)谟?jì)算 n / 2 乘法的過程中又會(huì)遇到 n / 4 位的乘法運(yùn)算……以此類推，直到我們遇到兩個(gè)個(gè)位數(shù)的乘法，我們就直接返回這兩個(gè)個(gè)位數(shù)乘法的結(jié)果。層層返回，最終得到 N 位數(shù)的乘法結(jié)果。

時(shí)間復(fù)雜度

我們平常使用的長(zhǎng)乘法，是 O (n ^ 2) 的時(shí)間復(fù)雜度。比如兩個(gè) N 位數(shù)相乘，我們需要將每一位按規(guī)則相乘，所以需要計(jì)算  N * N 次乘法。而使用  Karatsuba 算法每層需要計(jì)算三次乘法，兩次加法，以及若干次加法，每使用一次 karatsuba 算法，乘法規(guī)模就下降一半。

所以，對(duì)于兩個(gè) n =  2 ^ K 位數(shù)乘法運(yùn)算，我們需要計(jì)算 3 ^ k 次乘法運(yùn)算。而 K = log n(底數(shù)為 2)， 3 ^ K = 3 ^ log n = 2  ^ (log 3 * log n) = 2 ^ (log n * log 3) = n ^ log 3 （底數(shù)為 2）。

代碼實(shí)現(xiàn)

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

輸出結(jié)果：

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

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

關(guān)于利用Python怎么實(shí)現(xiàn)一個(gè)大整數(shù)乘法算法問題的解答就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道了解更多相關(guān)知識(shí)。

本文標(biāo)題：利用Python怎么實(shí)現(xiàn)一個(gè)大整數(shù)乘法算法-創(chuàng)新互聯(lián)
網(wǎng)址分享：http://jinyejixie.com/article10/dshjdo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信小程序、做網(wǎng)站、定制開發(fā)、商城網(wǎng)站、網(wǎng)站營(yíng)銷、App設(shè)計(jì)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)