高精度加法

維基百科,自由的百科全書

高精度加法是信息學的一種重要算法。這種算法使用多個存儲單位進行計算,因此它的計算範圍超過一般使用一個存儲單位的算法。也是一些信息學競賽的常考題目。

基本算法

以358934760892734899+38960302975237462為例:

1、計算結果的位數

358934760892734899共18位

38960302975237462 共17位

故結果不會超過19位。

2、將要計算的數字分割成多段,按照順序排列(這裡以0-32767作為每一存儲單位存儲的數的限制):

35 8934 7608 9273 4899
3 8960 3029 7523 7462

(為提高空間利用效率,可以一個存儲單位存儲多位數。)

3、將兩數相加。

35 8934 7608 9273 4899
3 8960 3029 7523 7462
和(不進位) 38 17894 10637 16796 12361
和(進位後) 39 7895 0638 6797 2361

4、輸出結果。

從高位到低位依次輸出。除最高位以外,其他低位上不足4位的要在前面補上0。

參見