15.9 大數乘法

壓軸:大數乘法。關鍵問題是——A[i] 乘 B[j] 的結果,該記到答案的哪一位?

用位值想(15.1):A[i] 的位值是 10^i、B[j] 的位值是 10^j,相乘的位值是 10^i \times 10^j = 10^{i+j}(又是指數律)。所以:

\texttt{A[i]} \times \texttt{B[j]} \text{ 的貢獻,歸戶到 } \texttt{C[i + j]}

「歸戶」就是記帳的意思——每筆乘積像一筆錢,匯進「第 i+j 位」這個帳戶累加。兩層迴圈把所有 (i, j) 組合都乘一遍、各自歸戶,先不進位;全部累加完,最後用 15.8 的統一進位一次收拾。這比「邊乘邊進位」好寫得多——乘的階段只管記帳,進位的程式碼跟加法共用同一段。

登入後即可閱讀完整內容

語法書免費開放給所有 AACPOJ 帳號,註冊只要一分鐘。