高精度計算器算法 (1)

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

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

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

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

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

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

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

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