ubuntuusers.de

[Code-Gala] Lychrel-Zahlen

Status: Ungelöst | Ubuntu-Version: Nicht spezifiziert
Antworten |
Dieses Thema ist die Diskussion des Artikels Projekte/Code_Gala.

verdooft

Anmeldungsdatum:
15. September 2012

Beiträge: 4286

Ja, die Modelle sind auch nur wenig für deutsche Sprache trainiert, weshalb ich die eigentlich in englischer verwende (Codekommentierung + Anweisungen). Ich wollte es nur bisschen Kompatibler mit den hier mitlesenden gestalten. Danke für deine Verbesserungen, mir ging es nur ums Ergebnis (Abgleich der letzten und ersten Zahlen). Threadzahl und bis wieviel Zahlen zu rechnen sind, könnte man auch übergeben, 8 passte halt für mein System.

Marc_BlackJack_Rintsch Team-Icon

Ehemalige
Avatar von Marc_BlackJack_Rintsch

Anmeldungsdatum:
16. Juni 2006

Beiträge: 4650

Wohnort: Berlin

@verdooft: Wenn es Dir ums Ergebnis geht/ging, hättest Du das besser überprüfen müssen. Bei mir spuckt das C++-Programm nämlich ganze 386 mehr Zahlen aus als es sollte. Was sehr wahrscheinlich daran liegen wird, dass long long nicht ausreicht. Der Datentyp muss mindestens 175 Bits haben, sonst funktioniert das C++-Programm nicht korrekt.

Und bei Python passen halt 8 Threads überhaupt nicht, egal auf welchem Rechner, weil Threads grundsätzlich das ganze verlangsamen statt beschleunigen. Zumindest wenn man nicht irgend etwas Experimentelles ohne GIL zur Ausführung verwendet.

verdooft

Anmeldungsdatum:
15. September 2012

Beiträge: 4286

Ok, hab das bei der c++ Variante nicht ordentlich geprüft, bei Python gings einfacher mit wc -l. Gut, dass das rausgefunden wurde.

Marc_BlackJack_Rintsch Team-Icon

Ehemalige
Avatar von Marc_BlackJack_Rintsch

Anmeldungsdatum:
16. Juni 2006

Beiträge: 4650

Wohnort: Berlin

Bei dem C++ könnte man in is_lychrell() einen Test nach der Addition einbauen ob das Ergebnis kleiner 0 ist:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
bool is_lychrel(long long n) {
    for (int i = 0; i < 100; i++) {
        n += reverse_number(n);
        // Test ob long long das Ergebnis der Addition aufnehmen konnte.
        if (n < 0) {
            std::cerr << "Overflow\n";
            std::exit(1);
        }
        // Wenn die Zahl nach der Addition und Invertierung eine Palindromzahl
        // ist, dann ist sie keine Lychrel-Zahl.
        if (n == reverse_number(n)) return false;
    }
    // Nach 100 Iterationen ohne ein Palindrom gefunden zu haben, wird die Zahl
    // als Lychrel-Zahl betrachtet.
    return true;
}

Jetzt muss man nur noch warten bis die Rechner soweit sind, dass long long genug Bits hat, dann läuft das Programm auch korrekt. 🤡

Marc_BlackJack_Rintsch Team-Icon

Ehemalige
Avatar von Marc_BlackJack_Rintsch

Anmeldungsdatum:
16. Juni 2006

Beiträge: 4650

Wohnort: Berlin

Hier noch mal eine Python-Lösung die zeigt wie man das tatsächlich parallelisieren kann, so dass das auch ein bisschen mehr Geschwindigkeit bringt. Statt Threads oder Prozesse selbst zu verwalten und die Arbeit zu verteilen und die Ergebnisse einzusammeln, gibt es in der Standardbibliothek ja bereits das concurrent.futures-Modul, das einem die ganze Arbeit abnimmt:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#!/usr/bin/env python3
from concurrent.futures import ProcessPoolExecutor
from itertools import compress


def is_lychrel(n):
    n_mirrored = str(n)[::-1]
    for _ in range(100):
        n += int(n_mirrored)
        n_text = str(n)
        n_mirrored = n_text[::-1]
        if n_text == n_mirrored:
            return False
    return True


def main():
    max_worker_count = 8
    candidates = range(1, 100001)
    executor = ProcessPoolExecutor(max_worker_count)
    for n in compress(
        candidates,
        executor.map(
            is_lychrel,
            candidates,
            chunksize=len(candidates) // max_worker_count,
        ),
    ):
        print(n)


if __name__ == "__main__":
    main()

Laufzeit:

real	0m0,443s
user	0m1,236s
sys	0m0,093s

Ist jetzt gegen die 0,658s ohne Parallelisierung nicht die Welt, aber immerhin ist es tatsächlich schneller. Und statt map() aufzurufen einen ThreadPoolExecutor erstellen und dessen map()-Methode zu verwenden, ist eine recht übersichtliche Änderung, die man mal eben schnell gemacht hat.

Neral

Anmeldungsdatum:
3. Oktober 2007

Beiträge: 230

Marc_BlackJack_Rintsch schrieb:

Bei dem C++ könnte man in is_lychrell() einen Test nach der Addition einbauen ob das Ergebnis kleiner 0 ist:

Das ist generell falsch, weil signed integrale Typen in C++ nicht wrappen, sondern man bekommt UB, wenn der Ergebnistyp das Ergebnis nicht repräsentieren kann (also z. B. wenn es einen Overflow geben würde):

1
2
3
4
5
6
7
auto addition_wraps(long long lhs, long long rhs) -> bool {
    if (lhs < 0 or rhs < 0) {
        return false;
    }
    auto result = lhs + rhs;
    return result < 0;
}

Das hier wird zu dem hier kompiliert:

1
2
3
addition_wraps(long long, long long):
        xor     eax, eax
        ret

Man muss also entweder unsigned benutzen oder vor der Rechnung prüfen, ob das Ergebnis passt.

Antworten |