2001年:多倍長整数計算研究記録

梅谷 武
作成:2001-01-10 更新:2006-01-12
2001年:多倍長整数計算研究記録
IMS:20010110001; NDC:418; keywords:多倍長整数計算, 整数;
目  次
1. 2000年10月以降のまとめ (2001.1.20)
2. 加減算試験 (2001.1.20)
3. 加減算試験(その2) (2001.1.27)
4. 構造改革 (2001.2.10)
5. Karatsuba法の実験 (2001.2.16)
6. 再び古典算法 (2001.2.20)
7. 再びKaratsuba法 (2001.2.21)
8. Toom-Cook法 (2001.3.12)
9. ガロア理論の復習 (2001.8.17)
10. 高速乗算法(1)の設計完了 (2001.9.1)
11. 高速乗算法(1)の性能評価(その1) (2001.9.9)
12. 高速乗算法(1)の性能評価(その2) (2001.9.10)
13. 高速乗算法(1)の浮動小数点演算による実装検討 (2001.9.11)
14. 高速乗算法(2)の設計完了 (2001.9.12)
15. 高速乗算法(2)の性能評価(その1) (2001.9.17)
16. 高速乗算法(3) (2001.9.20)
17. 高速乗算法(4) (2001.9.21)
18. 高速乗算法(5) (2001.9.25)
参考文献
1. 2000年10月以降のまとめ (2001.1.20)
 多倍長整数計算の研究はだいぶ間があいてしまいました。研究日誌の最後の日付を見ると10月25日になっています。この頃の状況を日誌とプログラムでたどってみたいと思います。まず、10月6日に32bit語長のストラッセン-ショーンハーゲ法(以後SS法と書く)をまずC++で実装して正しく計算できることを確認しています。
 10月11日にこれがあまりにも遅いのでこれを高速化するために、古典算法からすべてをアセンブラで書き直す作業を始めています。古典算法のアセンブラ化の過程で、いくつかのやり方を試して、クヌース本の算法をそのままx86に移植するのが一番速いことを実験で確認しています。古典算法のアセンブラ化は10月13日にとりあえず終了していますが、その日の日誌には除算だけはクヌース本のそのままの移植が難しいので、書きやすいやり方に変更したと書いてあります。32bit語長SS法のアセンブラ化は10月23日に終了したのですが、その日の古典算法とSS法との性能比較実験の記録は次のようになっています。
表1: 除算試験480回×10による性能比較
古典算法SS法
5秒98秒
除算試験となっていますが、これは乗算と除算が同時に試験されるようになっているものです。除算は同じルーチンを使っていますので、この差は乗算の違いだけで生じていることになります。
 このSS法の遅さの原因を考えていくとやはり、SS法の型がK=2kとして、
(n,m,ζ)(K,22K+1,24)
となっていることにたどりつきます。(n,m,ζ)型のSS法においては、長さnのFFTと法mの整数演算を行いますが、特に後者の演算に時間がかかりすぎるということが最大の原因です。10月25日の日誌に最終的に次のような結論にたどりついたという記述があります。
命題1.1 (ストラッセン-ショーンハーゲ法の計算量)
 ストラッセン-ショーンハーゲ法の計算量は、その型(n,m,ζ)が与えられたときに
  1. 長さnのFFT算法の計算量
  2. mの整数演算の計算量
により決定される。
 これはある意味ではあたりまえで、原論文はこの計算量を求めて乗算の最適な算法であると結論しているわけです。ただ、実装の対象となる計算機を決めたときに実行時間をクロック単位で見積もるという作業の必要性を認識するにいたったという意味で、これを強調しておくことにします。
 仕事のスケジュールが入ったこともあって、結果的にここまでが昨年の研究成果ということになりました。
2. 加減算試験 (2001.1.20)
 世紀があらたまって、なおかつ昨年末から開発していた文書整形システムXeXがなんとか使えるレベルになったので、C++による多倍長整数計算の研究をそろそろ再開しようと思います。
 昨年11月以降も、仕事の合間にInternet上の資源調査や文献調査は定期的にやっていたのですが、そこで幸運にも次のステップを踏み出すために非常に重要な資源であるNTL[N1]を発見しました。これはC++でかかれた数論のためのライブラリなのですが、1年ぐらい前に見たときには配布制限されていたので、これは使わないことにしていたのですが、今回見たら配布条件が変更されていて、GPL(GNU General Public License)で配布されるようになっていました。
 今日は馴らし運転ということでNTLを実際に使ってみることにしました。1をm回だけ+1した後、m回だけ-1するという簡単な加減算のプログラムで、UBASIC、NTL、S0を比較するという実験を行いました。m=10,000,000のときに結果を次に記します。
表2: 加減算試験1(m=10,000,000)
UBASICNTLS0
1回目61秒42秒108秒
2回目62秒42秒109秒
3回目61秒42秒108秒
 UBASICとNTLの差は、インタプリタとコンパイラの違いということで納得できますが、年が明けたばかりというのに、我S0の108という数字が煩悩の数のように見えます。加減算でこれだけ差がつくというのはまだまだ甘いということですね。一歩前へ進むための方向性がわかったということで今日は満足することにしましょう。
3. 加減算試験(その2) (2001.1.27)
 NTLの圧倒的な速さにえらく刺激されてしまいました。少し気合を入れて、S0のチューンアップ方法をあれこれ考えました。まず、NTLはすべてC++で記述されているのですが、S0ではPentiumの最適化コードをアセンブラで書くと決めて、その方針をまとめました。
多倍長整数算法のPentiumによる最適化
 今週は足し算と引き算をNTL並にしようというのを目標にしたのですが、実験していて気がついたのは、NTLではデータが可変長であるということです。S0は最初から静的にメモリ割り当てするという設計方針でしたので、データは固定長になっています。このため公平な評価を行なうことが難しいのです。評価プログラムによって結果が変わってくるということになります。最適化後の加減算試験1の結果を次に示します。
表3: 加減算試験1(m=10,000,000)
UBASICNTLS0
1回目61秒42秒55秒
2回目62秒42秒55秒
3回目61秒42秒55秒
UBASICを抜いたのですが、まだNTLよりも遅いように見えます。ところがS0のデータ長を最短にすると大体20秒程度で計算できてしまいます。
 いろいろなプログラムで実験してわかったことは、データ長を最適化した場合、S0はNTLの倍ぐらい速く、データ長が冗長であった場合、NTLの方が速くなるときもある、ということです。ここまではあっさりとできてしまったのですが、次の乗除算はなかなか手ごわいと予想されます。あまり高望みすると行き詰まりそうなので、最初は古典算法だけを最適化することにしました。
4. 構造改革 (2001.2.10)
 NTLとの性能比較をより精密にしようと新しいベンチマークプログラムSNBenchを作成しました。これはある特定の処理だけの性能比較ができるようにしたものです。これにより何が原因で差が生じているのかがはっきりわかるようになりました。このテストをやっているうちにS0の設計上の問題点が明らかになってきました。それは、データ配列の無効部分にすべて0をつめておくという原則を作り、その原則に依存するプログラムを作ってしまったことにあります。これにより桁上げや桁揃えのときに次数を大きくするだけで、大きくなった部分を0で埋める作業が必要がなくなったのですが、逆に、すべての処理の最初にデータ無効部分を0で埋めるという処理が必要になってしまいました。そしてこの処理が性能にかなり影響していることがSNBenchでわかってきたのです。
 実はこのことは最初からわかっていたのですが、なるべく楽をしようという誘惑に打ち勝てなくてずっとそのままにしてあったことなのです。いわゆる「問題の先送り」と呼ばれているものと同類ことではなかったかと思います。今回NTLの速さと完成度に大変な刺激を受けました。NTLのおかげでいままでになかったような高いモチベーションをもつことができるようになったと思います。これが「市場競争の原理」と呼ばれているものなのでしょう。やる気がでてきたおかげで、データ構造を変更し、全ソースを見直すと同時に必要な修正を加え、デバッグするという作業、すなわち「構造改革」を2週間かかって何とかやり遂げることができました。
 構造改革後のSNBenchの結果は次のようになりました。
表4: SNBench Ver.0.01(3回平均, 秒単位)
No.項目S0NTL
1加算17.724.3
2減算17.319.0
3加減算119.320.0
4加減算27.515.3
5乗算37.842.3
6除算8.811.0
7乗除算111.022.6
8乗除算215.428.3
9左シフト13.219.6
10右シフト12.918.3
11シフト14.37.6
12シフト21.42.0
13論理和14.322.6
14論理積14.321.6
15メルセンヌ133.250.0
16メルセンヌ217.211.0
 上の結果はある程度満足できるものだと思いますので、プログラムの最適化作業には一旦区切りをつけようと思います。項目15と16のメルセンヌ1、2は、p=4253に対するメルセンヌ素数の判定を行なうもので、前者は割り算を使用し、後者は割り算をシフトと論理積に置き換えたものです。メルセンヌ2はほとんど乗算の性能試験といっていいものです。唯一この項目で劣っていますが、これはS0がnビットの乗算をO(n2)の計算量で行なう古典算法を使っていることによります。
 これからいよいよ高速乗算法の組み込みを行いたいと思いますが、離散フーリエ変換を使う方法はしばらく封印して、まず、簡単な割に効果的であると思われるKaratsuba法から実験してみたいと思います。これがうまくいったらそれをVer.0.01としてGPLで公開いたします。
5. Karatsuba法の実験 (2001.2.16)
 もっとも簡単な高速乗算法であるKaratsuba法[S3]の実験を行いました。SNBenchの結果を示します。
表5: SNBench Ver.0.01(3回平均, 秒単位)
No.項目S0NTL
1加算16.524.3
2減算16.019.0
3加減算119.420.0
4加減算27.515.3
5乗算23.742.3
6除算8.511.0
7乗除算111.022.6
8乗除算220.028.3
9左シフト13.219.6
10右シフト12.918.3
11シフト14.27.6
12シフト21.32.0
13論理和15.522.6
14論理積15.621.6
15メルセンヌ127.250.0
16メルセンヌ210.811.0
 メルセンヌ2がNTLと同等になったことでその効果がわかりますが、乗除算2が遅くなっているのを見てもわかるように必ずしも満足すべき結果とはいえません。実験していて気がついた問題点は、
  1. 再帰関数による実装は簡単ではあるが実行効率が良くない。
  2. 使用するスタック量が事前に予測できないため、大きな桁の乗算でスタック不足が発生する可能性がある。
ということです。現段階ではKaratsuba法をS0に組み込むべきかどうかは判断できませんが、少なくとも現状の実験で使っている再帰関数による実装法は避けたいところです。
 次はKnuthの本[S2]のToom-Cook法を調べる予定ですが、その前にメルセンヌ素数の判定で使われている乗算は平方なので、平方専用の高速算法を組み込んでおこうと思います。NTLはおそらくこれを使っているのではないでしょうか。
6. 再び古典算法 (2001.2.20)
 古典乗法を元にして、平方算法を書いているあいだに古典乗法の最適化に関して新しいアイディアが湧いてきて、古典乗法を書き直しました。平方もそれをベースにして組み込みました。
表6: SNBench Ver.0.01(3回平均, 秒単位)
No.項目S0NTL
1加算16.524.3
2減算16.019.0
3加減算119.320.0
4加減算27.015.3
5乗算32.042.3
6除算8.411.0
7乗除算111.022.6
8乗除算216.928.3
9左シフト13.219.6
10右シフト12.918.3
11シフト14.37.6
12シフト21.42.0
13論理和15.522.6
14論理積15.621.6
15メルセンヌ126.450.0
16メルセンヌ211.011.0
 乗算試験で15%程度速くなりました。古典乗法で被乗数と乗数のポインタを比較して同じであれば古典平方算法を適用するようにして、メルセンヌ1、2はともに前回のKaratsuba法並になってしました。アセンブラによる最適化とはこんなものなのでしょう。ほんのちょっとしたアイディアで1〜2割の差がでてきてしまいます。次はKaratsuba法による平方算法を組み込んで実験してみたいと思います。
7. 再びKaratsuba法 (2001.2.21)
 Karatsuba法に平方を組み込みました。
表7: SNBench Ver.0.01(3回平均, 秒単位)
No.項目S0NTL
1加算16.624.3
2減算16.019.0
3加減算119.420.0
4加減算27.015.3
5乗算19.742.3
6除算8.411.0
7乗除算111.022.6
8乗除算217.528.3
9左シフト13.219.6
10右シフト13.018.3
11シフト14.27.6
12シフト21.22.0
13論理和15.622.6
14論理積16.721.6
15メルセンヌ123.750.0
16メルセンヌ27.911.0
 次はToom-Cook法を調べる予定です。
8. Toom-Cook法 (2001.3.12)
 Toomの原理を確認するために作譜実験を行なってToom-Cook法をS0/math/uint32に組み込むのは構造上難しいという結論に達しました。Cookの方法を使わなくても実装できるのですが、その場合、大量に消費するメモリを節約する算法を独自に考えなければなりません。理論上最適な算法でないものにそれだけの時間を使うのはもったいないと判断しました。
9. ガロア理論の復習 (2001.8.17)
 仕事場を移すという大仕事のために研究をしばらく中断していましたが、やっと一段落して落ち着いてきたので再開することにします。新しい仕事場ではこれまであちこちに分散していた本や資料を一箇所にまとめて整理しました。これが最大の目的だったのですが、実際やってみると実に気持ちがいいものです。またコンピュータ環境を新しくし、それと同時にかねてからの懸案であった過去のファイル資産の分類・整理をやっと実行することができました。これでだいぶ仕事や研究がし易くなります。
 多倍長整数計算の研究の今年のこれまでの成果を簡単に振り返ってみますと、まずプログラムの構造を変えてPentiumによる最適化を行ない、乗算以外はある程度満足できる性能になりました。次に高速乗算法の実装研究に移り、最初のKaratsuba法の実装はかなりうまくいきました。これによって中くらいの大きさの整数の乗算については目標としていたNTLを超えることができました。さらに大きい整数の高速乗算法としてToom-Cook法について実験したのですが効率のいい実装は難しいのではないかという結論になりました。
 次に何をやるべきかということなのですが、少し先を見渡したときに高速乗算法の実装がうまくいった段階で挑戦すべきテーマの一つとして、大きな整数の素因数分解があります。これに関する参考書はすでにいろいろ集めているのですが、この研究を行なうにはどうしても代数的整数論に通じる必要があります。代数学の基礎は学生時代にひととおり学んでいるので、感覚的に代数的整数論を理解し使いこなすにはかなり高度なスキルが要求されるということがわかっています。そこで、今年の夏は代数的整数論を学ぶための第一歩として、代数学の復習を行なうことにしました。実はこれは7月ぐらいからやっていて、今は目標であったガロア理論の復習が大体終わったところです。この夏の残りは高速乗算法の実装研究に使い、ある程度満足できる成果が得られたら、その次の段階として代数的整数論を集中的に学習する予定です。
10. 高速乗算法(1)の設計完了 (2001.9.1)
 この夏はどういうわけか絶好調で、特に理論研究上の収穫が多かったのですが、その最大のものは高速乗算法とは次のような条件を満たす素数pを見つけることであるという認識に至ったことかもしれません。
  1. Fpの演算が実装対象となるCPUで高速に計算できる。
  2. 目的となる数の乗算がいくつかの準同型写像を経由することによってFpの計算に帰着できる。
p = 264 - 232 + 1の場合の高速乗算法の設計が何とか完了しました。現在コーディングの途中なのですが、完成するのにまた1ヶ月ぐらいかかりそうなので、この段階で文書にまとめたものを公開します。(→[S5] 「高速乗算法の設計と実装(1)」)
 高速乗算法(1)という番号を付けた理由ですが、今回いろいろ文献を調べているうちに、上の(A)の条件は、
(A') 目的となる数の乗算がいくつかの準同型写像を経由することによってFpの拡大体の計算に帰着できる。
というように拡張できそうだということがわかってきたからです。
 2進計算機で計算するときの理想的な素数pは、2q-1の形のメルセンヌ素数です。剰余演算がANDと加算だけで計算できるからです。残念なことにpをメルセンヌ素数としたとき、Fp上では離散フーリエ変換の長さnに制約があってそのままでは実用にはなりません。
 長さnの離散フーリエ変換が存在することと1の原始n乗根がその係数体に含まれることは同値です。複素数の場合は代数的閉体ですのでつねに存在します。
 p = 2q - 1がメルセンヌ素数のとき、Fpの2次拡大体であるFp[i],i2 = -1(ガウス整数)にはその長さnの自由度が実用に十分なくらいあるということを、I. S. ReedT. K. Truongが1975年にIEEE Trans-ITに書いた論文で示しています。(リード-ソロモン符号のリードです。まだご健在のようです。)
 それ以後、このことに言及している文献はほとんど見つけることはできないのですが、1990年代後半になって、J. Buhler, M. Shokrollahi, V. Stemannがこれをより一般的な代数体にするような研究を発表しています。彼らの一連の論文はかなり代数学を知らないと読めそうもないのでまだ手をつけていませんが、1年ぐらいかけて代数的整数論を勉強して挑戦してみようと考えています。
 今回の高速乗算法(1)の実装実験が終わったら、次の段階は高速乗算法UとしてFp[i]の計算に帰着させるようなものを実際に設計してみたいと考えています。
11. 高速乗算法(1)の性能評価(その1) (2001.9.9)
 1年前に作ったショーンハーゲ・ストラッセン法のコードを再利用して、高速乗算法Tをコーディングすることができました。剰余演算はアセンブラで書きましたが、FFTを含むキャリーフラグによる桁上げ以外の部分はC++で書きました。デバッグに時間がかかるかなとも思ったのですが、数箇所修正する程度である程度複雑な乗算試験にパスしてしまいました。
 古典算法やKaratsuba法と同様に普通の乗算の他に平方専用の算法も組み込みました。古典算法やKaratsuba法はPentium用に最適化しているので、現段階では勝負にならないのですが、大体の感じを探るために性能比較試験をやってみました。
表8: 乗算法の性能比較[msec]
語長CL法KO法KO/CLM1法M1/CL
24=160.0220.0221.000.29113.2
25=320.0660.0550.830.69210.5
26=640.1760.1260.721.87310.6
27=1280.9800.4400.455.5505.66
28=2562.3101.3700.5917.8513.0
29=51212.604.400.3561.04.84
210=102434.1014.800.44223.06.54
211=2048165.044.00.27845.05.12
212=4096539.0148.00.273394.06.30
 古典算法(CL法)、Karatsuba法(KO法)、高速乗算法(1)(M1法)による平方をなるべく同じ条件で計測し、その時間とCL法との比を並べました。語長が212で終わっているのは、M1法はかなり大量にメモリを消費するために事前に自由メモリ領域からメモリを確保しているのですが、これ以上の語長についてはこの段階でメモリ不足になってしまうからです。また、M1法の実行時にどうもスワップが発生しているようです。
 性能評価に使ったマシンの主な仕様は、ですが、このマシンではM1法の性能評価は無理かもしれません。少なくとも語長が220程度とれないと肝心な部分の性能が測定できません。
 とりあえずメモリの節約と簡単にできる部分の最適化を検討して、実験をメモリ64MBのマシンでやろうと思いますが、最終的にはメモリを1GB程度積んだマシンを用意しないと性能評価は難しいものと思われます。工房を建てたばかりで、すっからかんになっているので頭が痛いところです。
12. 高速乗算法(1)の性能評価(その2) (2001.9.10)
 余白に0を埋めるてすべての係数を計算するのをやめて語長でその係数が0かどうかを判断するように変更し、かなり効果がありました。
表9: 乗算法の性能比較[msec]
語長CL法KO法KO/CLM1法M1/CL
24=160.0220.0271.230.27512.5
25=320.0710.0500.700.6158.66
26=640.1810.1260.701.5998.83
27=1280.9900.4400.444.4404.48
28=2562.3601.3700.5813.135.56
29=51212.104.400.3642.803.54
210=102434.0014.900.44148.04.35
211=2048165.050.00.30543.03.29
212=4096532.0149.00.282092.03.93
 剰余演算がちょうど浮動小数点演算器で誤差無く計算できる範囲であることに気が付きました。これで劇的に速くなる可能性がありますので、明日にでもやってみようと思います。
13. 高速乗算法(1)の浮動小数点演算による実装検討 (2001.9.11)
 昨日の剰余演算がちょうど浮動小数点演算器で誤差無く計算できる範囲であることに気が付いたというのは錯覚でした。Pentiumの浮動小数点演算器では整数は2の補数表現で扱っているので、その変換処理が必要になります。またこれを効率よく実装するためには、データを最初から浮動小数点形式でもつことが必要になり、最初の設計方針に反してしまいます。
 高速化する上での問題点がいろいろ見えてきたので、高速乗算法Tの実装と性能評価には一旦区切りをつけて、次の高速乗算法Uの検討に入りたいと思います。
14. 高速乗算法(2)の設計完了 (2001.9.12)
 高速乗算法(2)は高速乗算法(1)の欠点を改良したもので、本来は(1)という番号にすべきなのですが、ソースファイルや文書の管理上のUという番号付けにしました。メルセンヌ素数M31=231-1についてZM31の2次拡大体であるZM31[i],i2 = -1上の離散フーリエ変換を高速乗算法に応用してみようという試みです。(→[S6] 「高速乗算法の設計と実装(2)」)
15. 高速乗算法(2)の性能評価(その1) (2001.9.17)
 ZM31の2次拡大体ZM31[i],i2 = -1、これはガウスの複素整数Z[i]をイデアル(M31)で剰余したものと同型になりますが、この2次体の演算ライブラリを整備して、原始根やその冪乗である1の原始N乗根を計算する実験にだいぶ時間がかかってしまいました。整数の剰余環と違って、やや複雑な構造をもっているのでコーディングや検算には注意が必要です。
 2次体の計算を実際にコーディングしたのは長いプログラマ人生でも初めての体験でした。特に原始根の探索には時間がかかりました。有限体といってもかなりの大きさですし、なんといっても2次元ですので探索ループが2重になってしまいます。最初は2重ループでしらみつぶしに探索するプログラムを書いて、寝ている間に見つけようとマシン2台で12時間程度検索したのですが見つかりませんでした。実行状況を調べるてみると一順目のループも終わってなかったので一時はあきらめかけました。
 探索プログラムを見直しているうちにミスを発見して、それを修正し、いろいろな値で検算しているうちに偶然12+iという原始根を発見しました。原始根が見つかれば、後は高速乗算法(1)のソースを少し追加・修正するだけですので、2日ぐらいでコーディングとデバッグを終わらせることができました。次表は最初の性能試験の結果です。
表10: 乗算法の性能比較[msec]
語長CL法KO法KO/CLM2法M2/CL
24=160.0220.0281.270.36816.7
25=320.0710.0550.770.78010.9
26=640.1760.1260.721.78610.1
27=1280.9800.3900.404.0604.14
28=2562.3601.3200.569.0603.84
29=51212.704.4000.3519.701.55
210=102434.1015.400.4544.501.30
211=2048159.050.000.3199.000.62
212=4096516.0148.00.29220.00.43
 非常にいいカーブを描いています。2048語でついに古典算法を追い抜きました。
16. 高速乗算法(3) (2001.9.20)
 高速乗算法(3)は高速乗算法(2)において係数を2つに分解しているのをやめて、係数を少し大きなメルセンヌ素数M89=289-1で評価して、ZM89[i],i2 = -1上の離散フーリエ変換で1回で計算してみようという試みです。(→[S7] 「高速乗算法の設計と実装(3)」)
表11: 乗算法の性能比較[msec]
語長CL法KO法KO/CLM3法M3/CL
24=160.0160.0171.060.79649.8
25=320.0500.0541.081.81836.4
26=640.1860.1270.684.21822.7
27=1280.7200.5400.759.89013.7
28=2562.4201.3700.5722.309.21
29=51211.006.1000.5551.104.65
210=102434.0016.000.47113.13.33
211=2048160.049.000.30247.01.54
212=4096517.0148.00.29549.01.06
 高速乗算法(2)は4語と2語の剰余演算に分解していて、高速乗算法(3)は6語の剰余演算を行なっているのですが、やはり細分したほうが速いという結果になっています。
17. 高速乗算法(4) (2001.9.21)
 高速乗算法(4)は係数を3語で評価するところは、Vと同じですが、演算が3語でもいいところが大きな違いです。この詳細は論文にして投稿する予定ですのでしばらく非公開とします。メモリ消費量が減ったため213語まで演算することができるようになりました。
表12: 乗算法の性能比較[msec]
語長CL法KO法KO/CLM4法M4/CL
24=160.0220.0221.000.24711.2
25=320.0710.0490.690.5067.13
26=640.1810.1260.701.1816.52
27=1280.8800.4900.562.7503.13
28=2562.3601.3700.586.1002.58
29=51212.604.4000.3513.801.10
210=102434.0015.400.4531.300.92
211=2048165.050.000.3065.00.39
212=4096516.0148.00.29149.00.29
213=81922114.0500.00.24335.00.16
18. 高速乗算法(5) (2001.9.25)
 高速乗算法(5)は係数を2語と1語に分解したものです。この詳細は論文にして投稿する予定ですのでしばらく非公開とします。
表13: 乗算法の性能比較[msec]
語長CL法KO法KO/CLM5法M5/CL
24=160.0160.0171.060.26316.4
25=320.0550.0490.890.5507.17
26=640.1700.1320.781.2197.17
27=1280.7200.6000.832.8003.89
28=2562.3101.3700.596.1502.66
29=51210.405.5000.5313.801.33
210=102433.5015.400.4630.700.92
211=2048154.049.000.3266.000.43
212=4096532.0149.00.28148.00.28
213=81922054.0494.00.24324.00.16
参考文献
数論
[N1] Victor Shoup, NTL: A Library for doing Number Theory
算法
[S1] 野下 浩平, 高岡 忠雄, 町田 元, 基本的算法, 岩波書店, 1983
[S2] D. E. Knuth(中川 圭介訳), 準数値算法/算術演算, サイエンス社, 1986
[S3] 梅谷 武, Karatsuba法
[S4] 梅谷 武, Toom-Cook法
[S5] 梅谷 武, 高速乗算法の設計と実装(1)
[S6] 梅谷 武, 高速乗算法の設計と実装(2)
[S7] 梅谷 武, 高速乗算法の設計と実装(3)