Python的大數運算到底是根據什麼基礎原理或者演算法實現的？

01-07

曾經隨機生成了兩個兩萬位的數，然後進行乘法運算，結果也是秒出。linux下面的bc相比起來簡直是弱渣。
我做過加法器和CPU，但感覺單純的靠CPU和乘加法器，還要對大數進行拆分處理，假如沒有演算法的優化的話，無論如何也不可能做到這麼快啊。
如果原理很複雜的話，有沒有相關論文，我自己去看也可以。
不想看源碼。。我也知道實在想用的話可以直接用C++去調用python腳本。。但想深入理解一下原理。。。。

私以為FFT求循環卷積得大數乘可以解釋。回頭我再看看源碼再來分析，有點兒不太記得了……

Naive (grade school) multiplication has a running time of O(n^2).

Python uses Karatsuba multiplication whose running time is O(n^1.585).

Karatsuba Multiplication Algorithm

Also, a combination of Karatsuba, Toom-Cook, and Nussbaumer convolution can be used to get a running time of O(n*ln(n)).

======================

Python 為什麼使用「複雜度更高」的Karatsuba Multiplication而不是大家常念叨的O(nlogn)的FFT大法？

(1)

In practice the Sch?nhage–Strassen algorithm starts to outperform
older methods such as Karatsuba and Toom–Cook multiplication for
numbers beyond 2**2**15 to 2**2**17 (10,000 to 40,000 decimal digits). [1]

(2) 講道理的話，python使用者用的「大數」哪裡會超過10000位。。。

[1] Sch?nhage

=======================

Karatsuba Multiplication的源碼？

yes, talk is cheap, plz search it (python) on github. [2]

其實可以看到，當其中任意一個數的位數很少的時候，python是用樸素乘法的。。。

這說明樸素乘法在該情況下更快。。

[2] cpython/longobject.c at master · python/cpython · GitHub

=======================

Karatsuba Multiplication什麼時候加進python的？

2002年 [3]

[3] Issue 560379: Karatsuba multiplication

=======================

既然當位數很少的時候，Python用更快的樸素乘法，那為什麼不加一個判斷條件，當位數超級多的時候用FFT這種方法？

I"m far from sure that such a patch would be accepted. Indeed,
Tim Peters has been heard to mention that if he were to do it all
again, he probably wouldn"t even have implemented Karatsuba [4].
Asymptotically fast integer multiplication is a specialist need that"s
already available in 3rd-party Python libraries (gmpy). IMO, it"s not
appropriate to include it in a general-purpose programming language,
and the burden of maintaining such code would outweigh the benefits.

One thing that has been considered in the past is making it possible
to use GMP directly for Python"s implementation of long integers; see
Victor Stinner"s efforts in this direction [5]. Licensing concerns,
and the fact that Python"s implementation is faster for small
integers, ended up killing this issue.

[4] [Python-Dev] Optionally using GMP to implement long if available

[5] Issue 1814: Victor Stinner"s GMP patch for longs

=======================

Karatsuba演算法的思想？複雜度怎麼算的。。

分治，其實貼的鏈接裡面提得挺多的了。。下面簡單描述一下。

要算 $x imes y$ ，假設它們都是n位數。。把x和y都拆成2個n/2的部分 $x=overline{ab}, y=overline{cd}$ 。

普通的演算法是計算 $a imes c, a imes d,b imes c,b imes d$ ，這樣1次size為n的大數乘法變成 4次size為n/2的大數乘法加上1次size為n/2的大數加法，這樣得到的複雜度遞推式是 $T(n)=4T(n/2)+Theta(n/2)$ ，然後解這個遞推式子得到複雜度 $Theta(n^2)$ 。

然而，其實我們只要求 $a imes d+b imes c$ 而不必分別求它們，而且我們發現 $b imes c+a imes d=(a+b) imes(c+d)-a imes c-b imes d$ ，這樣1次size為n的大數乘法就變成了 3次size為n/2的大數乘法加上3次size為n/2的大數加法（減法也當作加法），這樣得到的複雜度遞推式為 $T(n)=3T(n/2)+3Theta(n/2)$ ，使用主方法解這個遞推式得到複雜度 $Theta(n^{log_23})$ 。

========================

a combination of Karatsuba, Toom-Cook, and Nussbaumer convolution是什麼？怎麼combine？

不知道。這句話是GMP [6]的作者寫的。有興趣可以去看GMP的實現。:)

[6] The GNU MP Bignum Library

加減不知道，乘法有快速傅里葉變換啊，複雜度從樸素O(N^2)優化到O(NlogN)。