複数多項式二次篩 １２．２８　川原　未鈴.

Presentation on theme: "複数多項式二次篩 １２．２８　川原　未鈴."— Presentation transcript:

1 複数多項式二次篩 １２．２８　川原　未鈴

2 目次 １、実験① ２、実験② ３、ガウスの消去法について ４、今後

3 実験環境 ハードウェア CPU: AMD Phenom(tm) Ⅱ X6 1090T Processor (3.2GHz 6cores) Memory: 8GB Disk: HDD 2TB, SDD 64GB システム Server: Windows Server 2008 R2 Standard Emulator: VMware(R) Player Ver Linux OS: CentOS (CPU: 4cores, Memory: 2GB, HDD: 200GB )

4 実験① ・NZMATHにある熊木さんのプログラムで実験 ・５０桁から６０桁の合成数について実験 ・それぞれの実験の対象となった合成数は ほぼ同じ桁数の素数２つの積であるような数とした ・各桁の１０個の合成数に対し,平均時間を算出

5 実験結果 ５０桁の実験は終了したが、出てきた時間がマイナスになっているものがあり、正確なタイムはわからない。 マイナスになった原因はArithのCPUTimeが大体４０００秒までは正確に測れるがそれ以上は正確には測れないため。 Komeyaも同じ性能。

6 ２、実験② ・NZMATHにある熊木さんのプログラムで実験 ・１０、１５、２０、２５、３０、３５、４０桁の合成数について実験 ・それぞれの実験の対象となった合成数は ほぼ同じ桁数の素数２つの積であるような数とした ・過程の中を （ⅰ）係数を決める（ⅱ）篩う （ⅲ）𝐵−𝑠𝑚𝑜𝑜𝑡ℎな𝑄(𝑥)を得る（＝（ⅰ）＋（ⅱ）） （ⅳ）ガウスの消去法（ⅴ）total に分けてそれぞれの時間を出す ・各桁の１０個の合成数に対し,それぞれの平均時間を算出

7 実験結果 10桁 １５桁 20桁 25桁 30桁 35桁 40桁 Time of deciding coefficient 0.001
0.048 0.2425 0.74 Sieving Time 0.008 0.0475 0.148 3.7425 80.105 Total time of getting enough smooth numbers 0.009 0.21 4.4825 Time of Gaussian Elimination 0.002 0.052 1.6825 Total time 0.019 0.0725 0.358 1.9825 8.34 43.08

8 ・３５桁まではガウスの消去法より篩いのほうに時間がかかっている ・Total Timeは５桁ごと上がるごとに大体５～６倍増えている → ５０桁では約６０００秒？ ・係数決め、篩い、ガウスの消去法以外のところでも桁数が上がるごとに時間がかかっている

9 ２、ガウスの消去法について ・先生からガウスの消去法の改良を提案されたが、codeを見たら先生の言っていた通りになっていた

10 ３、今後 どこかを改良する or どのくらい使えるのかを詳しく調べる 篩いの範囲について考える