高精度計算器算法 (1)

1、高精度計算器高精度計算器算法思想介紹算法思想介紹算法要求算法要求 設計一個高精度計算器設計一個高精度計算器 可以實現(xiàn)一百位以上、五百位以下數(shù)的運可以實現(xiàn)一百位以上、五百位以下數(shù)的運算算 加法加法 減法減法 乘法乘法 除法除法數(shù)據(jù)邏輯結構數(shù)據(jù)邏輯結構 兩個操作數(shù)均為線性結構兩個操作數(shù)均為線性結構 結果也為線性結構結果也為線性結構數(shù)據(jù)存儲結構設計數(shù)據(jù)存儲結構設計 操作數(shù)和操作符均采用順序存儲結構（數(shù)操作數(shù)和操作符均采用順序存儲結構（數(shù)組）進行存儲組）進行存儲 數(shù)組類型可以是字符型（節(jié)省存儲空間）數(shù)組類型可以是字符型（節(jié)省存儲空間） 也可以是整數(shù)類型（運算方便）也可以是整數(shù)類型（運算方便） 以下以整

2、數(shù)數(shù)組為例以下以整數(shù)數(shù)組為例數(shù)據(jù)存儲結構設計數(shù)據(jù)存儲結構設計 操作數(shù)：設數(shù)組操作數(shù)：設數(shù)組A和數(shù)組和數(shù)組B為長度為為長度為500的的整型數(shù)組，下標從整型數(shù)組，下標從1開始。開始。 運算結果：設數(shù)組運算結果：設數(shù)組C也為長度為也為長度為500的整型的整型數(shù)組，下標從數(shù)組，下標從1開始。開始。操作數(shù)操作數(shù)A：操作數(shù)操作數(shù)B：結果結果C：下標：下標：1 2 3 4 500數(shù)據(jù)輸入（數(shù)據(jù)輸入（Data in) 將將A、B、C數(shù)組的每一位用數(shù)組的每一位用0填充填充 輸入數(shù)據(jù)輸入數(shù)據(jù)A和和B，他們的最后一位均存在下標為，他們的最后一位均存在下標為500的位置的位置末位對齊末位對齊 如：輸入如：輸入A為為1

3、2345 B為為123456789 存儲結構為：存儲結構為：操作數(shù)操作數(shù)A：操作數(shù)操作數(shù)B：下標：下標：1 2 495 496 497 498 499 5005432154321987654321加法運算加法運算 從末位開始，對應位進行加法：從末位開始，對應位進行加法：Ci=Ai+Bi+JW 若結果小于若結果小于10，直接存入數(shù)組，直接存入數(shù)組C中對應單元，中對應單元，JW=0 若結果大于等于若結果大于等于10，將其減，將其減10后的結果存入數(shù)組后的結果存入數(shù)組C中中對應位，并記進位位變量值為對應位，并記進位位變量值為1：JW=1。操作數(shù)操作數(shù)A：操作數(shù)操作數(shù)B：下標：下標：1 2 495 4

4、96 497 498 499 5005432154321987654321結果結果C：414JWW=111JW=1JW=0JW=0JW=0JW=0JW=0JW=0減法運算減法運算 從末位開始，對應位進行減法：從末位開始，對應位進行減法：Ci=Ai-Bi-JW（借位）（借位） 若結果大于等于若結果大于等于0，直接存入數(shù)組，直接存入數(shù)組C中對應單元，中對應單元，JW=0 若結果小于若結果小于0，ci=ci+10，并記，并記JW=1。操作數(shù)操作數(shù)A：操作數(shù)操作數(shù)B：下標：下標：1 2 495 496 497 498 499 50054321543219871結果結果C：6

5、-4JW=15501-5JW=1-5JW=1JW=0JW=0JW=0簡單乘法運算簡單乘法運算 將乘數(shù)的每一位單獨拿出來（設為將乘數(shù)的每一位單獨拿出來（設為X）乘以）乘以被乘數(shù)被乘數(shù)N位數(shù)乘位數(shù)乘1位數(shù)位數(shù)將該將該N位數(shù)位數(shù)累加累加X次即可。次即可。 注意：進位問題注意：進位問題 如：如：123451789操作數(shù)操作數(shù)A：操作數(shù)操作數(shù)B：下標：下標：1 2 495 496 497 498 499 50054321543219結果：結果：第一步：第一步：123459 調(diào)用調(diào)用9次次12345自加，得到：自加，得到：501111第二步：第二步：123458操作數(shù)操作數(shù)A：操作數(shù)操作數(shù)B：下標：下標：

6、1 2 495 496 497 498 499 50054321543218結果：結果：06789 調(diào)用調(diào)用8次次12345自加，得到：自加，得到： 將第二次的結果左移一位（將第二次的結果左移一位（10）后累加）后累加上第一次的結果上第一次的結果5011110678900789001 依次類推，直至所有乘數(shù)都乘完為止依次類推，直至所有乘數(shù)都乘完為止除法運算除法運算 此處只演示被除數(shù)大于除數(shù)的情況此處只演示被除數(shù)大于除數(shù)的情況 假設被除數(shù)有假設被除數(shù)有M位，除數(shù)有位，除數(shù)有N位（位（M=N） 第一步：從被除數(shù)的左邊取出第一步：從被除數(shù)的左邊取出N位，將其與位，將其與除數(shù)進行逐位比較，得出除數(shù)進行

7、逐位比較，得出大于大于或或等于等于或或小小于于三種結果。三種結果。 若結果是小于，再取被除數(shù)的下一位補上。若結果是小于，再取被除數(shù)的下一位補上。 第二步：將除數(shù)乘第二步：將除數(shù)乘2后與被除數(shù)比較，后與被除數(shù)比較，小于小于則再乘則再乘3，小于小于則再乘則再乘4，直至得到的直至得到的結果是結果是大于大于為止為止得到一個商（小于最得到一個商（小于最后一個乘數(shù)的整數(shù)）。后一個乘數(shù)的整數(shù)）。 第三步，將取出的第三步，將取出的部分被除數(shù)部分被除數(shù)（N位或位或N+1位的）減去除數(shù)乘以商的結果，得到位的）減去除數(shù)乘以商的結果，得到“余余數(shù)數(shù)”。 第四步，把余數(shù)作為新的被除數(shù)，將原除第四步，把余數(shù)作為新的被除數(shù)

8、，將原除數(shù)的剩余位補上。數(shù)的剩余位補上。 重復以上操作。重復以上操作。1234567892458=?12342458第一步：從被除數(shù)的左邊取出第一步：從被除數(shù)的左邊取出N位，將其與位，將其與除數(shù)進行逐位比較，得出除數(shù)進行逐位比較，得出大于大于或或等于等于或或小于小于三種結果。三種結果。以上結果為：小于以上結果為：小于1234567892458=? 被除數(shù)追加一位被除數(shù)追加一位1234524581234567892458=?2458 24916 123452458 37374 123452458 49832123452458 51229012345 得到第一個商：得到第一個商：5 用現(xiàn)在的被除數(shù)用現(xiàn)在的被除數(shù)12345減去減去24585的結果，的結果，得到余數(shù)得到余數(shù)12345 12290551234567892458=?1234567892458=? 從原被除數(shù)中乘余