多倍長整数の基数変換（Karatsuba基数変換法）

前回は多倍長整数の基数変換方法を説明しました。
今回は、もうちょっと高速化できないか考えてみます。

16進数→2進数

ところで、16進数を2進数に変換するにはどうすればいいでしょうか。
deadbeefを2進数に変換する場合、

d = 1101
e = 1110
a = 1010
d = 1101
b = 1011
e = 1110
e = 1110
f = 1111

頭から連結して、11011110101011011011111011101111

前回と打って変わって簡単ですね。
こんなに簡単なのは、16=2⁴で、2進数の4桁を過不足なく16進数1桁で表現できるからです。

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

同じような考えは10進数にも適用できます。
前回と同じく、1100111010111を変換していきます。

前回と同じように、まず下から8桁で区切ると、11001, 11010111です。
区切った2つの数値をそれぞれ10進数に変換すると、25, 215です。
ここまでは前回と同じですが、今度は100で割っていきます。

25 ÷ 100 = 0...25 → 25 * 28 + 215 = 6615 → 6615 ÷ 100 = 66...15
 0 ÷ 100 = 0... 0 →  0 * 28 +  66 =   66 →   66 ÷ 100 =  0...66

下から連結して、6615

前回は4行にわたって計算をしましたが、今回は2行で済みました。
つまり計算量が半分になりました。

除数を100ではなく1000や10000にすれば、計算量がそれぞれ3分の1、4分の1になります。

これをKaratsuba基数変換法と言うらしいです。からつば先生が考えたそうな。