非常大的整數乘法和加法

Question

問候，

我需要乘以存儲在一個文本文件中的兩個極長整型值（通過GMP（MPIR出口，是精確的），這樣他們就可以是任何的任何基地） 。現在，我通常只需通過mpz_inp_str（）函數導入這些整數，然後在RAM中執行乘法運算，但這些值太長以至於我無法真正加載它們（每個數據大約爲1 GB）。什麼是最快的方式來做到這一點？也許有一些外部庫已經做這種事情了？是否有任何易於實現的方法（性能不是非常重要，因爲此操作只能執行一次或兩次）？

tl; dr：我需要將值乘得這麼大才能適合進程內存限制（Windows）。

謝謝你的時間。

Answer 1

我不知道是否有一個庫支持這個，但是你可以在每個真正大數的部分（RBN）上使用GMP/MPIR。也就是說，首先將每個RBN分成可管理的，統一大小的塊（例如10M數字塊，對於最高有效數字期望小塊，下面也見到）。

 
    RBN1 --> A B C D E 
    RBN2 --> F G H I J 

的組塊可在基座10來完成，所以只讀< chuck_size從對於每條文件>字符。然後每次乘以每個數字的塊。

 
    AxF BxF CxF DxF ExF 
    + AxG BxG CxG DxG ExG 
    +  AxH BxH CxH DxH ExH 
    +   AxI BxI CxI DxI ExI 
    +    AxJ BxJ CxJ DxJ ExJ 

在內存中執行最終總和的每一列。然後，將進位保留在內存中，將列寫出到磁盤中，重複下一列...對於進位，將每列和結果轉換爲帶GMP的字符串，寫出結果的底部<塊大小>部分並讀取頂部作爲進口的GMP int返回。

我建議爲每個乘法動態選擇一個塊大小，以保持每列添加內存;數字越大，需要添加的列數越多，塊大小就需要越小。 （注意，這不會加載整個文件，它只是基本上緩衝了虛擬內存上的IO）。對於讀寫，我建議使用內存映射文件，boost有一個很好的界面this（注意，這不會加載整個文件。爲每個輸入的RBN編號打開一個映射文件，以及size = size（RBN1）+ size（RBN2）+ 1的一個輸出;使用內存映射文件時，文件訪問被視爲原始char *，因此您可以使用gmp c-string io方法直接讀/寫塊。您可能需要讀入中間緩衝區才能使用GMP的NULL終止字符串（除非您想臨時更改內存映射文件）。

這不是很容易正確實現，但是這又不是一個特別簡單的問題（可能只是單調乏味）。這種方法的優點在於它完全反映了GMP在內存中的作用，所以算法是衆所周知的。