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

#概要

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

#使用ライブラリ

###[Boost](https://www.boost.org/)

###[GMP(MPIR)](http://mpir.org/)

この測定では膨大な桁数(少なくとも1万桁はある)の**"0以上の整数"**を扱うため、
**uint32_t**や**uint64_t**では桁数が足りません。
そのため、**Boost**の多倍長整数ライブラリである[**"Boost Multiprecision Library"**](https://www.boost.org/doc/libs/1_68_0/libs/multiprecision/doc/html/index.html)を使用します。

[>> 多倍長整数](https://boostjp.github.io/tips/multiprec-int.html)

#測定環境
```cpp
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(高速版)
```cpp: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(簡素版)
```cpp: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`**に変える。

#データ内の用語

```math
\#　メルセンヌ素数番号
```
```math
s^{p}-1　メルセンヌ数
```
```math
t[ms], t2[s], t3[min], t4[h]　測定時間
```
```math
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|

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

###近似式

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

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

##グラフ
![lltf.png](https://qiita-image-store.s3.amazonaws.com/0/213065/d1fc692c-7d62-ea61-60d8-0c0e133bdd5d.png)

#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|

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

###近似式

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

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

##グラフ
![llt.png](https://qiita-image-store.s3.amazonaws.com/0/213065/5f5a726b-8551-27e0-ec2e-585a818b2b2c.png)


#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|


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

###近似式

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

##グラフ
![lltfg.png](https://qiita-image-store.s3.amazonaws.com/0/213065/4184bcd9-591d-8bff-c05d-580cc9db9302.png)


#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|

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

###近似式

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

##グラフ
![lltg.png](https://qiita-image-store.s3.amazonaws.com/0/213065/48c874d4-399a-431d-298d-7d25ccab97df.png)

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

These codes are licensed under CC0.
[![CC0](https://mirrors.creativecommons.org/presskit/buttons/88x31/svg/cc-zero.svg "CC0")](http://creativecommons.org/publicdomain/zero/1.0/deed.ja)

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