15.6.1 2進数からの変換

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

2進表現からそれ以外の基数表現に変換するには，これから述べる二つのアルゴリズムのどちらかを利用します。 GET_STR_PRECOMPUTE_THRESHOLD以下のサイズの時には基本的なO(N^2)の方法を使います。 これはb^nで繰り返し除算していきます。ここでbは基数， nは1リム分に収まる最大のべき乗の指数です。 単に剰余rを使う代わりに， 追加的に除算を行うことで，r/b^nを表現する小数リム部分が導出できます。 この時，rの桁数はbを乗じて得ることができます。10進の場合は，特別にコードを記述してあり， 10を乗じる処理をシフトと加算だけ使用して最適実装してあります。

GET_STR_PRECOMPUTE_THRESHOLDを超えるサイズの時には，準2次アルゴリズムを使います。 入力値を tとすると，基数のべき乗b^(n*2^i)が計算され，べき乗がt～sqrt(t)になるまで繰り返されます。 さすれば，tは最大のべき乗で割られるので，べき乗数以上の桁数となる商と，それより小さい剰余が得られます。 この2数は，2番目に大きいべき乗で更に割られて，同様の結果を得ます。これを繰り返して返還を行います。 最終的にはGET_STR_DC_THRESHOLDリムまで値が小さくなった時に，前述の基本アルゴリズムが適用されて終了します。

このアルゴリズムの利点は，デカい数の除算を準2次の分割統治法アルゴリズムで行っていることです (see Divide and Conquer Division)。その結果，この除算のオーバヘッドが単一リムの除算を繰り返すよりも 相対的に小さく抑えられます。どんな場合でも，べき乗b^(n*2^i)の計算が一番コスト高なので 改善が必要です。

GET_STR_PRECOMPUTE_THRESHOLD と GET_STR_DC_THRESHOLDは基本同じものを 表現しており，デカい数の除算を行って入力値を半分にカットするメリットが出る地点を表わしています。 GET_STR_PRECOMPUTE_THRESHOLDは基数のべき乗の計算コストも考慮しており， GET_STR_DC_THRESHOLDはそれを含めた上で，更に再帰呼び出しのコストも考えて設定します。

ベースケースの場合は小さい桁から大きい桁の方に桁導出を行っていますが，やりたいのは 大きい桁から小さい桁への格納（表示）になりますので，格納に必要な桁数，もしくは最低でも過小評価には ならないようにすることが求められます。 GMPでは入力ビット数をchars_per_bit_exactlyをmp_basesから乗じて切り上げることで得ています。 その結果はピッタリ以上の桁数になります。

入力値の大きいビット数のいくつかを調べれば，何桁表示になるかを知ることができるようになりますが，毎回 そうそうピッタリ分かる訳ではなく，大体，100…になるか，99…になるかは末尾の数ビット分が効くわけで，こればかりは実際に99…を出してみるまでは分かりっこありません。

以上述べてきた r/b^nスキームは乗算を使って桁を出しており，1リム以上の数には有用です。 何度か実験をしてみましたが，実装が悪いのか，再帰呼び出ししてもあまり劇的な改善は望めません。 準2乗除算を使っても同じようなものですので，デカい基数べき乗を計算するコストが影響しているのでしょう。

準2乗部分の改善案としては，他にも基数べき乗部分を，商と剰余のサイズのバランスを取るように決めるというものがあります。これは最大のべき乗がb^(n*k)となり，大体sqrt(t)に等しいことから， 2^iには拘らなくても良いということです。計算時間とサイズのグラフを描いてみるとうまく速度向上しているはずですが，実際のところは何とも言えません。