多倍長整数演算:基数変換(続)

大体Knuthの内容が理解できた。本を返さなきゃならないのでメモっておこう。
とりあえず分かり易いように二進数<=>十進数の変換に限定して書いとく.(他の基数でもほとんど同じ)

まず進数に変換

普通の基数変換では、多倍長整数uがあった場合これを次々と10で割る(2で割る)ことによって各桁の数を求める。でもそれだと多倍長の除算を繰り返す事になり非効率。
そこで、一度10^n進数に変換して単精度の変換をするようにする。
一桁がunsigned long型(仮に4バイト)だとすると10^n <= 2^32であれば良いので10^9進数に一度直す。
これは元が10進数なら9桁ずつ区切ってその値を計算するだけ。*1

単精度の変換

単精度の変換には四つの方法があるらしい。
とりあえず整数限定なのでKnuthに書いてあった1aと1bの方法を書いておく。

2進 => 10進の変換(内部表現を文字列に直す場合)

1a. 10で次々割る。これはごく普通の方法。下の位から順に得られる。
例えば01111011(123)を十進に直す場合

123/10 = 12, 123%10 3
 12/10 =  1,  12%10 2
  1/10 =  0,   1%10 1

ちなみに2aの方法も面白いので書いておく。
今の例だと、まず123を0.123に直す。そして小数部分を次々10倍して整数部分を取り出す。

123 => 0.123
0.123 * 10 = 1.23 => 1
0.23  * 10 = 2.3  => 2
0.3   * 10 = 3.0  => 3

この方法の利点は

1. 除算を使わないので1aの方法より少し早い。
2. 上の位から順番に得られるので、上の桁から順番に表示するとかできる。

10進 => 2進の変換(文字列を内部表現に直す場合)

1b. まず10進数=>10^n進数の変換で元の数が

と変換できたとする。
これを次の様に計算していく(Horner法)。もちろんここは多倍長で計算。
[tex:*2

*1:RubyのBignumは一桁2バイト以上の場合にここを10^4にしてるみたい。Bignumは36進までの変換を提供しているので一桁4バイトの場合、nは最大で36^n <= 2^32 => n=6までいけるはず。一桁が3バイトなんて環境があったりするとか...???

*2:\cdots(u_mb+u_{m-1})b+\cdots)b+u_1)b+u_0)] これで元の数の内部表現が得られる。 ((Rubyでは10^n進への変換は行わず、10進のままこの計算を行っている。複数の基数に対応しているのが理由だと思うけど、もっと効率よくできないのかな?きっと十分議論がされてて、これがベストなんだろう。自分にはまだまだ分からない(^^;