多倍長整数ヤバい。マジヤバい。どのくらいヤバいかっていうと、メモリと時間さえ許せば、無限大の整数を表現できるぐらいヤバい。とにかくヤバいと思ったので、自分で作ってみたくなった。でも一から作るほどの腕はないので、どこかのライブラリを参考にしながら(というかパクリながら)実装してみることにした。
参考にしたのはtiny_mpというライブラリ。何よりも感動したのは、ソースがとても軽量。全部合わせても12KB、行数で530行程度。おまけにコードが読みやすい。単語間にはきっちりスペースが空いてて、まるで教科書に載っていそうなコード。
という訳で、現時点で完成しているのは以下の処理。
- 多倍長数同士の比較
- 多倍長数同士の代入、及び多倍長数に符号なし整数を代入
- 多倍長数同士の加算、及び多倍長数に符号なし整数を加算
- 多倍長数同士の減算、及び多倍長数に符号なし整数を減算
- 多倍長数同士の乗算、及び多倍長数に符号なし整数を乗算
- 多倍長数を符号なし整数で除算
多倍長数同士の除算は予想以上に難しいかもしれない。多倍長整数と銘打っておきながらも、実は今実装できてるのは正の整数のみだったりするので、正の整数の実装が全部終わったら、負の整数も扱えるように拡張していきたいな。
自分のコンピュータの上で、65536^100(ビット数で言うと1600ビット, 約4.5*10^481)なんていう途方もない数が動き始めるのは、かなり感動だった。コンピュータの威力を思い知ったね。