15.6.2 2進数への変換

ここに書いてあるのはGMP 4.3以前のアルゴリズムなので，書き直す必要があります。

2のべき乗を基数とする表現から2進数への変換は，簡単で高速な O(N)のビットごとに導出するアルゴリズムが使えます。

それ以外の基数表現から変換するにはこれから述べる2つのアルゴリズムのどちらかを使います。 サイズがSET_STR_PRECOMPUTE_THRESHOLD以下の場合は，基本的なO(N^2)法を使い， n桁ごとにリムに変換します。nは１リムに収まる基数bの最大べき乗です。このグループ をb^nを乗じた結果として保存しておき，足し込んでいきます。Knuth本の4.4 part E (see References)によれば，これで多倍長演算を節約できます。10進からの変換については 特別にコード化しており，コンパイラで10の乗算を最適化できるようにしてあります。

SET_STR_PRECOMPUTE_THRESHOLDを超えるサイズの場合は，準2次アルゴリズムを使い， n桁に分割した最初のグループをリムに変換します。さすれば，前のリムとくっついて x*b^n+yというリムのペアになります。ここでxと yはリムを表わします。この隣り合うリムペアは更に4つのリムに統合されx*b^(2n)+y となります。これを最後の1ブロックになるまで続け，最終結果が返されます。

この方法の利点は，各xに対する乗算がデカいブロックになっていることで，ここにKaratsubaアルゴリズムや 高次の乗算アルゴリズムが適用できるようになります。とはいえ，べき乗b^(n*2^i)を計算するコストは 改善すべきでしょう。 SET_STR_PRECOMPUTE_THRESHOLDは大概大きめにとってあり，大体5000桁ぐらいですが，CPUによっては大きすぎるかもしれません。

SET_STR_PRECOMPUTE_THRESHOLDは入力値を基準に決まっています(10進表現用には最適化してある）が リム数を基準とした方が，基数依存にならず良いかもしれません。 このカウントはベースケースでは使用されませんので，最初に計算しておくか評価しておく必要が出てくるでしょう。

SET_STR_PRECOMPUTE_THRESHOLDを使う理由は，対応する GET_STR_PRECOMPUTE_THRESHOLD よりずっと大きい値になるからで， mpn_mul_1関数は， mpn_divrem_1関数よりずっと高速になります (大体5倍以上）。