In C language, C #, Java8, Golang, Python3, I compared the processing time when the values in the range of int64 were factored into prime factors.
If you want to see the result first, click here. [Processing time list](https://qiita.com/gx3n-inue/items/7b63a2101ea26d3d1a29#Processing time list)
For C #, Java, Golang, I also calculated with bigint.
For the prime factorization algorithm, we used the simplest trial division method. We will try to see if it breaks by 2,3,5,7,11,13,17, ... (Hereafter, +2, +4 are repeated alternately).
In order to speed up the process, there is a way to prepare a table of prime numbers to check whether they are broken in advance, but (Because the loop processing of about 63 bits was completed in about 10 seconds) I have not prepared this time.
The following is an example of trial split processing in Java.
PrimeFactorization.java
private long[] trial_division(long n) {
List<Long> prime_list = new ArrayList<>();
long max = (long)(Math.sqrt(n)) + 1;
//Divide by 2
while (n % 2 == 0) {
prime_list.add((long)2);
n /= 2;
}
//Divide by 3
while (n % 3 == 0) {
prime_list.add((long)3);
n /= 3;
}
// 5 ～ Math.sqrt(n)Divide by the number of
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);
}
//(Hereafter omitted)
}
For Java and Golang, in addition to the int64 (long) type I tried the same calculation for bigint (BigInteger) type.
By the way, for Python3, there is no upper limit for integer types.
The source of the program is located below. https://github.com/NobuyukiInoue/PrimeFactorization
For the measurement of processing time, the following specifications also used a PC.
CPU: Intel Core-i7 8559U 2.7GHz (4.5GHz) 4 cores / 8 threads Memory: 16GB(LPDDR3 2,133MHz) OS: Windows 10 Professional
It's the so-called Macbook Pro 13-inch 2018 model.
The target value is the value you want to factor into. ("111 ..." is lined up, but it is a decimal number, not a binary number.)
In the case of the trial division method, if it is broken by a small prime number such as 2,3,5, .., the total number of loops will be reduced, so The processing time is not proportional to the size of the value.
In the case of int64, even a value of about 64 bits can be factored into prime factors within 10 seconds on a modern PC.
| Target value (Decimal number) |
C language long long int (Optimization options-O3) |
C# long |
C# BigInteger |
Java long |
Java BigInteger |
Golang int64 |
Golang BigInt |
Python3 int |
|---|---|---|---|---|---|---|---|---|
| 11111111111111 (44 bits) |
0.000[S] | 0.004[S] | 0.013[S] | 0.000[S] | 0.047[S] | 0.003[S] | 0.056[S] | 0.030[S] |
| 111111111111111 47 bits) |
0.006[S] | 0.008[S] | 0.038[S] | 0.016[S] | 0.109[S] | 0.007[S] | 0.169[S] | 0.088[S] |
| 1111111111111111 (50 bits) |
0.012[S] | 0.015[S] | 0.067[S] | 0.031[S] | 0.141[S] | 0.015[S] | 0.343[S] | 0.176[S] |
| 11111111111111111 (54 bits) |
0.204[S] | 0.257[S] | 1.540[S] | 0.250[S] | 1.859[S] | 0.271[S] | Abandon measurement (180 seconds or more) |
5.021[S] |
| 111111111111111111 (57 bits) |
0.001[S] | 0.002[S] | 0.007[S] | 0.000[S] | 0.031[S] | 0.001[S] | 0.022[S] | 0.016[S] |
| 1111111111111111111 (60 bit) |
2.122[S] | 2.300[S] | 15.025[S] | 2.422[S] | 15.688[S] | 2.519[S] | Abandon measurement (180 seconds or more) |
48.322[S] |
| 6111111111111111111 (63 bits) |
4.884[S] | 5.396[S] | 41.263[S] | 5.703[S] | 38.781[S] | 5.937[S] | Abandon measurement (180 seconds or more |
243.715[S] |
Golang's bigint has a large number of loops (because instance creation is done during assignment processing in the loop), It's taking a tremendous amount of time.
In some languages, 57-bit processing time is shorter than 44-bit, which is
The total of the prime factors [11, 239, 4649, 909091] of 11111111111111 (44 bits) is 913990, whereas The sum of the prime factors [3, 3, 7, 11, 13, 19, 37, 52579, 333667] of 111111111111111111 (57 bits) is 386339, This is because the number of loops is small.
When comparing processing speeds with bigint, is it the order of C #> Java> Golang?