化，掌握大數(shù)運(yùn)算核心)
1. 從“算不過來”到“算得精確”高精度乘法的現(xiàn)實(shí)需求在編程和算法競(jìng)賽的日常里我們經(jīng)常和整數(shù)打交道。大多數(shù)時(shí)候int或long long類型就能滿足需求畢竟它們能表示的數(shù)已經(jīng)相當(dāng)大了。但總有一些場(chǎng)景比如計(jì)算大數(shù)的階乘、處理超長整數(shù)的加密解密、或者模擬天體物理中的巨大數(shù)值時(shí)常規(guī)的整數(shù)類型會(huì)立刻“啞火”——它們溢出了。你可能會(huì)想不是有Python這種天生支持大整數(shù)的語言嗎確實(shí)如此但理解其背后的原理尤其是在C、Java等語言中如何手動(dòng)實(shí)現(xiàn)是深入理解計(jì)算機(jī)如何處理“無限”精度數(shù)據(jù)的關(guān)鍵。這就是高精度算法的用武之地而乘法作為四則運(yùn)算中最復(fù)雜的一環(huán)其高精度實(shí)現(xiàn)更是核心中的核心。簡(jiǎn)單來說高精度乘法就是模擬我們小學(xué)時(shí)學(xué)的豎式乘法但對(duì)象是每一位數(shù)字都存儲(chǔ)在數(shù)組里的“大數(shù)”。它不依賴語言內(nèi)置的大整數(shù)庫而是通過最基礎(chǔ)的數(shù)組操作實(shí)現(xiàn)任意長度整數(shù)的精確相乘。這不僅是算法競(jìng)賽的?？透抢斫庥?jì)算機(jī)底層數(shù)值計(jì)算、鍛煉嚴(yán)謹(jǐn)編程思維的絕佳練習(xí)。今天我們就拋開那些現(xiàn)成的庫從頭到尾把高精度乘法的原理、實(shí)現(xiàn)、優(yōu)化以及那些容易踩的坑掰開揉碎了講清楚。2. 基石如何用數(shù)組表示一個(gè)“大數(shù)”在實(shí)現(xiàn)任何高精度運(yùn)算之前我們首先要解決一個(gè)根本問題如何在計(jì)算機(jī)中表示一個(gè)遠(yuǎn)超內(nèi)置類型范圍的整數(shù)答案就是用數(shù)組確切地說是用數(shù)組的每一個(gè)元素來存儲(chǔ)大數(shù)的一位。2.1 存儲(chǔ)格式的選擇順位存儲(chǔ) vs. 倒位存儲(chǔ)這里有兩個(gè)主流的選擇它們各有優(yōu)劣。方案一順位存儲(chǔ)即數(shù)組下標(biāo)0存儲(chǔ)最高位下標(biāo)n-1存儲(chǔ)最低位。這很符合人類的閱讀習(xí)慣。但是當(dāng)你進(jìn)行運(yùn)算時(shí)尤其是涉及進(jìn)位操作時(shí)問題就來了。乘法或加法中進(jìn)位是從最低位向最高位傳遞的。如果最低位在數(shù)組末尾那么處理進(jìn)位時(shí)你可能需要在數(shù)組頭部進(jìn)行插入操作這在數(shù)組中是非常低效的需要移動(dòng)大量元素。方案二倒位存儲(chǔ)推薦這是實(shí)踐中幾乎無一例外采用的方法。我們讓數(shù)組下標(biāo)0存儲(chǔ)個(gè)位最低位下標(biāo)1存儲(chǔ)十位以此類推。這樣做有兩大好處進(jìn)位處理高效運(yùn)算從低位開始產(chǎn)生的進(jìn)位可以自然地向更高下標(biāo)即更高位累加完全符合計(jì)算過程無需移動(dòng)數(shù)組元素。長度擴(kuò)展方便如果結(jié)果位數(shù)比原數(shù)多我們只需要在數(shù)組末尾更高下標(biāo)追加新的元素即可。例如數(shù)字12345用倒位存儲(chǔ)的數(shù)組A表示就是A[0] 5,A[1] 4,A[2] 3,A[3] 2,A[4] 1。輸出時(shí)我們只需要從最高位數(shù)組最后一個(gè)有效元素倒序輸出即可。注意在代碼中我們通常使用vectorint或普通數(shù)組來存儲(chǔ)并維護(hù)一個(gè)變量表示當(dāng)前數(shù)字的長度有效位數(shù)以避免處理前導(dǎo)零。2.2 輸入與輸出的處理由于數(shù)字可能非常大我們無法用int直接讀入。標(biāo)準(zhǔn)的做法是先用字符串string或char[]讀入這個(gè)數(shù)字然后再將其轉(zhuǎn)換為倒位存儲(chǔ)的數(shù)組。string str_num 12345678901234567890; vectorint A; for (int i str_num.size() - 1; i 0; i--) { A.push_back(str_num[i] - 0); // 字符轉(zhuǎn)數(shù)字并倒序存入 } // 此時(shí) A [0,9,8,7,6,5,4,3,2,1,0,9,8,7,6,5,4,3,2,1]輸出時(shí)同樣需要倒序for (int i A.size() - 1; i 0; i--) { cout A[i]; }3. 核心算法拆解模擬豎式乘法的每一步高精度乘法的本質(zhì)就是模擬我們熟悉的豎式計(jì)算。假設(shè)我們要計(jì)算A * B其中A和B都是高精度數(shù)倒位存儲(chǔ)的數(shù)組。我們來看最基礎(chǔ)、最直觀的算法實(shí)現(xiàn)。3.1 算法流程與手動(dòng)模擬設(shè)A有n位B有m位。我們知道A * B的結(jié)果最多有n m位。計(jì)算過程創(chuàng)建一個(gè)結(jié)果數(shù)組C初始長度設(shè)為n m所有位初始化為0。用B的每一位B[j]j從0到m-1去乘以整個(gè)A。對(duì)于每一對(duì)A[i]和B[j]計(jì)算其乘積temp A[i] * B[j]。將這個(gè)乘積temp加到結(jié)果數(shù)組C的正確位置上。這個(gè)位置是C[i j]。為什么是i j因?yàn)锳[i]是A的第i位實(shí)際代表A[i] * 10^iB[j]是B的第j位代表B[j] * 10^j它們相乘的結(jié)果對(duì)最終結(jié)果的貢獻(xiàn)位是10^(ij)對(duì)應(yīng)數(shù)組下標(biāo)就是i j。處理加法帶來的進(jìn)位。由于temp可能是一個(gè)兩位數(shù)最大9*981加上C[ij]原有的值后可能會(huì)產(chǎn)生進(jìn)位這個(gè)進(jìn)位需要向高位C[ij1]累加。遍歷完所有i和j后C中存儲(chǔ)的就是結(jié)果但可能包含前導(dǎo)零。我們需要從最高位開始移除這些無意義的前導(dǎo)零得到最終的有效結(jié)果。讓我們手動(dòng)模擬一個(gè)小例子123 * 45。A [3, 2, 1] (123)B [5, 4] (45)初始化 C [0, 0, 0, 0, 0] (長度 325)第一輪j0 (B[0]5)i0: temp A[0]B[0] 3515。 C[00] 15 - C[0]15。進(jìn)位C[0]留5向C[1]進(jìn)1。i1: temp 2*510。 C[10] 10 - C[1]101(進(jìn)位)11。進(jìn)位C[1]留1向C[2]進(jìn)1。i2: temp 1*55。 C[20] 5 - C[2]51(進(jìn)位)6。進(jìn)位C[2]6無進(jìn)位。 此輪后C [5, 1, 6, 0, 0]第二輪j1 (B[1]4)i0: temp 3*412。 C[01] 12 - C[1]11213。進(jìn)位C[1]留3向C[2]進(jìn)1。i1: temp 2*48。 C[11] 8 - C[2]681(進(jìn)位)15。進(jìn)位C[2]留5向C[3]進(jìn)1。i2: temp 1*44。 C[21] 4 - C[3]041(進(jìn)位)5。進(jìn)位C[3]5無進(jìn)位。 此輪后C [5, 3, 5, 5, 0]最終處理從最高位C[4]開始檢查C[4]0 是前導(dǎo)零移除。得到最終數(shù)組 [5, 3, 5, 5]倒序輸出為5535正是123 * 45的結(jié)果。3.2 基礎(chǔ)代碼實(shí)現(xiàn)樸素算法根據(jù)上述流程我們可以寫出最樸素的代碼。這里以 C 為例使用vectorint存儲(chǔ)大數(shù)。#include iostream #include vector #include string using namespace std; // 高精度乘法 (樸素算法) vectorint multiply_naive(const vectorint A, const vectorint B) { int n A.size(), m B.size(); // 結(jié)果最多有 nm 位 vectorint C(n m, 0); // 核心計(jì)算部分 for (int i 0; i n; i) { for (int j 0; j m; j) { C[i j] A[i] * B[j]; // 立即處理進(jìn)位防止單一位存儲(chǔ)的數(shù)字過大 C[i j 1] C[i j] / 10; C[i j] % 10; } } // 處理最后一輪的進(jìn)位實(shí)際上上面的循環(huán)內(nèi)處理了大部分但最高位可能還有進(jìn)位 // 更穩(wěn)妥的做法是再統(tǒng)一處理一次所有位的進(jìn)位 // 但通常內(nèi)循環(huán)中即時(shí)處理已足夠這里為了清晰展示另一種統(tǒng)一處理的方式 // 我們可以在計(jì)算完所有乘積后再統(tǒng)一處理進(jìn)位 // vectorint C(n m, 0); // for (int i 0; i n; i) // for (int j 0; j m; j) // C[i j] A[i] * B[j]; // 先只累加不處理進(jìn)位 // // 統(tǒng)一處理進(jìn)位 // int carry 0; // for (int i 0; i C.size(); i) { // C[i] carry; // carry C[i] / 10; // C[i] % 10; // } // 移除前導(dǎo)零 while (C.size() 1 C.back() 0) { C.pop_back(); } return C; } // 輔助函數(shù)將字符串轉(zhuǎn)換為倒位存儲(chǔ)的vector vectorint str_to_vec(const string s) { vectorint res; for (int i s.size() - 1; i 0; i--) { res.push_back(s[i] - 0); } // 如果輸入是0確保結(jié)果不是空vector if (res.empty()) res.push_back(0); return res; } // 輔助函數(shù)輸出高精度數(shù) void print_vec(const vectorint num) { for (int i num.size() - 1; i 0; i--) { cout num[i]; } cout endl; } int main() { string s1, s2; // 假設(shè)輸入兩個(gè)大數(shù)字符串 s1 123456789; s2 987654321; vectorint A str_to_vec(s1); vectorint B str_to_vec(s2); vectorint C multiply_naive(A, B); cout s1 * s2 ; print_vec(C); // 應(yīng)輸出 121932631112635269 return 0; }這段代碼清晰地展示了高精度乘法的核心思想。它的時(shí)間復(fù)雜度是 O(nm)對(duì)于兩個(gè) n 位和 m 位的數(shù)需要進(jìn)行 nm 次單位數(shù)乘法和加法。4. 性能瓶頸與優(yōu)化從 O(n2) 到更快的算法樸素算法雖然正確但在面對(duì)位數(shù)非常多比如幾十萬位的大數(shù)時(shí)O(n2) 的復(fù)雜度會(huì)成為嚴(yán)重的性能瓶頸。在實(shí)際應(yīng)用和算法競(jìng)賽中我們需要更高效的算法。4.1 為什么樸素算法慢根本原因在于它模擬的是最基礎(chǔ)的豎式乘法每一位都需要和另一個(gè)數(shù)的每一位相乘。當(dāng)位數(shù)增加時(shí)計(jì)算量呈平方級(jí)增長。例如兩個(gè) 10000 位的數(shù)相乘需要進(jìn)行約 1 億次單位數(shù)乘法和加法。4.2 優(yōu)化方向一壓位存儲(chǔ)我們之前是一位數(shù)組元素存一個(gè)十進(jìn)制數(shù)字0-9。這其實(shí)浪費(fèi)了int類型的存儲(chǔ)空間。一個(gè)int通常能存儲(chǔ)高達(dá)約20億的數(shù)我們完全可以利用它來存儲(chǔ)多位十進(jìn)制數(shù)這就是壓位。常見的壓位方式萬進(jìn)制壓位每個(gè)數(shù)組元素存儲(chǔ) 4 位十進(jìn)制數(shù)范圍 0-9999。因?yàn)?10000 * 10000 100000000仍在int的安全范圍內(nèi)小于21億且進(jìn)位處理方便。億進(jìn)制壓位每個(gè)數(shù)組元素存儲(chǔ) 8 位十進(jìn)制數(shù)范圍 0-99999999。這要求使用long long或int64_t類型存儲(chǔ)因?yàn)?100000000 * 100000000 會(huì)超過int范圍。億進(jìn)制能進(jìn)一步減少循環(huán)次數(shù)。壓位帶來的改變輸入輸出需要按“塊”來解析和輸出字符串。乘法計(jì)算核心邏輯不變但每次乘法的對(duì)象變成了“塊”一個(gè)多位整數(shù)乘法的結(jié)果可能很大需要更仔細(xì)地處理進(jìn)位。進(jìn)位基數(shù)從 10 變成了 10000萬進(jìn)制或 100000000億進(jìn)制。萬進(jìn)制壓位乘法示例偽代碼思路// 假設(shè) A, B 已是萬進(jìn)制倒位存儲(chǔ)的vectorint vectorint multiply_compressed(const vectorint A, const vectorint B) { int n A.size(), m B.size(); vectorlong long C(n m, 0); // 使用long long防止中間結(jié)果溢出 const int BASE 10000; for (int i 0; i n; i) { for (int j 0; j m; j) { C[i j] (long long)A[i] * B[j]; // 這里可以延遲處理進(jìn)位 } } // 統(tǒng)一處理進(jìn)位 long long carry 0; for (int i 0; i C.size(); i) { C[i] carry; carry C[i] / BASE; C[i] % BASE; } // 移除前導(dǎo)零整個(gè)塊為0 while (C.size() 1 C.back() 0) C.pop_back(); // 將C從long long轉(zhuǎn)回int (如果值在int范圍內(nèi)) vectorint res(C.begin(), C.end()); return res; }壓位能將計(jì)算量減少到原來的 1/4 或 1/8常數(shù)級(jí)優(yōu)化顯著代碼復(fù)雜度增加不多是競(jìng)賽和實(shí)踐中必用的優(yōu)化手段。4.3 優(yōu)化方向二分治算法FFT與NTT當(dāng)位數(shù)達(dá)到十萬甚至百萬級(jí)時(shí)即使是壓位優(yōu)化的 O(n2) 算法也力不從心。這時(shí)就需要時(shí)間復(fù)雜度更低的算法它們基于“分治”思想。基本原理將大數(shù)乘法轉(zhuǎn)化為多項(xiàng)式乘法。一個(gè) n 位十進(jìn)制數(shù)可以看作一個(gè)以 10 為基的多項(xiàng)式。兩個(gè)多項(xiàng)式相乘樸素也是 O(n2)但利用快速傅里葉變換FFT或數(shù)論變換NTT可以在 O(n log n) 時(shí)間內(nèi)完成。FFT/NTT 乘法步驟系數(shù)表示將兩個(gè)大數(shù) A 和 B 視為多項(xiàng)式的系數(shù)倒位存儲(chǔ)的數(shù)組本身就是系數(shù)。點(diǎn)值表示利用 FFT/NTT將兩個(gè)多項(xiàng)式的系數(shù)表示快速轉(zhuǎn)換為在特定點(diǎn)集上的值點(diǎn)值表示。這個(gè)過程是 O(n log n)。點(diǎn)值相乘將兩個(gè)多項(xiàng)式在相同點(diǎn)上的值一一對(duì)應(yīng)相乘得到結(jié)果多項(xiàng)式的點(diǎn)值表示。這是 O(n)。插值利用逆 FFT/NTT將結(jié)果多項(xiàng)式的點(diǎn)值表示快速轉(zhuǎn)換回系數(shù)表示。這個(gè)過程也是 O(n log n)。進(jìn)位處理得到的系數(shù)數(shù)組是多項(xiàng)式乘法的結(jié)果但每一位可能遠(yuǎn)大于進(jìn)制基數(shù)比如10或10000需要像普通高精度一樣進(jìn)行統(tǒng)一的進(jìn)位處理。為什么有效FFT/NTT 巧妙地利用了復(fù)數(shù)的單位根或數(shù)論原根的性質(zhì)將多項(xiàng)式系數(shù)與點(diǎn)值之間的轉(zhuǎn)換復(fù)雜度從 O(n2) 降到了 O(n log n)從而大幅加速了乘法的核心步驟。實(shí)現(xiàn)考量FFT使用復(fù)數(shù)運(yùn)算有精度誤差對(duì)于極大的整數(shù)可能需要多次變換或調(diào)整參數(shù)來保證精度。NTT在模素?cái)?shù)下進(jìn)行無精度誤差結(jié)果精確但要求模素?cái)?shù) P 滿足某些性質(zhì)如 P c * 2^k 1且數(shù)值不能超過 P。通常需要多次 NTT 配合中國剩余定理CRT來還原大數(shù)。應(yīng)用場(chǎng)景在算法競(jìng)賽中當(dāng) n 超過 5000~10000 時(shí)FFT/NTT 的優(yōu)勢(shì)就開始體現(xiàn)。許多標(biāo)準(zhǔn)的高精度乘法庫如 GMP在底層就使用了這些算法。實(shí)操心得對(duì)于絕大多數(shù)日常應(yīng)用和競(jìng)賽題目掌握壓位高精度乘法已經(jīng)完全足夠。FFT/NTT 屬于“屠龍技”在需要處理極端大數(shù)據(jù)時(shí)才會(huì)用到。建議先精通樸素和壓位算法理解其每一個(gè)細(xì)節(jié)再在有余力時(shí)去研究分治算法。直接上手 FFT 容易陷入實(shí)現(xiàn)細(xì)節(jié)而忽略了高精度本身的數(shù)據(jù)處理邏輯。5. 實(shí)戰(zhàn)中的細(xì)節(jié)、陷阱與經(jīng)驗(yàn)分享理解了原理和算法真正動(dòng)手實(shí)現(xiàn)時(shí)還有很多細(xì)節(jié)決定成敗。下面是我在多次實(shí)現(xiàn)和使用高精度乘法中積累的一些經(jīng)驗(yàn)。5.1 前導(dǎo)零的處理這是一個(gè)非常常見且容易忽略的 bug 來源。在乘法完成后結(jié)果數(shù)組C的長度是預(yù)分配的nm但實(shí)際有效位數(shù)可能小于這個(gè)值。例如100 * 0 000我們需要把前面的兩個(gè)0去掉只保留一個(gè)0。處理技巧在輸出或返回結(jié)果前一定要從最高位數(shù)組末尾向前檢查移除所有連續(xù)的0直到遇到非零數(shù)字或只剩下一位保證結(jié)果為0時(shí)能正確輸出0。在壓位存儲(chǔ)中前導(dǎo)零是整個(gè)“塊”為0判斷條件是C.back() 0。5.2 進(jìn)位的處理時(shí)機(jī)在樸素算法的代碼示例中我展示了兩種處理進(jìn)位的方式即時(shí)處理在內(nèi)層循環(huán)中每次累加后立即處理當(dāng)前位的進(jìn)位。這樣做邏輯清晰不容易出錯(cuò)且單一位的數(shù)字不會(huì)太大。統(tǒng)一處理先完成所有A[i]*B[j]的累加讓C中的每一位可能遠(yuǎn)大于 9或壓位的基數(shù)然后再用一個(gè)單獨(dú)的循環(huán)統(tǒng)一處理所有位的進(jìn)位。經(jīng)驗(yàn)之談對(duì)于新手推薦使用統(tǒng)一處理。原因如下邏輯更分離乘法累加和進(jìn)位處理兩個(gè)步驟涇渭分明便于調(diào)試。性能影響微乎其微對(duì)于 O(n2) 算法多一次 O(n) 的遍歷開銷幾乎可以忽略。在壓位和 FFT 算法中由于中間結(jié)果可能非常大統(tǒng)一處理進(jìn)位幾乎是唯一的選擇。統(tǒng)一處理的代碼模式非常固定建議背下來int carry 0; for (int i 0; i C.size(); i) { C[i] carry; carry C[i] / BASE; // BASE是進(jìn)制十進(jìn)制為10萬進(jìn)制為10000 C[i] % BASE; } // 處理最高位可能的額外進(jìn)位 while (carry) { C.push_back(carry % BASE); carry / BASE; }5.3 負(fù)數(shù)的處理高精度運(yùn)算通常也支持負(fù)數(shù)。常見的處理方式是單獨(dú)存儲(chǔ)符號(hào)位。定義結(jié)構(gòu)體BigInt包含一個(gè)bool sign正為false負(fù)為true和一個(gè)vectorint存儲(chǔ)絕對(duì)值。乘法規(guī)則sign_C sign_A ^ sign_B異或同號(hào)得正異號(hào)得負(fù)。在實(shí)現(xiàn)乘法函數(shù)時(shí)先取兩數(shù)的絕對(duì)值進(jìn)行計(jì)算得到結(jié)果的絕對(duì)值最后再附上計(jì)算出的符號(hào)。特別注意-0應(yīng)該規(guī)范化為0即當(dāng)結(jié)果為0時(shí)無論符號(hào)是什么都強(qiáng)制將符號(hào)設(shè)為正。5.4 與加、減、除、模運(yùn)算的協(xié)作高精度乘法很少孤立使用它通常是一個(gè)完整大整數(shù)類的一部分。在設(shè)計(jì)時(shí)需要考慮與其他運(yùn)算的兼容性。存儲(chǔ)一致性確保所有運(yùn)算都使用同一種存儲(chǔ)格式如倒位存儲(chǔ)、萬進(jìn)制壓位。函數(shù)接口設(shè)計(jì)清晰的接口如BigInt operator*(const BigInt rhs) const。性能權(quán)衡在實(shí)現(xiàn)除法時(shí)可能會(huì)調(diào)用乘法例如在試商時(shí)。如果乘法非常快比如用了FFT可以提升除法的整體性能。5.5 測(cè)試策略高精度代碼極易出錯(cuò)必須有完善的測(cè)試。邊界測(cè)試測(cè)試0、1、10等特殊數(shù)字。隨機(jī)測(cè)試生成大量隨機(jī)的大整數(shù)對(duì)用你的高精度乘法計(jì)算結(jié)果同時(shí)用 Python 等支持大整數(shù)的語言計(jì)算相同算式對(duì)比結(jié)果是否一致。這是最有效的測(cè)試方法。壓力測(cè)試測(cè)試兩個(gè)位數(shù)很多如幾千位的數(shù)相乘檢查時(shí)間和結(jié)果是否正確。符號(hào)測(cè)試測(cè)試正數(shù)、負(fù)數(shù)、零之間的各種組合。6. 從理論到應(yīng)用高精度乘法的典型場(chǎng)景掌握了實(shí)現(xiàn)我們來看看高精度乘法具體用在哪兒。這能幫你更好地理解它的價(jià)值。6.1 算法競(jìng)賽中的經(jīng)典問題階乘計(jì)算計(jì)算n!n的階乘。隨著 n 增大結(jié)果會(huì)迅速超出任何內(nèi)置類型的范圍。例如100!就有158位。這需要循環(huán)進(jìn)行高精度乘法。組合數(shù)計(jì)算計(jì)算 C(n, m) 時(shí)可能涉及大數(shù)的乘法和除法。斐波那契數(shù)列某些變體或極大下標(biāo)的斐波那契數(shù)。高精度冪運(yùn)算計(jì)算a^b其中a和b都可能很大需要通過快速冪算法結(jié)合高精度乘法來實(shí)現(xiàn)。大數(shù)進(jìn)制轉(zhuǎn)換將一個(gè)非常大的數(shù)從一種進(jìn)制轉(zhuǎn)換到另一種進(jìn)制過程中可能涉及高精度乘法和除法。6.2 實(shí)際工程與科研應(yīng)用密碼學(xué)RSA等公鑰加密算法涉及數(shù)百位甚至上千位大整數(shù)的乘、模冪運(yùn)算。雖然這些庫如OpenSSL, GMP使用更底層的優(yōu)化和匯編指令但原理相通。數(shù)值計(jì)算與仿真在天體物理、量子化學(xué)等領(lǐng)域模擬需要極高的數(shù)值精度遠(yuǎn)超雙精度浮點(diǎn)數(shù)的范圍這時(shí)就需要高精度算術(shù)庫。計(jì)算機(jī)代數(shù)系統(tǒng)如 Mathematica、Maple它們能進(jìn)行符號(hào)計(jì)算和任意精度數(shù)值計(jì)算底層離不開高效的高精度算法。分布式計(jì)算校驗(yàn)在一些分布式協(xié)議中可能會(huì)用到大數(shù)運(yùn)算來生成或驗(yàn)證全局唯一的ID或校驗(yàn)和。6.3 一個(gè)完整的實(shí)戰(zhàn)案例計(jì)算任意位數(shù)的斐波那契數(shù)讓我們用高精度乘法來實(shí)現(xiàn)一個(gè)稍微復(fù)雜點(diǎn)的功能快速計(jì)算第n項(xiàng)斐波那契數(shù)F(n)。我們知道斐波那契數(shù)列增長極快F(100)就已經(jīng)是 354224848179261915075 這樣一個(gè)21位數(shù)了。單純用高精度加法迭代計(jì)算是 O(n) 的對(duì)于極大的 n比如 n10^6太慢。我們可以利用矩陣快速冪公式將問題轉(zhuǎn)化為矩陣的冪運(yùn)算而矩陣乘法中包含了整數(shù)乘法。斐波那契數(shù)的矩陣公式是[ F(n1) F(n) ] [1 1] ^ n [ F(n) F(n-1) ] [1 0]計(jì)算矩陣[1 1; 1 0]的 n 次冪結(jié)果的左上角元素就是F(n1)。矩陣快速冪的復(fù)雜度是 O(log n)但其中的乘法運(yùn)算需要用到我們的高精度乘法。實(shí)現(xiàn)步驟定義一個(gè)2x2的矩陣其元素為高精度整數(shù)BigInt。實(shí)現(xiàn)高精度矩陣的乘法。實(shí)現(xiàn)矩陣的快速冪算法。調(diào)用快速冪計(jì)算[1 1; 1 0]^n。輸出結(jié)果矩陣中的對(duì)應(yīng)元素。這個(gè)案例綜合運(yùn)用了高精度加法、乘法以及快速冪算法是一個(gè)很好的練習(xí)項(xiàng)目。它讓你看到高精度運(yùn)算不僅是獨(dú)立的更是構(gòu)建更復(fù)雜算法的基石。7. 總結(jié)與進(jìn)階資源走到這里你應(yīng)該已經(jīng)對(duì)高精度乘法從概念到實(shí)現(xiàn)從基礎(chǔ)到優(yōu)化有了一個(gè)全面的認(rèn)識(shí)。我們來回顧一下最關(guān)鍵的點(diǎn)核心思想用數(shù)組模擬豎式倒位存儲(chǔ)是關(guān)鍵它讓進(jìn)位處理變得高效自然。算法演進(jìn)從 O(n2) 的樸素算法到通過壓位獲得常數(shù)級(jí)優(yōu)化再到利用 FFT/NTT 實(shí)現(xiàn) O(n log n) 的質(zhì)變。對(duì)于絕大多數(shù)情況壓位高精度乘法是性價(jià)比最高、必須掌握的技能。細(xì)節(jié)魔鬼前導(dǎo)零、進(jìn)位處理時(shí)機(jī)、負(fù)數(shù)處理這些細(xì)節(jié)決定了你的代碼是否健壯。學(xué)以致用將其應(yīng)用到階乘、快速冪、矩陣運(yùn)算等實(shí)際問題中能加深理解。如果你想繼續(xù)深入深入研究FFT/NTT可以學(xué)習(xí)《算法導(dǎo)論》中多項(xiàng)式與FFT的章節(jié)或者在網(wǎng)上搜索“FFT 大數(shù)乘法”找到許多詳細(xì)的教程和代碼實(shí)現(xiàn)。閱讀優(yōu)秀源碼嘗試閱讀 GNU Multiple Precision Arithmetic Library (GMP) 的部分源碼或文檔了解工業(yè)級(jí)高精度庫的設(shè)計(jì)和優(yōu)化技巧例如它對(duì)不同規(guī)模數(shù)據(jù)采用不同算法Toom-Cook, Karatsuba 等這些是介于樸素和FFT之間的分治算法。挑戰(zhàn)自己實(shí)現(xiàn)一個(gè)完整的BigInt類支持加、減、乘、除、模、冪等所有運(yùn)算并確保其正確性和效率。高精度乘法就像一把鑰匙它打開了一扇門門后是關(guān)于計(jì)算機(jī)如何表示和處理數(shù)字、如何平衡精度與效率的廣闊世界。從準(zhǔn)確地算出100!開始你已經(jīng)在理解這個(gè)世界的路上邁出了堅(jiān)實(shí)的一步。 高精度乘法：從豎式模擬到FFT優(yōu)化，掌握大數(shù)運(yùn)算核心
1. 從“算不過來”到“算得精確”高精度乘法的現(xiàn)實(shí)需求在編程和算法競(jìng)賽的日常里我們經(jīng)常和整數(shù)打交道。大多數(shù)時(shí)候int或long long類型就能滿足需求畢竟它們能表示的數(shù)已經(jīng)相當(dāng)大了。但總有一些場(chǎng)景比如計(jì)算大數(shù)的階乘、處理超長整數(shù)的加密解密、或者模擬天體物理中的巨大數(shù)值時(shí)常規(guī)的整數(shù)類型會(huì)立刻“啞火”——它們溢出了。你可能會(huì)想不是有Python這種天生支持大整數(shù)的語言嗎確實(shí)如此但理解其背后的原理尤其是在C、Java等語言中如何手動(dòng)實(shí)現(xiàn)是深入理解計(jì)算機(jī)如何處理“無限”精度數(shù)據(jù)的關(guān)鍵。這就是高精度算法的用武之地而乘法作為四則運(yùn)算中最復(fù)雜的一環(huán)其高精度實(shí)現(xiàn)更是核心中的核心。簡(jiǎn)單來說高精度乘法就是模擬我們小學(xué)時(shí)學(xué)的豎式乘法但對(duì)象是每一位數(shù)字都存儲(chǔ)在數(shù)組里的“大數(shù)”。它不依賴語言內(nèi)置的大整數(shù)庫而是通過最基礎(chǔ)的數(shù)組操作實(shí)現(xiàn)任意長度整數(shù)的精確相乘。這不僅是算法競(jìng)賽的?？透抢斫庥?jì)算機(jī)底層數(shù)值計(jì)算、鍛煉嚴(yán)謹(jǐn)編程思維的絕佳練習(xí)。今天我們就拋開那些現(xiàn)成的庫從頭到尾把高精度乘法的原理、實(shí)現(xiàn)、優(yōu)化以及那些容易踩的坑掰開揉碎了講清楚。2. 基石如何用數(shù)組表示一個(gè)“大數(shù)”在實(shí)現(xiàn)任何高精度運(yùn)算之前我們首先要解決一個(gè)根本問題如何在計(jì)算機(jī)中表示一個(gè)遠(yuǎn)超內(nèi)置類型范圍的整數(shù)答案就是用數(shù)組確切地說是用數(shù)組的每一個(gè)元素來存儲(chǔ)大數(shù)的一位。2.1 存儲(chǔ)格式的選擇順位存儲(chǔ) vs. 倒位存儲(chǔ)這里有兩個(gè)主流的選擇它們各有優(yōu)劣。方案一順位存儲(chǔ)即數(shù)組下標(biāo)0存儲(chǔ)最高位下標(biāo)n-1存儲(chǔ)最低位。這很符合人類的閱讀習(xí)慣。但是當(dāng)你進(jìn)行運(yùn)算時(shí)尤其是涉及進(jìn)位操作時(shí)問題就來了。乘法或加法中進(jìn)位是從最低位向最高位傳遞的。如果最低位在數(shù)組末尾那么處理進(jìn)位時(shí)你可能需要在數(shù)組頭部進(jìn)行插入操作這在數(shù)組中是非常低效的需要移動(dòng)大量元素。方案二倒位存儲(chǔ)推薦這是實(shí)踐中幾乎無一例外采用的方法。我們讓數(shù)組下標(biāo)0存儲(chǔ)個(gè)位最低位下標(biāo)1存儲(chǔ)十位以此類推。這樣做有兩大好處進(jìn)位處理高效運(yùn)算從低位開始產(chǎn)生的進(jìn)位可以自然地向更高下標(biāo)即更高位累加完全符合計(jì)算過程無需移動(dòng)數(shù)組元素。長度擴(kuò)展方便如果結(jié)果位數(shù)比原數(shù)多我們只需要在數(shù)組末尾更高下標(biāo)追加新的元素即可。例如數(shù)字12345用倒位存儲(chǔ)的數(shù)組A表示就是A[0] 5,A[1] 4,A[2] 3,A[3] 2,A[4] 1。輸出時(shí)我們只需要從最高位數(shù)組最后一個(gè)有效元素倒序輸出即可。注意在代碼中我們通常使用vectorint或普通數(shù)組來存儲(chǔ)并維護(hù)一個(gè)變量表示當(dāng)前數(shù)字的長度有效位數(shù)以避免處理前導(dǎo)零。2.2 輸入與輸出的處理由于數(shù)字可能非常大我們無法用int直接讀入。標(biāo)準(zhǔn)的做法是先用字符串string或char[]讀入這個(gè)數(shù)字然后再將其轉(zhuǎn)換為倒位存儲(chǔ)的數(shù)組。string str_num 12345678901234567890; vectorint A; for (int i str_num.size() - 1; i 0; i--) { A.push_back(str_num[i] - 0); // 字符轉(zhuǎn)數(shù)字并倒序存入 } // 此時(shí) A [0,9,8,7,6,5,4,3,2,1,0,9,8,7,6,5,4,3,2,1]輸出時(shí)同樣需要倒序for (int i A.size() - 1; i 0; i--) { cout A[i]; }3. 核心算法拆解模擬豎式乘法的每一步高精度乘法的本質(zhì)就是模擬我們熟悉的豎式計(jì)算。假設(shè)我們要計(jì)算A * B其中A和B都是高精度數(shù)倒位存儲(chǔ)的數(shù)組。我們來看最基礎(chǔ)、最直觀的算法實(shí)現(xiàn)。3.1 算法流程與手動(dòng)模擬設(shè)A有n位B有m位。我們知道A * B的結(jié)果最多有n m位。計(jì)算過程創(chuàng)建一個(gè)結(jié)果數(shù)組C初始長度設(shè)為n m所有位初始化為0。用B的每一位B[j]j從0到m-1去乘以整個(gè)A。對(duì)于每一對(duì)A[i]和B[j]計(jì)算其乘積temp A[i] * B[j]。將這個(gè)乘積temp加到結(jié)果數(shù)組C的正確位置上。這個(gè)位置是C[i j]。為什么是i j因?yàn)锳[i]是A的第i位實(shí)際代表A[i] * 10^iB[j]是B的第j位代表B[j] * 10^j它們相乘的結(jié)果對(duì)最終結(jié)果的貢獻(xiàn)位是10^(ij)對(duì)應(yīng)數(shù)組下標(biāo)就是i j。處理加法帶來的進(jìn)位。由于temp可能是一個(gè)兩位數(shù)最大9*981加上C[ij]原有的值后可能會(huì)產(chǎn)生進(jìn)位這個(gè)進(jìn)位需要向高位C[ij1]累加。遍歷完所有i和j后C中存儲(chǔ)的就是結(jié)果但可能包含前導(dǎo)零。我們需要從最高位開始移除這些無意義的前導(dǎo)零得到最終的有效結(jié)果。讓我們手動(dòng)模擬一個(gè)小例子123 * 45。A [3, 2, 1] (123)B [5, 4] (45)初始化 C [0, 0, 0, 0, 0] (長度 325)第一輪j0 (B[0]5)i0: temp A[0]B[0] 3515。 C[00] 15 - C[0]15。進(jìn)位C[0]留5向C[1]進(jìn)1。i1: temp 2*510。 C[10] 10 - C[1]101(進(jìn)位)11。進(jìn)位C[1]留1向C[2]進(jìn)1。i2: temp 1*55。 C[20] 5 - C[2]51(進(jìn)位)6。進(jìn)位C[2]6無進(jìn)位。 此輪后C [5, 1, 6, 0, 0]第二輪j1 (B[1]4)i0: temp 3*412。 C[01] 12 - C[1]11213。進(jìn)位C[1]留3向C[2]進(jìn)1。i1: temp 2*48。 C[11] 8 - C[2]681(進(jìn)位)15。進(jìn)位C[2]留5向C[3]進(jìn)1。i2: temp 1*44。 C[21] 4 - C[3]041(進(jìn)位)5。進(jìn)位C[3]5無進(jìn)位。 此輪后C [5, 3, 5, 5, 0]最終處理從最高位C[4]開始檢查C[4]0 是前導(dǎo)零移除。得到最終數(shù)組 [5, 3, 5, 5]倒序輸出為5535正是123 * 45的結(jié)果。3.2 基礎(chǔ)代碼實(shí)現(xiàn)樸素算法根據(jù)上述流程我們可以寫出最樸素的代碼。這里以 C 為例使用vectorint存儲(chǔ)大數(shù)。#include iostream #include vector #include string using namespace std; // 高精度乘法 (樸素算法) vectorint multiply_naive(const vectorint A, const vectorint B) { int n A.size(), m B.size(); // 結(jié)果最多有 nm 位 vectorint C(n m, 0); // 核心計(jì)算部分 for (int i 0; i n; i) { for (int j 0; j m; j) { C[i j] A[i] * B[j]; // 立即處理進(jìn)位防止單一位存儲(chǔ)的數(shù)字過大 C[i j 1] C[i j] / 10; C[i j] % 10; } } // 處理最后一輪的進(jìn)位實(shí)際上上面的循環(huán)內(nèi)處理了大部分但最高位可能還有進(jìn)位 // 更穩(wěn)妥的做法是再統(tǒng)一處理一次所有位的進(jìn)位 // 但通常內(nèi)循環(huán)中即時(shí)處理已足夠這里為了清晰展示另一種統(tǒng)一處理的方式 // 我們可以在計(jì)算完所有乘積后再統(tǒng)一處理進(jìn)位 // vectorint C(n m, 0); // for (int i 0; i n; i) // for (int j 0; j m; j) // C[i j] A[i] * B[j]; // 先只累加不處理進(jìn)位 // // 統(tǒng)一處理進(jìn)位 // int carry 0; // for (int i 0; i C.size(); i) { // C[i] carry; // carry C[i] / 10; // C[i] % 10; // } // 移除前導(dǎo)零 while (C.size() 1 C.back() 0) { C.pop_back(); } return C; } // 輔助函數(shù)將字符串轉(zhuǎn)換為倒位存儲(chǔ)的vector vectorint str_to_vec(const string s) { vectorint res; for (int i s.size() - 1; i 0; i--) { res.push_back(s[i] - 0); } // 如果輸入是0確保結(jié)果不是空vector if (res.empty()) res.push_back(0); return res; } // 輔助函數(shù)輸出高精度數(shù) void print_vec(const vectorint num) { for (int i num.size() - 1; i 0; i--) { cout num[i]; } cout endl; } int main() { string s1, s2; // 假設(shè)輸入兩個(gè)大數(shù)字符串 s1 123456789; s2 987654321; vectorint A str_to_vec(s1); vectorint B str_to_vec(s2); vectorint C multiply_naive(A, B); cout s1 * s2 ; print_vec(C); // 應(yīng)輸出 121932631112635269 return 0; }這段代碼清晰地展示了高精度乘法的核心思想。它的時(shí)間復(fù)雜度是 O(nm)對(duì)于兩個(gè) n 位和 m 位的數(shù)需要進(jìn)行 nm 次單位數(shù)乘法和加法。4. 性能瓶頸與優(yōu)化從 O(n2) 到更快的算法樸素算法雖然正確但在面對(duì)位數(shù)非常多比如幾十萬位的大數(shù)時(shí)O(n2) 的復(fù)雜度會(huì)成為嚴(yán)重的性能瓶頸。在實(shí)際應(yīng)用和算法競(jìng)賽中我們需要更高效的算法。4.1 為什么樸素算法慢根本原因在于它模擬的是最基礎(chǔ)的豎式乘法每一位都需要和另一個(gè)數(shù)的每一位相乘。當(dāng)位數(shù)增加時(shí)計(jì)算量呈平方級(jí)增長。例如兩個(gè) 10000 位的數(shù)相乘需要進(jìn)行約 1 億次單位數(shù)乘法和加法。4.2 優(yōu)化方向一壓位存儲(chǔ)我們之前是一位數(shù)組元素存一個(gè)十進(jìn)制數(shù)字0-9。這其實(shí)浪費(fèi)了int類型的存儲(chǔ)空間。一個(gè)int通常能存儲(chǔ)高達(dá)約20億的數(shù)我們完全可以利用它來存儲(chǔ)多位十進(jìn)制數(shù)這就是壓位。常見的壓位方式萬進(jìn)制壓位每個(gè)數(shù)組元素存儲(chǔ) 4 位十進(jìn)制數(shù)范圍 0-9999。因?yàn)?10000 * 10000 100000000仍在int的安全范圍內(nèi)小于21億且進(jìn)位處理方便。億進(jìn)制壓位每個(gè)數(shù)組元素存儲(chǔ) 8 位十進(jìn)制數(shù)范圍 0-99999999。這要求使用long long或int64_t類型存儲(chǔ)因?yàn)?100000000 * 100000000 會(huì)超過int范圍。億進(jìn)制能進(jìn)一步減少循環(huán)次數(shù)。壓位帶來的改變輸入輸出需要按“塊”來解析和輸出字符串。乘法計(jì)算核心邏輯不變但每次乘法的對(duì)象變成了“塊”一個(gè)多位整數(shù)乘法的結(jié)果可能很大需要更仔細(xì)地處理進(jìn)位。進(jìn)位基數(shù)從 10 變成了 10000萬進(jìn)制或 100000000億進(jìn)制。萬進(jìn)制壓位乘法示例偽代碼思路// 假設(shè) A, B 已是萬進(jìn)制倒位存儲(chǔ)的vectorint vectorint multiply_compressed(const vectorint A, const vectorint B) { int n A.size(), m B.size(); vectorlong long C(n m, 0); // 使用long long防止中間結(jié)果溢出 const int BASE 10000; for (int i 0; i n; i) { for (int j 0; j m; j) { C[i j] (long long)A[i] * B[j]; // 這里可以延遲處理進(jìn)位 } } // 統(tǒng)一處理進(jìn)位 long long carry 0; for (int i 0; i C.size(); i) { C[i] carry; carry C[i] / BASE; C[i] % BASE; } // 移除前導(dǎo)零整個(gè)塊為0 while (C.size() 1 C.back() 0) C.pop_back(); // 將C從long long轉(zhuǎn)回int (如果值在int范圍內(nèi)) vectorint res(C.begin(), C.end()); return res; }壓位能將計(jì)算量減少到原來的 1/4 或 1/8常數(shù)級(jí)優(yōu)化顯著代碼復(fù)雜度增加不多是競(jìng)賽和實(shí)踐中必用的優(yōu)化手段。4.3 優(yōu)化方向二分治算法FFT與NTT當(dāng)位數(shù)達(dá)到十萬甚至百萬級(jí)時(shí)即使是壓位優(yōu)化的 O(n2) 算法也力不從心。這時(shí)就需要時(shí)間復(fù)雜度更低的算法它們基于“分治”思想。基本原理將大數(shù)乘法轉(zhuǎn)化為多項(xiàng)式乘法。一個(gè) n 位十進(jìn)制數(shù)可以看作一個(gè)以 10 為基的多項(xiàng)式。兩個(gè)多項(xiàng)式相乘樸素也是 O(n2)但利用快速傅里葉變換FFT或數(shù)論變換NTT可以在 O(n log n) 時(shí)間內(nèi)完成。FFT/NTT 乘法步驟系數(shù)表示將兩個(gè)大數(shù) A 和 B 視為多項(xiàng)式的系數(shù)倒位存儲(chǔ)的數(shù)組本身就是系數(shù)。點(diǎn)值表示利用 FFT/NTT將兩個(gè)多項(xiàng)式的系數(shù)表示快速轉(zhuǎn)換為在特定點(diǎn)集上的值點(diǎn)值表示。這個(gè)過程是 O(n log n)。點(diǎn)值相乘將兩個(gè)多項(xiàng)式在相同點(diǎn)上的值一一對(duì)應(yīng)相乘得到結(jié)果多項(xiàng)式的點(diǎn)值表示。這是 O(n)。插值利用逆 FFT/NTT將結(jié)果多項(xiàng)式的點(diǎn)值表示快速轉(zhuǎn)換回系數(shù)表示。這個(gè)過程也是 O(n log n)。進(jìn)位處理得到的系數(shù)數(shù)組是多項(xiàng)式乘法的結(jié)果但每一位可能遠(yuǎn)大于進(jìn)制基數(shù)比如10或10000需要像普通高精度一樣進(jìn)行統(tǒng)一的進(jìn)位處理。為什么有效FFT/NTT 巧妙地利用了復(fù)數(shù)的單位根或數(shù)論原根的性質(zhì)將多項(xiàng)式系數(shù)與點(diǎn)值之間的轉(zhuǎn)換復(fù)雜度從 O(n2) 降到了 O(n log n)從而大幅加速了乘法的核心步驟。實(shí)現(xiàn)考量FFT使用復(fù)數(shù)運(yùn)算有精度誤差對(duì)于極大的整數(shù)可能需要多次變換或調(diào)整參數(shù)來保證精度。NTT在模素?cái)?shù)下進(jìn)行無精度誤差結(jié)果精確但要求模素?cái)?shù) P 滿足某些性質(zhì)如 P c * 2^k 1且數(shù)值不能超過 P。通常需要多次 NTT 配合中國剩余定理CRT來還原大數(shù)。應(yīng)用場(chǎng)景在算法競(jìng)賽中當(dāng) n 超過 5000~10000 時(shí)FFT/NTT 的優(yōu)勢(shì)就開始體現(xiàn)。許多標(biāo)準(zhǔn)的高精度乘法庫如 GMP在底層就使用了這些算法。實(shí)操心得對(duì)于絕大多數(shù)日常應(yīng)用和競(jìng)賽題目掌握壓位高精度乘法已經(jīng)完全足夠。FFT/NTT 屬于“屠龍技”在需要處理極端大數(shù)據(jù)時(shí)才會(huì)用到。建議先精通樸素和壓位算法理解其每一個(gè)細(xì)節(jié)再在有余力時(shí)去研究分治算法。直接上手 FFT 容易陷入實(shí)現(xiàn)細(xì)節(jié)而忽略了高精度本身的數(shù)據(jù)處理邏輯。5. 實(shí)戰(zhàn)中的細(xì)節(jié)、陷阱與經(jīng)驗(yàn)分享理解了原理和算法真正動(dòng)手實(shí)現(xiàn)時(shí)還有很多細(xì)節(jié)決定成敗。下面是我在多次實(shí)現(xiàn)和使用高精度乘法中積累的一些經(jīng)驗(yàn)。5.1 前導(dǎo)零的處理這是一個(gè)非常常見且容易忽略的 bug 來源。在乘法完成后結(jié)果數(shù)組C的長度是預(yù)分配的nm但實(shí)際有效位數(shù)可能小于這個(gè)值。例如100 * 0 000我們需要把前面的兩個(gè)0去掉只保留一個(gè)0。處理技巧在輸出或返回結(jié)果前一定要從最高位數(shù)組末尾向前檢查移除所有連續(xù)的0直到遇到非零數(shù)字或只剩下一位保證結(jié)果為0時(shí)能正確輸出0。在壓位存儲(chǔ)中前導(dǎo)零是整個(gè)“塊”為0判斷條件是C.back() 0。5.2 進(jìn)位的處理時(shí)機(jī)在樸素算法的代碼示例中我展示了兩種處理進(jìn)位的方式即時(shí)處理在內(nèi)層循環(huán)中每次累加后立即處理當(dāng)前位的進(jìn)位。這樣做邏輯清晰不容易出錯(cuò)且單一位的數(shù)字不會(huì)太大。統(tǒng)一處理先完成所有A[i]*B[j]的累加讓C中的每一位可能遠(yuǎn)大于 9或壓位的基數(shù)然后再用一個(gè)單獨(dú)的循環(huán)統(tǒng)一處理所有位的進(jìn)位。經(jīng)驗(yàn)之談對(duì)于新手推薦使用統(tǒng)一處理。原因如下邏輯更分離乘法累加和進(jìn)位處理兩個(gè)步驟涇渭分明便于調(diào)試。性能影響微乎其微對(duì)于 O(n2) 算法多一次 O(n) 的遍歷開銷幾乎可以忽略。在壓位和 FFT 算法中由于中間結(jié)果可能非常大統(tǒng)一處理進(jìn)位幾乎是唯一的選擇。統(tǒng)一處理的代碼模式非常固定建議背下來int carry 0; for (int i 0; i C.size(); i) { C[i] carry; carry C[i] / BASE; // BASE是進(jìn)制十進(jìn)制為10萬進(jìn)制為10000 C[i] % BASE; } // 處理最高位可能的額外進(jìn)位 while (carry) { C.push_back(carry % BASE); carry / BASE; }5.3 負(fù)數(shù)的處理高精度運(yùn)算通常也支持負(fù)數(shù)。常見的處理方式是單獨(dú)存儲(chǔ)符號(hào)位。定義結(jié)構(gòu)體BigInt包含一個(gè)bool sign正為false負(fù)為true和一個(gè)vectorint存儲(chǔ)絕對(duì)值。乘法規(guī)則sign_C sign_A ^ sign_B異或同號(hào)得正異號(hào)得負(fù)。在實(shí)現(xiàn)乘法函數(shù)時(shí)先取兩數(shù)的絕對(duì)值進(jìn)行計(jì)算得到結(jié)果的絕對(duì)值最后再附上計(jì)算出的符號(hào)。特別注意-0應(yīng)該規(guī)范化為0即當(dāng)結(jié)果為0時(shí)無論符號(hào)是什么都強(qiáng)制將符號(hào)設(shè)為正。5.4 與加、減、除、模運(yùn)算的協(xié)作高精度乘法很少孤立使用它通常是一個(gè)完整大整數(shù)類的一部分。在設(shè)計(jì)時(shí)需要考慮與其他運(yùn)算的兼容性。存儲(chǔ)一致性確保所有運(yùn)算都使用同一種存儲(chǔ)格式如倒位存儲(chǔ)、萬進(jìn)制壓位。函數(shù)接口設(shè)計(jì)清晰的接口如BigInt operator*(const BigInt rhs) const。性能權(quán)衡在實(shí)現(xiàn)除法時(shí)可能會(huì)調(diào)用乘法例如在試商時(shí)。如果乘法非常快比如用了FFT可以提升除法的整體性能。5.5 測(cè)試策略高精度代碼極易出錯(cuò)必須有完善的測(cè)試。邊界測(cè)試測(cè)試0、1、10等特殊數(shù)字。隨機(jī)測(cè)試生成大量隨機(jī)的大整數(shù)對(duì)用你的高精度乘法計(jì)算結(jié)果同時(shí)用 Python 等支持大整數(shù)的語言計(jì)算相同算式對(duì)比結(jié)果是否一致。這是最有效的測(cè)試方法。壓力測(cè)試測(cè)試兩個(gè)位數(shù)很多如幾千位的數(shù)相乘檢查時(shí)間和結(jié)果是否正確。符號(hào)測(cè)試測(cè)試正數(shù)、負(fù)數(shù)、零之間的各種組合。6. 從理論到應(yīng)用高精度乘法的典型場(chǎng)景掌握了實(shí)現(xiàn)我們來看看高精度乘法具體用在哪兒。這能幫你更好地理解它的價(jià)值。6.1 算法競(jìng)賽中的經(jīng)典問題階乘計(jì)算計(jì)算n!n的階乘。隨著 n 增大結(jié)果會(huì)迅速超出任何內(nèi)置類型的范圍。例如100!就有158位。這需要循環(huán)進(jìn)行高精度乘法。組合數(shù)計(jì)算計(jì)算 C(n, m) 時(shí)可能涉及大數(shù)的乘法和除法。斐波那契數(shù)列某些變體或極大下標(biāo)的斐波那契數(shù)。高精度冪運(yùn)算計(jì)算a^b其中a和b都可能很大需要通過快速冪算法結(jié)合高精度乘法來實(shí)現(xiàn)。大數(shù)進(jìn)制轉(zhuǎn)換將一個(gè)非常大的數(shù)從一種進(jìn)制轉(zhuǎn)換到另一種進(jìn)制過程中可能涉及高精度乘法和除法。6.2 實(shí)際工程與科研應(yīng)用密碼學(xué)RSA等公鑰加密算法涉及數(shù)百位甚至上千位大整數(shù)的乘、模冪運(yùn)算。雖然這些庫如OpenSSL, GMP使用更底層的優(yōu)化和匯編指令但原理相通。數(shù)值計(jì)算與仿真在天體物理、量子化學(xué)等領(lǐng)域模擬需要極高的數(shù)值精度遠(yuǎn)超雙精度浮點(diǎn)數(shù)的范圍這時(shí)就需要高精度算術(shù)庫。計(jì)算機(jī)代數(shù)系統(tǒng)如 Mathematica、Maple它們能進(jìn)行符號(hào)計(jì)算和任意精度數(shù)值計(jì)算底層離不開高效的高精度算法。分布式計(jì)算校驗(yàn)在一些分布式協(xié)議中可能會(huì)用到大數(shù)運(yùn)算來生成或驗(yàn)證全局唯一的ID或校驗(yàn)和。6.3 一個(gè)完整的實(shí)戰(zhàn)案例計(jì)算任意位數(shù)的斐波那契數(shù)讓我們用高精度乘法來實(shí)現(xiàn)一個(gè)稍微復(fù)雜點(diǎn)的功能快速計(jì)算第n項(xiàng)斐波那契數(shù)F(n)。我們知道斐波那契數(shù)列增長極快F(100)就已經(jīng)是 354224848179261915075 這樣一個(gè)21位數(shù)了。單純用高精度加法迭代計(jì)算是 O(n) 的對(duì)于極大的 n比如 n10^6太慢。我們可以利用矩陣快速冪公式將問題轉(zhuǎn)化為矩陣的冪運(yùn)算而矩陣乘法中包含了整數(shù)乘法。斐波那契數(shù)的矩陣公式是[ F(n1) F(n) ] [1 1] ^ n [ F(n) F(n-1) ] [1 0]計(jì)算矩陣[1 1; 1 0]的 n 次冪結(jié)果的左上角元素就是F(n1)。矩陣快速冪的復(fù)雜度是 O(log n)但其中的乘法運(yùn)算需要用到我們的高精度乘法。實(shí)現(xiàn)步驟定義一個(gè)2x2的矩陣其元素為高精度整數(shù)BigInt。實(shí)現(xiàn)高精度矩陣的乘法。實(shí)現(xiàn)矩陣的快速冪算法。調(diào)用快速冪計(jì)算[1 1; 1 0]^n。輸出結(jié)果矩陣中的對(duì)應(yīng)元素。這個(gè)案例綜合運(yùn)用了高精度加法、乘法以及快速冪算法是一個(gè)很好的練習(xí)項(xiàng)目。它讓你看到高精度運(yùn)算不僅是獨(dú)立的更是構(gòu)建更復(fù)雜算法的基石。7. 總結(jié)與進(jìn)階資源走到這里你應(yīng)該已經(jīng)對(duì)高精度乘法從概念到實(shí)現(xiàn)從基礎(chǔ)到優(yōu)化有了一個(gè)全面的認(rèn)識(shí)。我們來回顧一下最關(guān)鍵的點(diǎn)核心思想用數(shù)組模擬豎式倒位存儲(chǔ)是關(guān)鍵它讓進(jìn)位處理變得高效自然。算法演進(jìn)從 O(n2) 的樸素算法到通過壓位獲得常數(shù)級(jí)優(yōu)化再到利用 FFT/NTT 實(shí)現(xiàn) O(n log n) 的質(zhì)變。對(duì)于絕大多數(shù)情況壓位高精度乘法是性價(jià)比最高、必須掌握的技能。細(xì)節(jié)魔鬼前導(dǎo)零、進(jìn)位處理時(shí)機(jī)、負(fù)數(shù)處理這些細(xì)節(jié)決定了你的代碼是否健壯。學(xué)以致用將其應(yīng)用到階乘、快速冪、矩陣運(yùn)算等實(shí)際問題中能加深理解。如果你想繼續(xù)深入深入研究FFT/NTT可以學(xué)習(xí)《算法導(dǎo)論》中多項(xiàng)式與FFT的章節(jié)或者在網(wǎng)上搜索“FFT 大數(shù)乘法”找到許多詳細(xì)的教程和代碼實(shí)現(xiàn)。閱讀優(yōu)秀源碼嘗試閱讀 GNU Multiple Precision Arithmetic Library (GMP) 的部分源碼或文檔了解工業(yè)級(jí)高精度庫的設(shè)計(jì)和優(yōu)化技巧例如它對(duì)不同規(guī)模數(shù)據(jù)采用不同算法Toom-Cook, Karatsuba 等這些是介于樸素和FFT之間的分治算法。挑戰(zhàn)自己實(shí)現(xiàn)一個(gè)完整的BigInt類支持加、減、乘、除、模、冪等所有運(yùn)算并確保其正確性和效率。高精度乘法就像一把鑰匙它打開了一扇門門后是關(guān)于計(jì)算機(jī)如何表示和處理數(shù)字、如何平衡精度與效率的廣闊世界。從準(zhǔn)確地算出100!開始你已經(jīng)在理解這個(gè)世界的路上邁出了堅(jiān)實(shí)的一步。