[PYTHON] Comparaison du temps de traitement par décomposition en facteurs premiers Int64 (méthode de division d'essai) par langue

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.

Algorithme de décomposition des facteurs premiers utilisé

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)
}

Langue utilisée

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

PC utilisé pour la mesure

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.

Liste des délais de traitement (mise à jour 23:10 2020/07/15 (mer.))

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]

Impressions

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?

Recommended Posts

Comparaison du temps de traitement par décomposition en facteurs premiers Int64 (méthode de division d'essai) par langue
Comparaison de la taille de la forêt aléatoire / du temps de traitement