多倍長整数の解説執筆がいつまで経っても進展しないので、お詫びの印にガイドを書いてみる
- 実装が欲しいよ派（実用主義派）
-
- お金は掛けたくないよ派
-
GMPとか、Mintはどうでしょうね。前者は開発者もユーザーも多いのでその点で信頼性が期待できますし、かなり速いです。後者は、x86限定ですが、ドキュメントも日本語ですし分かりやすく、設計上も使いやすい感じです。作者の苫米地聰さんは数体篩い法の実装などで知られる、計算実験に関してはかなり凄い人です。
あるいは、いっそPythonインタプリタやGaucheを埋め込んでしまうのはどうでしょうね。どちらもCプログラムに埋め込み易く書かれていますし、元来は汎用のスクリプティング言語ですから、アプリケーションにマクロ言語機能も付けられるというおまけがあってお得な感じです。アプリケーションのマクロ言語としてはRubyは最高と思うのですが、如何せん、現Ruby実装はインタプリタのインスタンスが1個しか作れなかったり、マクロ言語として埋め込むには難しい点もあります。
- 只のものなんて信用できないよ派（サポート欲しい派）
-
えっと、GMPやPythonの多倍長整数実装と同等以上に信頼できて、サポートが付く……。高そうですねぇ。GMPを使って自前でサポートするんじゃ駄目ですか？ 開発もそれなりに活発みたいですよ、あそこは。担当者にGMPを理解させる時間がない？ 困りましたねぇ
- 仕組みを理解したいよ派
-
- 大学のレポートだよ派
-
うちのサイトのドキュメントを読み終わったら、黙ってKnuth読みましょう。最近出た新しい翻訳です。前の翻訳本はサイエンス社のやつです。そういうレポートが出る大学なら多分どっちかは図書館にあります。該当部分はそんなに多くないので、そこだけコピーしてとにかく読みましょう。
もし、Karatsubaあたりまで必要なのであれば多倍長演算についてを読むのも良いと思います。
- 新人研修だよ派
-
会社があなたに求めているスキルは、うちのサイトの実装を読んで理解できる程度の水準と思われます。それなりにドキュメントは書いたつもりなので、頑張れ。
- 趣味だよ派
-
とりあえず、前述のKnuthは持ってて損はないです。もう持ってらっしゃる可能性大ですが。
それから、多倍長演算についてや梅谷さんのIMSを読みましょう。理論面ではかなり突き詰めて書いてあります。
書籍ではアセンブラを使わないC++による多倍長計算—高速フーリエ変換使用なんてのもありまして、ぱっと見、期待できそうな感じてはありますが、読んだことはないので何とも言えません。
Knuth片手にMintを読むのも勉強になります。実装だけなら、うちのサイトのものも参考程度にはなるでしょう。その他の日本語圏の実装としては、tiny_mpとか、技術計算用Ｃプログラム ソースとかもあります。いずれもソースを参照して勉強するのに悪くないと思います。
自前で実装するなら、UBASICを超えるのを目標にしましょう。とにかく整数計算が速いです。コンパイラインタプリタですらない古典的BASICインタプリタにも関わらず、下手なC言語実装をすると速度で負けます。
