En langage C, C #, Java8, Golang, Python3, J'ai comparé le temps de traitement lorsque les valeurs de la plage de int64 étaient factorisées.
Si vous voulez voir le résultat en premier, cliquez ici. [Liste des délais de traitement](https://qiita.com/gx3n-inue/items/7b63a2101ea26d3d1a29#Liste des délais de traitement)
Pour C #, Java, Golang, j'ai également calculé avec bigint.
Pour l'algorithme de factorisation prime, nous avons utilisé la méthode de division d'essai la plus simple. J'essaierai de voir s'il casse de 2,3,5,7,11,13,17, ... (ci-après, la valeur que +2, +4 est répétée en alternance).
Afin d'accélérer le processus, il existe une méthode pour préparer une table de nombres premiers pour vérifier si elle est cassée ou non à l'avance, mais (Parce que le traitement en boucle d'environ 63 bits s'est terminé en environ 10 secondes) Je n'ai pas préparé cette fois.
Voici un exemple de traitement d'essai fractionné en Java.
PrimeFactorization.java
private long[] trial_division(long n) {
List<Long> prime_list = new ArrayList<>();
long max = (long)(Math.sqrt(n)) + 1;
//Diviser par 2
while (n % 2 == 0) {
prime_list.add((long)2);
n /= 2;
}
//Diviser par 3
while (n % 3 == 0) {
prime_list.add((long)3);
n /= 3;
}
// 5 ～ Math.sqrt(n)Divisez par le nombre de
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);
}
//(Ci-après omis)
}
Pour Java et Golang, en plus du type int64 (long) J'ai essayé le même calcul pour le type bigint (BigInteger).
À propos, pour Python3, il n'y a pas de limite supérieure pour les types entiers.
La source du programme se trouve ci-dessous. https://github.com/NobuyukiInoue/PrimeFactorization
Pour la mesure du temps de traitement, les spécifications suivantes utilisaient également un PC.
CPU: Intel Core-i7 8559U 2,7 GHz (4,5 GHz) 4 cœurs / 8 threads Memory: 16GB(LPDDR3 2,133MHz) OS: Windows 10 Professional
Modèle dit Macbook Pro 13 pouces 2018.
La valeur cible est la valeur que vous souhaitez factoriser. ("111 ..." est aligné, mais c'est un nombre décimal, pas un nombre binaire.)
Dans le cas de la méthode de division d'essai, si elle est interrompue par un petit nombre premier tel que 2,3,5, .., le nombre total de boucles sera réduit, donc Le temps de traitement n'est pas proportionnel à la taille de la valeur.
Dans le cas de int64, même avec une valeur d'environ 64 bits, un PC moderne peut effectuer une factorisation prime en 10 secondes.
| Valeur cible (Nombre décimal) |
Langage C long long int (Options d'optimisation-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] | Abandonner la mesure (180 secondes ou plus) |
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 bits) |
2.122[S] | 2.300[S] | 15.025[S] | 2.422[S] | 15.688[S] | 2.519[S] | Abandonner la mesure (180 secondes ou plus) |
48.322[S] |
| 6111111111111111111 (63 bits) |
4.884[S] | 5.396[S] | 41.263[S] | 5.703[S] | 38.781[S] | 5.937[S] | Abandonner la mesure (180 secondes ou plus |
243.715[S] |
Le bigint de Golang a un grand nombre de boucles (car l'instance est créée pendant le processus d'affectation dans la boucle), Cela prend énormément de temps.
Dans certaines langues, le temps de traitement de 57 bits est inférieur à 44 bits, ce qui
La somme des facteurs premiers [11, 239, 4649, 909091] de 11111111111111 (44 bits) est 913990, La somme des facteurs premiers [3, 3, 7, 11, 13, 19, 37, 52579, 333667] de 111111111111111111 (57 bits) est 386339, C'est parce que le nombre de boucles est petit.
Dans la comparaison de la vitesse de traitement avec bigint, est-ce l'ordre de C #> Java> Golang?