在 .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)=1234
5678各box分別取模再聯合(傳統是123456789123456789 ÷ 333=370741108478849 模是72) 那麼重新分配的盒子應該是box(1) =478849 box(2) =370741180 而不能是box(1) =370741180 box(2) = 478849 為什麼? ∵從高位開始取模,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
