June 11, 2010

Preface in Japanese : R.P.Brent & P.Zimmermann, "Modern Computer Arithmetic" Ver.0.5.1

 現物は著者のページから見て欲しい。以下の前書きは0.5.1版からの訳出である。

----------------
まえがき

 本書は数値演算のアルゴリズムと,現代のコンピュータ上でそれを実装する方法について解説したものである。我々はどちらかというとハードウェアよりソフトウェアの方に興味があるので,コンピュータのアーキテクチャとかハードウェアのデザインについては本書では触れていない。その手のトピックを扱った良書がすでにいくつか存在しているからでもある。その代わりと言っては何だが,加減乗除といった演算を高速に実行したり,それと関連したモジュラー演算,最大公約数計算,高速フーリエ変換(FFT),特殊関数の計算のようなトピックに焦点を当てて解説を行っている。
 本書で示したアルゴリズムは,任意精度演算向けのものがメインである。つまり,32ビット,64ビットというコンピュータのワードサイズに固定された桁の計算ではなく,メモリと計算時間の制限内でできる限りの桁数の計算に対応している。整数演算だけでなく,実数(浮動小数点数)演算についても述べてある。

 本書の構成は4章+短い1章(実質的には付録扱い)から成る。第一章は整数演算についてであるが,これについてはもちろん,いろんな本や論文で扱われているものである。しかし,公開鍵暗号研究における貢献によって,近年著しく進展している分野であるため,多くの既存の本の記述は一部,時代遅れになっていたり,不完全になっていたりする。我々は,この進化した部分について,なるべく簡潔に記述しようと試みた。同時に,必ずしもこの分野に精通していない読者にも,自学自習ができるような自己完結した入門編となるよう心がけた。
 第二章は,モジュラー演算とFFT,コンピュータ演算への応用に関することを扱っている。さまざまな数の表現方法,高速乗算・除算・べき乗算法,中国剰余定理(CRT)の使用方法について議論している。
 第三章は浮動小数点演算を扱う。ハードウェアで提供されている精度(IEEE754 53ビット倍精度など)では不十分な場合に,より高い精度の浮動小数点数演算をソフトウェアで実装することを考える。この章で扱うのは,IEEE754規格を任意精度浮動小数点演算に拡張した,"正確な丸め"(Correctly Rounded)を可能にするアルゴリズムである。
 第四章では,べき級数や連分数で定義される,任意精度の初等関数(sqrt, exp, ln, sin, cosなど)の計算法を扱う。特殊関数は膨大なボリュームのあるテーマなので,部分的に取り上げるだけにしてある。任意精度計算に相応しい,高性能な計算方法のみに集中して解説した。
 最終章は,実装されたソフトウェア,有用なWebサイトやメーリングリストなどを紹介している。最終ページでは,有用な"aide-memoir"となるべく,「計算量のまとめ」を行っている。
 以上の章は,それぞれ章ごとに自己完結しているので,どういう順番で読んでもらって構わない。例えば,第四章を第一章~第三章より先に読むこともできるし,いつも第五章だけを参照する,という使い方もできる。Newton法のように,いくつかのトピックは,複数の章で異なる取り上げ方をしていたりすることもある。また,相互参照は必要な場所で適宜行っている。

 あえて飛ばした詳細については,参考文献と同様,各章の"Notes and References"でその情報へのポインタを示してある。できる限り本文がすっきり読めるよう,注釈や参考文献を使用しているので,ほとんどの参考文献は"Notes and References"の節に押し込めてある。

 本書は,高性能なコンピュータ演算の設計に興味のある人だけでなく,もっと一般の数値計算アルゴリズムを高性能にしたい人も対象として書かれている。読者個人が好きなコンピュータ言語を使って実装できるよう,できるだけ抽象度を上げて記述し,具体的に,特定マシンに依存するような記述は避けた。アルゴリズムのアルファベット順のリストは索引に載せてある。

 本書は特別,教科書を意図して書かれたものではないので,数学専攻,コンピュータ科学専攻の大学院生レベルでないと難しいように思われる。扱っているトピックも長々と解説したりせず,演習問題として各章の最後にまとめてあるが,この難易度は恐ろしいほど幅があり,簡単なものから,ちょっとした研究プロジェクトレベルのものまであるが,それを順位付けしたりはしていない。演習問題の解答を知りたければ,著者である我々に連絡をして頂きたい。

 コメントやバグの報告はいつでも歓迎したい。著者のどちらかに送って頂ければ幸いである。

Rechard Brent
Paul Zimmermann
キャンベラとナンシーにて
2010年2月
----------------

 多倍長計算向けのアルゴリズム本って,少ないんだよね。1.0を楽しみに待ちたい。

Posted by tkouya at June 11, 2010 12:32 AM