問(wèn)題15 大數(shù)乘法三解

?常用的程序設(shè)計(jì)語(yǔ)言中都提供算術(shù)表達(dá)式功能，直接使用即可。

發(fā)明計(jì)算機(jī)最初的目的，計(jì)算彈道，密碼破譯，都是為了高效的計(jì)算。

程序設(shè)計(jì)初學(xué)者往往認(rèn)為算術(shù)運(yùn)算是非常簡(jiǎn)單的事。但是，當(dāng)計(jì)算的數(shù)很大（位數(shù)很多）時(shí)，就不是一件簡(jiǎn)單的事情了，需要結(jié)合計(jì)算方法和算法設(shè)計(jì)兩方面的知識(shí)，才能讓計(jì)算機(jī)高效的計(jì)算“大”數(shù)。

?

本章，作者針對(duì)求兩個(gè)大整數(shù)的精確乘問(wèn)題，介紹了三種風(fēng)格迥異的方法。

第一種方法，利用字符串（存儲(chǔ)大整數(shù)）和列表（存儲(chǔ)中間結(jié)果和最后的乘積），讓計(jì)算機(jī)直接模擬手工“長(zhǎng)乘法”。這個(gè)算法理論上不受乘數(shù)大小的限制。

?

計(jì)算機(jī)執(zhí)行一次乘法操作的時(shí)間遠(yuǎn)遠(yuǎn)大于加法操作的時(shí)間。如何減小大數(shù)乘法中乘法操作的次數(shù)，可以提高大數(shù)乘法的執(zhí)行效率。

?

本章介紹的第二種方法是Karatsuba算法（書(shū)中的名字打錯(cuò)了）是一種快速乘法算法。算法采用了分治法的策略，使用三個(gè)較小數(shù)字的乘法來(lái)計(jì)算兩個(gè)大數(shù)的乘積的公式（我第一次在算法書(shū)中看到時(shí)，大為震撼）。它將算法的復(fù)雜度從n的平方量級(jí)降到log23

?

本章介紹的第三種方法，稱為“中國(guó)余數(shù)定理”（來(lái)源與《孫子算經(jīng)》），把兩個(gè)大的乘數(shù)分解到一些互素的模上，然后通過(guò)解同余方程組，就可得到相應(yīng)的乘積。這種方法可以大幅度降低乘數(shù)的位數(shù)，從而提高執(zhí)行效率。

?

【作者感受】

學(xué)計(jì)算機(jī)的人，都是數(shù)學(xué)還不錯(cuò)的，不過(guò)每次看到這樣的章節(jié)，總覺(jué)得數(shù)學(xué)還學(xué)得不夠，難怪，有人推薦，本科學(xué)數(shù)學(xué)，研究生再進(jìn)入計(jì)算機(jī)領(lǐng)域。在計(jì)算機(jī)領(lǐng)域中混，數(shù)學(xué)不好真不行。