数十万文字の長さのベース n (符号なし) 整数があります。
この数値 (ファイルから読み取った文字列) を 2 ～ 256 の基数に変換するにはどうすればよいですか? もちろん妥当な時間で。
GMP ライブラリは、基数 2 ～ 62 のみをサポートします。
1 に答える
5
GMP は、非常に大きな整数に対して巧妙な分割統治基数変更アルゴリズムを使用します。
基本的な考え方が同じものを作るのは難しくありません。基数rと入力番号を呼び出しますx。
それぞれrp[i] = r^(2^i)が元の数の約半分のビット数になるiまで待ちます。rp[i]最後の 1 つを呼び出しますrp[n-1]。モジュロ を減らしますrp[n-1]。次に、上位基数桁は2^(n-1)base-に変換されたものであり、下位基数桁は base- に変換されたものです。一度だけ計算する必要があることに注意してください。rx / rp[n-1]rrx % rp[n-1]rrp
これは、ビット数とビット数ではなく、kビット数を 2 つのほぼビット数に減らすため、一度に 1 桁を抽出するよりも効率的です。k/2log(r)k-log(r)
于 2013-11-10T21:15:42.583 に答える