二次篩法 (QS) (実験)

実験1

高速化編 である程度できあがりましたが、データ依存の特性があると大変なのでいくつか実験してみます。実験対象データは大きさを何となく揃えて

$$11629360743077306442685712558623=5195515532454019\times2238345871633717\\ 3744415610430032407516295690131=16256148018281939\times230338429880129\\ 68537341130385531256638307475593=17872053620603069\times3834888960459197\\ 5771575935008051535435704081273=409935203758667\times14079239553199819\\ 67251182482543820029553857590733=15587979931471483\times4314297476529751\\ 6534957630746867139737702348563=10733523989188097\times608836169493779\\ 76718387622433587950305665096229=14343970899438487\times5348476245544867\\ 24420293826778483317984087343343=7396304974565543\times3301688330964601\\ 94806855720177504532123255706081=7574761603887791\times12516150431918191\\ 17844683428259046930588783557747=3399485652339011\times5249230399304977$$

の10個です。1個目はこれまで使っていたものと同じです。ひとまずパラメータも同じ

$$(a,b) = (\sqrt{N}-6000000,\sqrt{N}+6000000)\\ P_0 = 20000$$

で回します。実験結果は

	#FB	#S	#R	篩[秒]	依存解析[秒]	時間合計[秒]
(a)	1108	1471	403	13.5	5.3	18.8
(b)	1127	2809	1687	14.3	12.4	26.7
(c)	1110	1027	15	14.5	3.1	17.7
(d)	1124	1764	661	14.8	6.2	21.1
(e)	1146	4112	2971	17.4	18.1	35.5
(f)	1130	2719	1594	15.3	11.2	26.5
(g)	1141	1529	425	15.6	5.1	20.8
(h)	1122	1112	56	11.5	3.0	14.5
(i)	1135	625	-	14.7	0.9	15.6
(j)	1105	989	-	11.8	2.4	14.3

となりました。#FBはfactor baseの数、#Sはsmoothになったデータ数、#Rはsmoothなデータから出てきた依存関係の式の数です。

考察

この結果とこれまでの実験とを合わせると

• FBの数はだいたい$P_0$（本当は素数定理から$P_0/\log {P_0}$と思われる）に比例するくらいと見積もれる。
• 篩の時間はあまりブレない。（篩う領域幅に依存するものと考えられる。）
• 出てくるsmoothなデータ数は$N$によりマチマチで事前予測は難しい
  • 結果的に出てくる依存関係式がムダに多いことも、足りなくて計算できていないこともある
• 依存解析の時間は出てきたsmoothな関係式に依存。疎行列演算でやっているおかげか$O(\sqrt{n})$より少し大きいくらいに見える。

という感じです。中でも出てくるsmoothなデータ数を見積もれないと分かったことが大きいですね。

対策

さて、この問題に対する対策として篩う範囲の分割を考えました。これは無駄な篩を行うことを削減するだけでなく、逆にある程度の篩が終わってもsmoothなデータが足りない場合は追加で篩うことができるというメリットもあります。また、一括で篩う範囲が小さくなるので作業に必要なメモリ量が減ることが期待されます。

もう少し具体的には、これまでは $x_0=\lceil\sqrt{N}\rceil$ として $x_0\pm6\times10^6$ の$12\times10^6$ 幅で篩っていました。これを今度は $w=10^5$ として

$$w = 10^5\\ x_i = x_0 + (-1)^{i \bmod 2}\lfloor (i + 1)/2\rfloor w$$

として $(x_i, x_i+w)$ を篩います。数式で書くとわかりにくいですが、順番に

i	$\cdots$	3	1	0	2	4	$\cdots$
x_i		$x_0-2w$	$x_0-w$	$x_0$	$x_0+w$	$x_0+2w$

という感じです。篩うごとにsmoothデータのみを蓄積しておき、FBの数を超えた時点で篩を止めます。FB以上にsmoothデータがある、というのは依存解析で最低1つの依存式が出る（自明解である可能性はあるけれど）ことを保証するものです。

さてこの変更^[1]をして実験しましょう。

実験

というわけで実験した結果がこちらです。#B は繰り返した篩いBlockの数なので #B に $w$ をかけることで本質的に篩を書けた幅が分かります。

	#FB	#B	#S	#R	篩[秒]	依存解析[秒]	時間合計[秒]
(a)	1108	84	1110	76	6.7	2.4	9.2
(b)	1127	36	1140	106	3.1	2.6	5.7
(c)	1110	148	1113	90	13.4	2.4	15.8
(d)	1124	69	1127	85	5.7	2.4	8.2
(e)	1146	22	1153	127	2.1	2.5	4.7
(f)	1130	37	1144	112	3.1	2.6	5.7
(g)	1141	83	1144	78	7.4	2.7	10.2
(h)	1122	125	1125	65	8.4	2.6	11.0
(i)	1135	291	1140	69	24.6	2.7	27.3
(j)	1105	150	1106	65	10.5	2.3	12.9

で、結果としては見ての通りFBの数を超えた時点で篩いが終わるのでsmoothデータ数もあまりブレず、依存解析の時間もブレない感じになりました。一方で予想通り篩の時間がバラバラになりましたね。ただこれはFBの数によって変わるのが分かっているので、結局は全体の計算時間は $P_0$ の設定で決まるわけです。

ということで次は桁数ごとの最適な $P_0$ 設定を探索することになります。ちなみにここでの最適とは今の実装で10個くらいの合成数の分解を試した平均時間が最小になりそう、くらいの意味です。理論的には分からないですからね。

実験2：P0の探索

今、桁数と $P_0$ の2つの探索パラメータがありますが、2つ一緒に動かすのは大変なのでまずは $P_0$ だけ動かしましょう。

$P_0$	合計時間[秒]
10000	223.7
20000	129.5
40000	239.9

たまたまですがこの桁数では最初に設定してた $P_0=20000$ くらいが良さそうですね。同様に桁数をずらして確認しましょう。

次の実験対象は 20 桁の素数2個をかけた以下の 5 合成数です。

$$1601798941465291067882890182696890987431=61740539207527213211 \times 25944038747073410021\\ 4235895261589541237660495214113955869221=62654308354408220519 \times 67607405984420429459\\ 3424165404798895007339224419737684398669=54584037418934170193 \times 62731992111875491133\\ 3291026379897089149590993928699881470269=47994671926736535167 \times 68570661029224522307\\ 2470283282588306742357514641908668348561=54706057845686742023 \times 45155571062283632807$$

$P_0$	合計時間[秒]
80000	1193
70000	902
60000	846
50000	844
40000	1111
20000	2573

この桁数だと $P_0$ は 50000～60000 辺りが良さそうです。

とこの辺で二次篩法QSの研究は一旦お開きにしようと思います。次回は複数多項式二次篩法 MPQS をやってみましょう。並列化はその辺りからかな。

脚注

1. TODO：変更内容を書く