FLYING

/* TODO: 気の利いた説明を書く */

多倍長整数って凄くね?

多倍長整数ヤバい。マジヤバい。どのくらいヤバいかっていうと、メモリと時間さえ許せば、無限大の整数を表現できるぐらいヤバい。とにかくヤバいと思ったので、自分で作ってみたくなった。でも一から作るほどの腕はないので、どこかのライブラリを参考にしながら(というかパクリながら)実装してみることにした。

参考にしたのはtiny_mpというライブラリ。何よりも感動したのは、ソースがとても軽量。全部合わせても12KB、行数で530行程度。おまけにコードが読みやすい。単語間にはきっちりスペースが空いてて、まるで教科書に載っていそうなコード。

という訳で、現時点で完成しているのは以下の処理。

  • 多倍長数同士の比較
  • 多倍長数同士の代入、及び多倍長数に符号なし整数を代入
  • 多倍長数同士の加算、及び多倍長数に符号なし整数を加算
  • 多倍長数同士の減算、及び多倍長数に符号なし整数を減算
  • 多倍長数同士の乗算、及び多倍長数に符号なし整数を乗算
  • 多倍長数を符号なし整数で除算

多倍長数同士の除算は予想以上に難しいかもしれない。多倍長整数と銘打っておきながらも、実は今実装できてるのは正の整数のみだったりするので、正の整数の実装が全部終わったら、負の整数も扱えるように拡張していきたいな。

自分のコンピュータの上で、65536^100(ビット数で言うと1600ビット, 約4.5*10^481)なんていう途方もない数が動き始めるのは、かなり感動だった。コンピュータの威力を思い知ったね。