More than 5 years have passed since last update.

素数判定の速度測定データ一覧

Last updated at 2018-12-29Posted at 2018-09-26

#概要

この記事は"【Qiitaで最も大きい素数を判定】高速メルセンヌ素数判定プログラム"の記事で得られたデータをもとに素数判定にどの程度の時間がかかるのか、記載します。

#使用ライブラリ

この測定では膨大な桁数(少なくとも1万桁はある)の**"0以上の整数"を扱うため、
uint32_tやuint64_t**では桁数が足りません。
そのため、Boostの多倍長整数ライブラリである"Boost Multiprecision Library"を使用します。

>> 多倍長整数

#測定環境

PC: "HP Spectre x360 Convertible 13-ac0XX"
CPU: Intel Corei7-7500U '@' 2.70GHz 2.90GHz
RAM: 16.0GB
ROM: SSD 512GB
IDE: VisualStudio Community 2017
Compiler: cl;  C/C++ Compiler 
Compiler File version: 19.15.26729.0
Compiler Product version: 14.15.26729.0

#実装コード

###lucasLehmerTestFast(高速版)

lucasLehmerTestFast

bool lucasLehmerTestFast(const int_fast32_t p_) {
	mp::cpp_int m = 1;
	m <<= p_;
	--m;
	mp::cpp_int s = 4;
	mp::cpp_int sqrt;
	for (int_fast32_t i = 2; i < p_; ++i) {
		sqrt = s * s;
		s = (sqrt & m) + (sqrt >> p_);
		if (s >= m) s -= m;
		s -= 2;
	}
	if (s == 0) return true;
	return false;
}

###lucasLehmerTest(簡素版)

lucasLehmerTest

bool lucasLehmerTest(const int_fast32_t p_) {
	mp::cpp_int m = 1;
	m <<= p_;
	--m;
	mp::cpp_int s = 4;
	for (int_fast32_t i = 2; i < p_; ++i)
		s = (s*s - 2) % m;
	if (s == 0) return true;
	return false;
}

これはBoostのコード。
m(メルセンヌ数)が素数か調べ、素数ならば"true"、素数でないならば**"false"を返す。
GMPの場合はmp::cpp_intの部分をmpz_class**に変える。

#データ内の用語

\#　メルセンヌ素数番号

s^{p}-1　メルセンヌ数

t[ms], t2[s], t3[min], t4[h]　測定時間

tt[ms], tt2[s], tt3[min], tt4[h]　推定時間

#Boost(lucasLehmerTestFast)

#	p	t[ms]	tt[ms]	t2[s]	tt2[s]	t3[min]	tt3[min]	t4[h]	tt4[h]
20	4423	241	195.9478738	0.241	0.195947874	0.004016667	0.003265798	6.69444E-05	5.443E-05
21	9689	1942	2006.401193	1.942	2.006401193	0.032366667	0.03344002	0.000539444	0.000557334
22	9941	2121	2165.197758	2.121	2.165197758	0.03535	0.036086629	0.000589167	0.000601444
23	11213	2973	3094.717709	2.973	3.094717709	0.04955	0.051578628	0.000825833	0.000859644
24	19937	16232	17063.26273	16.232	17.06326273	0.270533333	0.284387712	0.004508889	0.004739795
25	21701	21013	21942.61707	21.013	21.94261707	0.350216667	0.365710284	0.005836944	0.006095171
26	23209	25298	26781.87939	25.298	26.78187939	0.421633333	0.446364657	0.007027222	0.007439411
27	44497	177123	184669.1586	177.123	184.6691586	2.95205	3.077819309	0.049200833	0.051296988
28	86243	1398378	1315061.524	1398.378	1315.061524	23.3063	21.91769206	0.388438333	0.365294868
29	110503	2849994	2743408.181	2849.994	2743.408181	47.4999	45.72346968	0.791665	0.762057828
30	132049	4969037	4653524.217	4969.037	4653.524217	82.81728333	77.55873695	1.380288056	1.292645616
31	216091	20601900	20059539.73	20601.9	20059.53973	343.365	334.3256621	5.72275	5.572094369

###計算量

計算量：O(n^{3})

###近似式

t≈3^{-9}×p^{2.9665}　(t≒3^{-9}×p^{2.9665})

t≈3^{-9}×p^{3}　(t≒3^{-9}×p^{3})

##グラフ

#Boost(lucasLehmerTest)

#	p	t[ms]	tt[ms]	t2[s]	tt2[s]	t3[min]	tt3[min]	t4[h]	tt4[h]
20	4423	664	583.9090905	0.664	0.58390909	0.011066667	0.009731818	0.000184444	0.000162197
21	9689	5775	5975.166465	5.775	5.975166465	0.09625	0.099586108	0.001604167	0.001659768
22	9941	6301	6447.938392	6.301	6.447938392	0.105016667	0.10746564	0.001750278	0.001791094
23	11213	8951	9215.152303	8.951	9.215152303	0.149183333	0.153585872	0.002486389	0.002559765
24	19937	38686	50785.95279	38.686	50.78595279	0.644766667	0.846432546	0.010746111	0.014107209
25	21701	65347	65304.10699	65.347	65.30410699	1.089116667	1.088401783	0.018151944	0.01814003
26	23209	78262	79702.10278	78.262	79.70210278	1.304366667	1.32836838	0.021739444	0.022139473
27	44497	557699	549284.0149	557.699	549.2840149	9.294983333	9.154733581	0.154916389	0.152578893
28	86243	4146876	3909477.76	4146.876	3909.47776	69.1146	65.15796267	1.15191	1.085966044
29	110503	8196264	8154117.867	8196.264	8154.117867	136.6044	135.9019645	2.27674	2.265032741
30	132049	13757184	13829505.3	13757.184	13829.5053	229.2864	230.4917549	3.82144	3.841529249
31	216091	0	59590154.19	0	59590.15419	0	993.1692365	0	16.55282061

###計算量

計算量：O(n^{3})

###近似式

t≈9^{-9}×p^{2.9657}　(t≒9^{-9}×p^{2.9657})

t≈9^{-9}×p^{3}　(t≒9^{-9}×p^{3})

##グラフ

#GMP(lucasLehmerTestFast)

#	p	t[ms]	tt[ms]	t2[s]	tt2[s]	t3[min]	tt3[min]	t4[h]	tt4[h]
20	4423	41	49.32975395	0.041	0.049329754	0.000683333	0.000822163	1.13889E-05	1.37027E-05
21	9689	235	288.8015433	0.235	0.288801543	0.003916667	0.004813359	6.52778E-05	8.02227E-05
22	9941	270	306.0058077	0.27	0.306005808	0.0045	0.005100097	0.000075	8.50016E-05
23	11213	351	401.3972133	0.351	0.401397213	0.00585	0.006689954	0.0000975	0.000111499
24	19937	1282	1468.366947	1.282	1.468366947	0.021366667	0.024472782	0.000356111	0.00040788
25	21701	1607	1777.509835	1.607	1.777509835	0.026783333	0.029625164	0.000446389	0.000493753
26	23209	1892	2068.066892	1.892	2.068066892	0.031533333	0.034467782	0.000525556	0.000574463
27	44497	7928	8966.013568	7.928	8.966013568	0.132133333	0.149433559	0.002202222	0.002490559
28	86243	39897	39835.3406	39.897	39.8353406	0.66495	0.663922343	0.0110825	0.011065372
29	110503	76168	69641.65059	76.168	69.64165059	1.269466667	1.160694176	0.021157778	0.019344903
30	132049	111715	104042.2927	111.715	104.0422927	1.861916667	1.734038211	0.031031944	0.028900637
31	216091	347218	315688.2918	347.218	315.6882918	5.786966667	5.26147153	0.096449444	0.087691192
32	756839	3888237	5321616.199	3888.237	5321.616199	64.80395	88.69360332	1.080065833	1.478226722
33	859433	5237340	7086984.375	5237.34	7086.984375	87.289	118.1164063	1.454816667	1.968606771

###計算量

計算量：O(n^{2.25})

###近似式

t≈3^{-7}×p^{2.2536}　(t≒3^{-7}×p^{2.2536})

##グラフ

#GMP(lucasLehmerTest)

#	p	t[ms]	tt[ms]	t2[s]	tt2[s]	t3[min]	tt3[min]	t4[h]	tt4[h]
20	4423	110	119.203999	0.11	0.119203999	0.001833333	0.001986733	3.05556E-05	3.31122E-05
21	9689	827	975.9773977	0.827	0.975977398	0.013783333	0.01626629	0.000229722	0.000271105
22	9941	845	1045.536629	0.845	1.045536629	0.014083333	0.01742561	0.000234722	0.000290427
23	11213	1161	1443.9399	1.161	1.4439399	0.01935	0.024065665	0.0003225	0.000401094
24	19937	5065	6756.283134	5.065	6.756283134	0.084416667	0.112604719	0.001406944	0.001876745
25	21701	6280	8480.728132	6.28	8.480728132	0.104666667	0.141345469	0.001744444	0.002355758
26	23209	7600	10154.64107	7.6	10.15464107	0.126666667	0.169244018	0.002111111	0.002820734
27	44497	59934	58156.62385	59.934	58.15662385	0.9989	0.969277064	0.016648333	0.016154618
28	86243	304988	342914.91	304.988	342.91491	5.083133333	5.715248499	0.084718889	0.095254142
29	110503	565614	666544.096	565.614	666.544096	9.4269	11.10906827	0.157115	0.185151138
30	132049	870280	1074625.307	870.28	1074.625307	14.50466667	17.91042179	0.241744444	0.29850703
31	216091	2789054	4025235.774	2789.054	4025.235774	46.48423333	67.0872629	0.774737222	1.118121048

###計算量

計算量：O(n^{2.68})

###近似式

t≈3^{-8}×p^{2.6813}　(t≒3^{-8}×p^{2.6813})

##グラフ

##ソースコードのライセンス

These codes are licensed under CC0.

ソースコードは自由に使用してください。

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up