在.NET 開發中,有時會因為處理一些邊緣學科的知識內容,如統計,金融,天文等計算,是加密解密演算法都會涉及到大數的運算,就是.net中最大數值類型儲存了都會溢出的數,我的一個想法是計算時用數值類型,儲存(暫時)和輸出時是字串那麼儲存時就需要BOX[n] n個陣列來暫時儲存一個計算中的小步驟結果,
'如一下例子
====================演算法理解圖=========================
'97*97*97*97*97 = 8587340257 box(1) = 587340257 box(2)=8
'97*97*97*97*97*97 = 832972004929 box(1) = 972004929 box(2)=832
'97*97*97*97*97*97*97 = 80798284478113 box(1) = 284478113 box(2)=80798
'97*97*97*97*97*97*97*97 = 7837433594376961 box(1) = 594376961 box(2)=7837433
'97^ 9 = 760231058654565217 box(1) = 654565217 box(2)=760231058
'97^ 10 = 73742412689492826049 box(1) = 492826049 box(2)=742412689 box(3)=73
…… …… …… ……
注意box 下表越大對應的數越高位在,在運用上面的算法時要記住①先定義一個BOX的標誌為幾位,如上面是9位(根據需要和實際情況),
②由於計算習慣,很多人會從底位算起時{box(0 -> n)} 要先算box(n+1)位的數,在把box(n) 產生的進位數(如第一條計算box(1)向box(2)=0產生進位數8 box(2)+進位數= 8 )進行處理,如以上時加法處理③ 最好從高位算起,你將省去很多麻煩, box個數未知,沒關係,用動態數組,滿了時(最高下標box產生的進位數)再添一個還有取模運算時,如果模數不大,也可以採用以上思想分段求模,再鏈接box得暫時結果,重新分配box(一定要從高位起重新截斷)如被模數123456789123456789 設八位一個box box(1)=89 box(2)=91234567 box(3)=12345678box(2)=91234567 box(3)=12345678box再聯合(傳統是123456789123456789 ÷ 333=370741108478849 模是72) 那麼重新分配的盒子應該是box(1) =478849 box(2) =370741180 而不能是box(17074 ∵從高位開始取模,box(n) 在被取模一次後如果不變,再次取模結果沒變是box(n) = box(n) 程式將進入死循環
另外一種涉及大數運算的情況式是對A的n 次方後取模(A ^n mod V ) 如果mod數不大可以(是n個A後結束)((A mod V)* A mod V) * A mod V …… 此演算法不一定要用遞歸實現,簡單的循環即可,最多兩層嵌套循環
最後忠告:對一個大數進行加減乘除時千萬別輕易的進行對被(加/減/乘/除)數因式分解,這種演算法效率會很底
(文章編寫匆忙,可能存在錯字,敬請原諒)
出處：same BLOG