[PYTHON] Int64-Primfaktor-Zerlegung durch Sprachverarbeitung (Versuchsaufteilungsmethode), Verarbeitungszeitvergleich

In C-Sprache C #, Java8, Golang, Python3, Ich habe die Verarbeitungszeit verglichen, als die Werte im Bereich von int64 faktorisiert wurden.

Wenn Sie das Ergebnis zuerst sehen möchten, klicken Sie hier. Verarbeitungszeitliste

Für C #, Java, Golang habe ich auch mit bigint gerechnet.

Primfaktor-Zerlegungsalgorithmus verwendet

Für den Primfaktorisierungsalgorithmus haben wir die einfachste Versuchsaufteilungsmethode verwendet. Ich werde versuchen zu sehen, ob es um 2,3,5,7,11,13,17, ... bricht (im Folgenden werden +2, +4 abwechselnd wiederholt).

Um den Prozess zu beschleunigen, gibt es eine Methode, um eine Tabelle mit Primzahlen zu erstellen, um zu prüfen, ob sie defekt ist oder nicht, aber im Voraus (Da die Schleifenverarbeitung von ca. 63 Bit in ca. 10 Sekunden abgeschlossen war) habe ich diesmal nicht vorbereitet.

Das folgende Beispiel zeigt die Test-Split-Verarbeitung in Java.

PrimeFactorization.java


private long[] trial_division(long n) {
    List<Long> prime_list = new ArrayList<>();
    long max = (long)(Math.sqrt(n)) + 1;

    //Teilen Sie durch 2
    while (n % 2 == 0) {
        prime_list.add((long)2);
        n /= 2;
    }

    //Teilen Sie durch 3
    while (n % 3 == 0) {
        prime_list.add((long)3);
        n /= 3;
    }

    // 5 ~ Math.sqrt(n)Teilen Sie durch die Anzahl von
    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);
    }
//(Im Folgenden weggelassen)
}

Verwendete Sprache

Für Java und Golang zusätzlich zum Typ int64 (long) Ich habe die gleiche Berechnung für den Bigint-Typ (BigInteger) versucht.

Für Python3 gibt es übrigens keine Obergrenze für Ganzzahltypen.

Die Quelle des Programms befindet sich unten. https://github.com/NobuyukiInoue/PrimeFactorization

PC zur Messung verwendet

Für die Messung der Verarbeitungszeit wurde in den folgenden Spezifikationen auch ein PC verwendet.

CPU: Intel Core-i7 8559U 2,7 GHz (4,5 GHz) 4 Kerne / 8 Threads Memory: 16GB(LPDDR3 2,133MHz) OS:    Windows 10 Professional

Sogenanntes Macbook Pro 13 Zoll 2018 Modell.

Bearbeitungszeitliste (Aktualisiert um 23:10 Uhr am 15.07.2020 (Mi))

Der Zielwert ist der Wert, den Sie berücksichtigen möchten. ("111 ..." ist in einer Reihe, aber es ist eine Dezimalzahl, keine Binärzahl.)

Im Fall der Versuchsaufteilungsmethode wird die Gesamtzahl der Schleifen reduziert, wenn sie durch eine kleine Primzahl wie 2,3,5, .. gebrochen wird Die Verarbeitungszeit ist nicht proportional zur Größe des Wertes.

Im Fall von int64 kann selbst bei einem Wert von ungefähr 64 Bit, wenn es sich um einen modernen PC handelt, die Primfaktorisierung innerhalb von 10 Sekunden erfolgen.

Zielwert
(Dezimalzahl)
C Sprache
long long int
(Optimierungsoptionen-O3)
C#
long
C#
BigInteger
Java
long
Java
BigInteger
Golang
int64
Golang
BigInt
Python3
int
11111111111111
(44 Bit)
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 Bit)
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 Bit)
0.204[S] 0.257[S] 1.540[S] 0.250[S] 1.859[S] 0.271[S] Messung abbrechen
(180 Sekunden oder mehr)
5.021[S]
111111111111111111
(57 Bit)
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] Messung abbrechen
(180 Sekunden oder mehr)
48.322[S]
6111111111111111111
(63 Bit)
4.884[S] 5.396[S] 41.263[S] 5.703[S] 38.781[S] 5.937[S] Messung abbrechen
(180 Sekunden oder mehr
243.715[S]

Impressionen

Golangs Bigint hat eine große Anzahl von Schleifen (da die Instanz während des Zuweisungsprozesses in der Schleife erstellt wird). Es dauert enorm viel Zeit.

In einigen Sprachen ist die 57-Bit-Verarbeitungszeit kürzer als die 44-Bit-Verarbeitung

Die Summe der Primfaktoren [11, 239, 4649, 909091] von 11111111111111 (44 Bit) beträgt 913990, Die Summe der Primfaktoren [3, 3, 7, 11, 13, 19, 37, 52579, 333667] von 111111111111111111 (57 Bit) beträgt 386339, Dies liegt daran, dass die Anzahl der Schleifen gering ist.

Ist es im Vergleich der Verarbeitungsgeschwindigkeit mit bigint die Reihenfolge von C #> Java> Golang?

Recommended Posts

Int64-Primfaktor-Zerlegung durch Sprachverarbeitung (Versuchsaufteilungsmethode), Verarbeitungszeitvergleich
Zufälliger Vergleich von Waldgröße und Verarbeitungszeit