掛け算の研究

2000年にC++多倍長整数クラスを書いてみようと思い立って、多倍長整数の計算について いろいろ調べ始めました。これまでの成果としては高速乗算法の設計法、C++が数値計算 に向いていない理由等がわかってきたことがあります。

高速算法はCあるいはアセンブラで記述して、Cの関数ライブラリとして実装し、C++は わかりやすいユーザーインターフェースを提供するものと考えた方がよさそうです。 しかし、実際に数値実験を行ってみるとC++よりもPythonのようなインタープリタの 方がはるかに使い心地がよく、最近はCの関数ライブラリにPythonのインターフェースを もたせるような方向へ考え方が変わってきています。

2001年
高速乗算法の設計と実装(5)|XML|PDF
高速乗算法(5)は係数を2語と1語に分解する方法である。
高速乗算法の設計と実装(4)|XML|PDF
高速乗算法(3)において係数を分解しない方法の実験を行なったが、剰余演算の語長が6語 であったため、2語と4語に分解した高速乗算法Uよりかなり計算量が多くなった。 高速乗算法Wは係数を分解しないで剰余演算の語長を3語にする。
高速乗算法の設計と実装(3)|XML|PDF
メルセンヌ素数を標数とする2次体上の離散フーリエ変換を使った32bit算術演算器向け 高速乗算法を設計し、Pentiumへの実装を試みる。高速乗算法(2)においては係数を分解 したが、高速乗算法(3)は係数を分解しないで計算する。
高速乗算法の設計と実装(2)|XML|PDF
メルセンヌ素数を標数とする2次体上の離散フーリエ変換を使った32bit算術演算器向け 高速乗算法を設計し、Pentiumへの実装を試みる。
高速乗算法の設計と実装(1)|XML|PDF
ショーンハーゲ-ストラッセン法を俯瞰することによって、多倍長整数の高速乗算法の構造 についてより抽象的な視点で検討し、その応用として32bit算術演算器向け高速乗算法を 設計し、Pentiumへの実装を試みる。
Toom-Cook法|XML|PDF
多倍長整数の高速乗算法であるToom-Cook法についてわかりやすく解説する。
Karatsuba法|XML|PDF
多倍長整数の高速乗算法であるKaratsuba法についてわかりやすく解説する。
多倍長整数算法のPentiumによる最適化|XML|PDF
Pentiumの最適化技術を使って多倍長整数クラスの高速化を試みる。
2001年:多倍長整数計算研究記録|XML|PDF
2001年の多倍長整数計算研究記録
2000年
ストラッセン-ショーンハーゲ法|XML|PDF
多倍長整数の高速乗算法であるストラッセン-ショーンハーゲ法の実装法について検討する。 作譜に必要な個々の算法について見渡した後、32ビット語長の場合について、その主要部分 を算譜としてまとめる。
離散Fourier変換|XML|PDF
離散Fourier変換の概念を可換環R上へ一般化し、複素数上や整数の剰余環上の離散Fourier変換 の性質や高速算法の議論を統一的に行なえるようにすることを目的とする。最初に離散Fourier 変換を可換環R上で定義し、その諸性質を整理する。その上で高速算法について論ずる。
Fourier変換を学ぶ|XML|PDF
Fourier変換の学習記録
C++による代数的構造の表現|XML|PDF
C++の数値計算ライブラリを開発するにあたって、C++によって代数的構造を表現すること について考察します。代数的構造の表現は抽象クラスとして記述され、組み込み型以外の すべてのクラスは、これらから派生させることになります。
2000年:多倍長整数計算研究記録|XML|PDF
2000年の多倍長整数計算研究記録
整数論を学ぶ
[1] 高木 貞治,
 初等整数論講義 第2版
[2] 山本 芳彦,
 数論入門
[3] 松坂 和夫,
 代数系入門
整数の計算
[1] D.E.クヌース,
 準数値算法―算術演算
[2] 木田 祐司, 牧野 潔夫,
 UBASICによるコンピュータ整数論
[4] 和田 秀男,
 コンピュータと素因子分解
離散フーリエ変換
[1] T.W.ケルナー,
 フーリエ解析大全〈上〉
[2] T.W.ケルナー,
 フーリエ解析大全〈下〉
[3] 梅谷 武,
  離散フーリエ変換