FLYING

〈全日本・紀文豆乳飲料シリーズ「麦芽コーヒー」の500ミリリットルパックを扱う小売店が少ないことに遺憾の意を表明する会〉活動記録

多倍長整数って凄くね?

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

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

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

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

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

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