C言語、C#, Java8, Golang, Python3 で、
int64の範囲内の値を素因数分解したときの処理時間の比較してみました。
先に結果を見たい方はこちらへ。
処理時間一覧
C#, Java, Golangについては、bigintでも計算してみました。
利用した素因数分解のアルゴリズム
素因数分解のアルゴリズムについては、最も単純な試し割り法を利用しました。
2,3,5,7,11,13,17, ... （以下、+2, +4を交互に繰り返した値）で割れるかどうか試していきます。
処理の高速化のために、あらかじめ割れるかどうか照合する素数の表を用意しておく方法もありますが、
（63ビット程度のループ処理も10秒程度で終わったため、）今回は用意していません。
下記は、Javaでの試し割り処理の例です。
private long[] trial_division(long n) {
List<Long> prime_list = new ArrayList<>();
long max = (long)(Math.sqrt(n)) + 1;
// 2 で割っていく
while (n % 2 == 0) {
prime_list.add((long)2);
n /= 2;
}
// 3 で割っていく
while (n % 3 == 0) {
prime_list.add((long)3);
n /= 3;
}
// 5 ～ Math.sqrt(n) の数字で割っていく
boolean flag = true;
for (long i = 5; i < max; ) {
while (n % i == 0) {
prime_list.add(i);
n /= i;
if (n == 1)
i = max;
}
if (flag)
i += 2;
else
i += 4;
flag = !flag;
}
if (n != 1) {
prime_list.add(n);
}
// （以下、省略）
}
使用言語
- C言語 (gcc version 8.2.0(MinGW.org GCC-8.2.0-3))
- C# (.NET Core 3.0)
- Java8 (javac 11.0.4)
- Golang (go version go1.12.7 windows/amd64)
- Python3 (Python 3.7.4)
- Elixir (Elixir 1.11.2 & Mix 1.11.2(compiled with Erlang/OTP 21))
JavaとGolangについては、int64(long)型のほかに、
bigint(BigInteger)型でも同様の計算を行ってみました。
ちなみに、Python3については、整数型の上限がありませんね。
Elixirについては、Windows10ではなくWSL2内のUbuntu20.04LTSで実行しています。
プログラムのソースは、下記に配置しています。
https://github.com/NobuyukiInoue/PrimeFactorization
計測に使用したPC
処理時間の計測は、以下のスペックをPCを使用しました。
CPU: Intel Core-i7 8559U 2.7GHz(4.5GHz) 4コア/8スレッド
Memory: 16GB(LPDDR3 2,133MHz)
OS: Windows 10 Professional
いわゆる、Macbook Pro 13インチ 2018モデルですね。
処理時間一覧（2021/01/12 22:04更新）
対象の値は、素因数分解したい値です。
（"111..."が並んでいますが、2進数ではなく10進数です。）
試し割り法の場合、2,3,5,..などの小さな素数で割れた場合は、トータルのループ回数が少なくなるので、
値の大きさに比例して処理時間がかかるわけではありません。
int64の場合、64ビット程度の値でも、いまどきのPCであれば10秒以内で素因数分解ができてしまいます。
| 対象の値 (10進数) |
C言語 long long int (最適化オプション-O3) |
C# long |
C# BigInteger |
Java long |
Java BigInteger |
Golang int64 |
Golang BigInt |
Python3 int |
Elixir |
|---|---|---|---|---|---|---|---|---|---|
| 11111111111111 (44ビット) |
0.000[S] | 0.004[S] | 0.013[S] | 0.000[S] | 0.047[S] | 0.003[S] | 0.056[S] | 0.030[S] | 0.006[S] |
| 111111111111111 (47ビット) |
0.006[S] | 0.008[S] | 0.038[S] | 0.016[S] | 0.109[S] | 0.007[S] | 0.169[S] | 0.088[S] | 0.017[S] |
| 1111111111111111 (50ビット) |
0.012[S] | 0.015[S] | 0.067[S] | 0.031[S] | 0.141[S] | 0.015[S] | 0.343[S] | 0.176[S] | 0.033[S] |
| 11111111111111111 (54ビット) |
0.204[S] | 0.257[S] | 1.540[S] | 0.250[S] | 1.859[S] | 0.271[S] | 計測断念 (180秒以上) |
5.021[S] | 0.557[S] |
| 111111111111111111 (57ビット) |
0.001[S] | 0.002[S] | 0.007[S] | 0.000[S] | 0.031[S] | 0.001[S] | 0.022[S] | 0.016[S] | 0.003[S] |
| 1111111111111111111 (60ビット) |
2.122[S] | 2.300[S] | 15.025[S] | 2.422[S] | 15.688[S] | 2.519[S] | 計測断念 (180秒以上) |
48.322[S] | 20.44[S] |
| 6111111111111111111 (63ビット) |
4.884[S] | 5.396[S] | 41.263[S] | 5.703[S] | 38.781[S] | 5.937[S] | 計測断念 (180秒以上) |
243.715[S] | 46.36[S] |
M1 Mac処理時間一覧（2021/01/15 23:03更新）
参考までに、M1 Mac(MacBook Air 8コア/7GPU 8G/256GB)の計測結果も掲載させていただきます。
（アーキテクチャはすべてx86_64）
| 対象の値 (10進数) |
C言語 long long int (最適化オプション-O3) |
C# long |
C# BigInteger |
Java long |
Java BigInteger |
Golang int64 |
Golang BigInt |
Python3.8.2 int |
Elixir (Erlang/OTP 21) Mix 1.7.1) |
|---|---|---|---|---|---|---|---|---|---|
| 6111111111111111111 (63ビット) |
0.902[S] | 1.263[S] | 53.270[S] | 1.047[S] | 24.592[S] | 1.033[S] | 未計測 |
127.968[S] | 32.788[S]) |
2018年の時点でも、Intel Core-i7 8559U は、スマホの Qualcomm Snapdragon 845 に負けていましたが、、、
x86_64 でも、、、、M1 Mac 速ええ...orz
Elixirは、ループを再帰呼び出しで行っていますので、ループ回数が多いとさすがに苦戦します。
とはいえ、int64を超える整数も気にせず扱えます。
感想
Golangのbigintは、ループ数が多いと、（ループ内の代入処理時にインスタンス生成が行っているため）、
とんでもなく時間がかかっています。
いくつかの言語で、57ビットの処理時間が44ビットよりも短くなっていますが、これは、
11111111111111(44ビット)の素因数[11, 239, 4649, 909091] の合計が913990に対し、
111111111111111111(57ビット)の素因数[3, 3, 7, 11, 13, 19, 37, 52579, 333667]の合計が386339であり、
ループ回数が少なく済んでいるからです。
bigintでの処理速度の比較では、C# > Java > Golang の順番といったところでしょうか。