多倍長整数の基数変換（2進数→10進数）

今日は数学のおはなしです。
あらかじめ断っておきますが、数学バリバリの人には何の役にも立ちません。

例えば、2進数の11001を10進数にどうやって変換しますか？

授業で習う方法

情報系の教科書に載っている方法は多分こんなかんじだと思います。

1 × 20 = 1
0 × 21 = 0
0 × 22 = 0
1 × 23 = 8
1 × 24 = 16
1 + 0 + 0 + 8 + 16 =25

もちろん理論的には何の問題もありません。
ただ、これだと非常に大きな桁数（100桁とか1000桁とか）の2進数（文字列）を10進数（文字列）に変換するときに加算・乗算で苦労しそうですね。

10進数→2進数

翻って、10進数を2進数に変換するにはどうすればいいでしょうか。
これも情報系の教科書にはこんなやり方が載っていると思います。
例えば13を2進数に変換する場合。

13 ÷ 2 = 6...1
 6 ÷ 2 = 3...0
 3 ÷ 2 = 1...1
 1 ÷ 2 = 0...1

余りを下から連結して、 1101

こちらは、除算さえうまくできれば文字列を連結すればいいのでイイカンジにいけそうです。

10進数→10進数

何いってんだコイツ？と言わないでください。
10進数の123を10進数に変換するには、

123 ÷ 10 = 12...3
 12 ÷ 10 =  1...2
  1 ÷ 10 =  0...1

余りを下から連結して、123

方法はさっきと同じです。余りを連結していくだけ。
これを、最初のテーマである大きな桁数の2進数を10進数に変換する方法に応用してみます。

あらためて、2進数→10進数

2進数の1100111010111を10進数に変換してみます。
桁数は多くないけど無理やり分割して考えます。

下から8桁で区切ると、11001, 11010111です。
区切った2つの数値をそれぞれ10進数に変換すると、25, 215です。

10進数に変換する方法の解説なのにサクッと変換してんじゃねーよというツッコミが来そうですが、ここはあくまで大きな桁数の2進数を10進数に変換するのが目的なので、ある程度小さな桁数（8bitとか）は既に変換できるものと仮定しています。
例えばC++ではstd::stoi()で簡単に変換できます。

はい、そんなこんなで今度は25, 215を頑張って10進数にします。
注意点は、これらは8bitで区切った2つの数値であって、10進数の25215（二万五千二百十五）ではないということです。

基本的には上でやった方法と同じく、10で割った余りを逆順につなげていきます。

25 ÷ 10 = 2...5 → 5 * 28 + 215 = 1495 → 1495 ÷ 10 = 149...5
 2 ÷ 10 = 0...2 → 2 * 28 + 149 =  661 →  661 ÷ 10 =  66...1
 0 ÷ 10 = 0...0 → 0 * 28 +  66 =   66 →   66 ÷ 10 =   6...6
 0 ÷ 10 = 0...0 → 0 * 28 +   6 =    6 →    6 ÷ 10 =   0...6

余りを下から連結して、6615

6615くらいなら16bitで表せる範囲なので、まだstd::stoi()で変換できますが、これが数百桁、数千桁になっても基本の考えは同じ。

多倍長整数の除算さえ実装できればそう難しくなさそうです。

また、区切る桁数については今回は8bitで区切りましたが、実際には変換後の基数（10）より大きいbit数、つまり4bit以上（2⁴=16>10）ならいくつでも構いません。
高速化のために、途中の計算が桁溢れしない範囲で可能な限り大きいbit数で区切るといいでしょう。
具体的には、(10 - 1) × 2ⁿ + (2ⁿ - 1) が桁溢れしない最大のnです。

2進数→10進数の例で説明しましたが、理論的には同じ方法で任意の基数変換ができます。