ubuntuusers.de

[Code-Gala] Lychrel-Zahlen

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

hannenz

Anmeldungsdatum:
7. Dezember 2006

Beiträge: Zähle...

Wohnort: Ulm

ja du hast recht mit den 5 bzw. 6 Stellen. Ich hab das jetzt mal geändert und die "number" noch in die Zeropage gelegt, damit komm ich jetzt auf 15.79 Sekunden. Ich glaube mehr ist nicht zu machen.
Was ich jetzt noch interessant fände wäre, das Dingens als Benchmark für versch. C-Implementationen auf dem C64/C128 zu nutzen, also cc65, Power-C, Super-C - würde mich mal interessieren, welcher Compiler da bei gleichem Sourcecode am besten abschneidet.
Sag mal, Marc, bist du eigentlich auch in einem der einschlägigen 8-bit Foren (z. Bsp. forum-64.de) zugegen, würde da evtl. besser passen, als hier 😉

BigMc

Avatar von BigMc

Anmeldungsdatum:
18. März 2007

Beiträge: 1814

Moin,

was soll nun mit der Seite Baustelle/Code Gala passieren? Löschen oder nach Projekte verschieben? Oder sagen wir mal so: würde jemand der Seite nachtrauern? In der Baustelle kann sie jedenfalls nicht bleiben.

Gruß, BigMc

user_unknown

Avatar von user_unknown

Anmeldungsdatum:
10. August 2005

Beiträge: 17583

Wohnort: Berlin

Ich würde nachtrauern.

BigMc

Avatar von BigMc

Anmeldungsdatum:
18. März 2007

Beiträge: 1814

So sehr, dass du die paar Syntaxfehler ausbesserst, damit ich nach Projekte verschieben kann?

EDIT: Ok, verschoben. Wieder eine Baustelle weniger. ☺

Hello_World

Anmeldungsdatum:
13. Juni 2006

Beiträge: 3620

user unknown hat so gut wie nichts verbessert. Die C- und C++-Programme waren voll mit irgendwelchen völlig sinnlosen Sternchen. Ich hab das jetzt mal überarbeitet, allerdings müsste jetzt die Baustelle wieder entfernt werden.

BigMc

Avatar von BigMc

Anmeldungsdatum:
18. März 2007

Beiträge: 1814

Jetzt erstellt bitte nicht immer wieder die Baustelle neu. Die Seite ist jetzt unter Projekte/Code Gala. Baustelle nochmal gelöscht.

Hello_World

Anmeldungsdatum:
13. Juni 2006

Beiträge: 3620

BigMc schrieb:

Jetzt erstellt bitte nicht immer wieder die Baustelle neu. Die Seite ist jetzt unter Projekte/Code Gala. Baustelle nochmal gelöscht.

Entschuldigung, ich werde mir nicht nochmal die Mühe machen, dutzende Syntaxfehler in der Seite zu beheben.

Sid_Burn

Anmeldungsdatum:
23. Oktober 2004

Beiträge: 2159

Hello World schrieb:

BigMc schrieb:

Jetzt erstellt bitte nicht immer wieder die Baustelle neu. Die Seite ist jetzt unter Projekte/Code Gala. Baustelle nochmal gelöscht.

Entschuldigung, ich werde mir nicht nochmal die Mühe machen, dutzende Syntaxfehler in der Seite zu beheben.

Qualität wird halt bei ubuntu(users) generell nicht hoch angesehen. Auch ist wohl zu viel Wissen schädlich, daher möchte man auch gerne Sachen löschen. Vielleicht wäre ein Stop Schild gut?

BigMc

Avatar von BigMc

Anmeldungsdatum:
18. März 2007

Beiträge: 1814

Hello World schrieb:

Entschuldigung, ich werde mir nicht nochmal die Mühe machen, dutzende Syntaxfehler in der Seite zu beheben.

Sorry, hatte eine Änderung übersehen. Jetzt sind wieder alle Änderungen von dir auf der Seite im Wiki enthalten.

Gruß, BigMc

senden9

Avatar von senden9

Anmeldungsdatum:
8. Februar 2010

Beiträge: 965

Wohnort: Österreich

Hi, wie sieht's mit dem "Projekt" (Code-Gala) aus? Ich hätte noch Interesse an so was. Schade das es "tot" ist, es könnte ja wieder ins Leben gerufen werden.

domachine

Anmeldungsdatum:
16. Mai 2007

Beiträge: 562

Ich wär auch noch interessiert. Wie wärs mit folgender Aufgabe, die ich aus dem Projekt Euler habe:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 x 99. Find the largest palindrome made from the product of two 3-digit numbers.

Übersetzt heiszt das so viel wie:

Ein Palindrom ist eine Zahl die in beide Richtungen gelesen die gleiche Zahl bleibt. Das längste Palindrom aus dem Produkt zweier 2-stelliger Zahlen ist 9009 = 91 x 99. Finde das längste Palindrom aus dem Produkt zweier 3-stelliger Zahlen.

Meine Lösung in C:

 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <stdio.h>
#include <stdlib.h>


/*
  Faster but longer.
*/
int is_palin(int num)
{
    int i, x;    /* Runtime variables. */
    int len = 0;
    int limit; /* The limit. `len / 2` with even numbers and `len / 2 - 1`
                  with not even numbers. */
    int *stack;

    for(i = num; i > 0; i /= 10)
        ++len;

    limit = len / 2;

    stack = (int *)malloc(limit * sizeof(int));
    for(i = num, x = 0; x < limit; i /= 10, ++x)
        stack[x] = i % 10;

    i = (len % 2 == 0) ? i : (i / 10);
    for(x = limit - 1; x >= 0; i /= 10, --x) {
        if(i % 10 != stack[x])
            return 0;
    }

    free(stack);
    return 1;
}


/*
  Slower but shorter.
*/
int is_palin2(int num)
{
    int *stack = NULL;
    int i,       /* Runtime variable. */
        len = 0, /* Char length of the number. */
        limit;

    for(i = num; i != 0; i /= 10) {
        stack = (int *)realloc(stack, ++len * sizeof(int));
        stack[len - 1] = i % 10;
    }

    limit = len / 2;
    for(i = 0; i < limit; ++i) {
        if(stack[i] != stack[(len - 1) - i])
            return 0;
    }

    free(stack);
    return 1;
}


int main()
{
    int largest = 0,
        i,
        j,
        product = 2 * 4;

    for(i = 1; i < 10000; ++i) {
        for(j = 1; j < 10000; ++j) {
            product = i * j;
            if(product > largest && is_palin(product))
                largest = product;
        }
    }

    printf("Largest palindrome: %d\n", largest);
    return 0;
}

domachine

Anmeldungsdatum:
16. Mai 2007

Beiträge: 562

Entschuldigung hab die Überschrift nicht ganz gelesen. Mein Post ist dann wohl etwas fehlgeleitet.

sh4711

Anmeldungsdatum:
13. Februar 2011

Beiträge: 1091

Danke für die Aufgabenstellung Lychrel Zahlen. War nicht trivial, habe was dazu gelernt.

verdooft

Anmeldungsdatum:
15. September 2012

Beiträge: 4287

Ich weiß, der Thread ist uralt, mich hat trotzdem mal interessiert, ob ein rein lokal lauffähiges LLM das hinbekommt.

Aufgerufen wurde das so:

./main -t 6 -m ~/Downloads/models/Codestral-22B-v0.1-Q8_0.gguf -c 8192 --temp 0.7 --repeat_penalty 1.1 --log-enable -n -1 -p '<s> [INST] <<SYS>>\n'''Kommentiere den Quellcode ausführlich in deutscher Sprache.'''\n<</SYS>>\n\n'''Erstelle ein C++ Programm, das folgende Aufgabe löst: Gib alle vermutlichen Lychrel Zahlen zwischen 1 und 100000 aus. Für jede Zahl sollen 100 Iterationen ausgeführt werden. Verwende 8 Threads um die Ausgabe zu beschleunigen. Die Ausgabe soll richtig sortiert erst am Ende aller Berechnungen erfolgen.''' [/INST]  </s>\n' --mirostat 2 -e -i -s 2333334
  • Im interaktiven Modus startete ich das für den Fall, dass ich mit dem zuerst zurückgegebenen Source nicht zufrieden gewesen wäre, dann kann man Korrekturen angeben, das Programm kennt aber auch alles vorher ein- und ausgegebene.

Ausgabe:

 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <thread>
#include <vector>
#include <algorithm>
#include <mutex>

// Eine Mutex, um den gleichzeitigen Zugriff auf die Konsole zu synchronisieren
std::mutex mtx;

// Funktion, um eine Zahl zu invertieren
long long reverse_number(long long num) {
    long long rev = 0;
    while (num > 0) {
        rev = rev * 10 + num % 10;
        num /= 10;
    }
    return rev;
}

// Funktion, um zu überprüfen ob eine Zahl eine Lychrel-Zahl ist
bool is_lychrel(long long n) {
    for (int i = 0; i < 100; i++) {
        n += reverse_number(n);

        // 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;
}

// Funktion für jeden Thread, überprüft eine Teilmenge der Zahlen und fügt Lychrel-Zahlen in einen Vektor ein
void check_lychrel(int start, int end, std::vector<long long> &result) {
    for (long long i = start; i <= end; i++) {
        if (is_lychrel(i)) {
            // Schutz vor gleichzeitigem Zugriff auf die Konsole und den Vektor
            mtx.lock();
            result.push_back(i);
            mtx.unlock();
        }
    }
}

int main() {
    const int num_threads = 8;
    std::vector<std::thread> threads(num_threads);
    std::vector<long long> lychrel_numbers;

    // Jeder Thread bekommt einen Bereich der Zahlen zum überprüfen
    for (int i = 0; i < num_threads; ++i) {
        threads[i] = std::thread(check_lychrel, i * 12500 + 1, (i + 1) * 12500, std::ref(lychrel_numbers));
    }

    // Warten auf alle Threads
    for (auto &th : threads) {
        th.join();
    }

    // Sortieren und Ausgabe der Lychrel-Zahlen
    std::sort(lychrel_numbers.begin(), lychrel_numbers.end());

    for (const auto &num : lychrel_numbers) {
        std::cout << num << " ";
    }

    return 0;
}

Dieses Programm schreibt alle Lychrel-Zahlen zwischen 1 und 100000 aus. Es verwendet acht Threads, um die Berechnungen zu beschleunigen und eine Mutex für den synchronisierten Zugriff auf die Konsole. Jeder Thread überprüft einen Teilbereich der Zahlen und speichert Lychrel-Zahlen in einem Vektor. Am Ende sortiert das Hauptprogramm die gefundenen Lychrel-Zahlen und gibt sie aus.

Ausführung:

time ./a.out
196 295 394 493 592 ... 99961 99973 99974 99979 99990 99999
real    0m0,015s
user    0m0,062s
sys     0m0,000s

Edit ergänzt noch die Pythonversion:

Aufruf:

./main -t 6 -m ~/Downloads/models/Codestral-22B-v0.1-Q8_0.gguf -c 8192 --temp 0.7 --repeat_penalty 1.1 --log-enable -n -1 -p '<s> [INST] <<SYS>>\n'''Kommentiere den Quellcode ausführlich in deutscher Sprache.'''\n<</SYS>>\n\n'''Erstelle ein Python Programm, das folgende Aufgabe löst: Gib alle vermutlichen Lychrel Zahlen zwischen 1 und 100000 aus. Für jede Zahl sollen 100 Iterationen ausgeführt werden. Verwende 8 Threads um die Ausgabe zu beschleunigen. Die Ausgabe soll richtig sortiert erst am Ende aller Berechnungen erfolgen. Das Programm soll auf Ausführungsgeschwindigkeit optimiert sein.''' [/INST]  </s>\n' --mirostat 2 -e -i -s 2333334

Ausgabe:

 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
34
35
36
37
38
39
40
41
42
43
import threading
from queue import Queue

# Funktion zur Überprüfung, ob eine Zahl eine Lychrel-Zahl ist
def is_lychrel(n):
    for i in range(100):
        n += int(str(n)[::-1])
        if str(n) == str(n)[::-1]:
            return False
    return True

# Funktion zum Arbeiten von Threads. Dequeues eine Zahl aus der Queue, überprüft sie und ergänzt das Ergebnis zur Liste
def worker():
    while True:
        n = q.get()
        if is_lychrel(n):
            results.append(n)
        q.task_done()

# Anzahl der Threads
num_threads = 8

# Erstellen einer Queue und einer Liste für Ergebnisse
q = Queue()
results = []

# Starten von Threads
for i in range(num_threads):
    t = threading.Thread(target=worker)
    t.daemon = True
    t.start()

# Füllen der Queue mit Zahlen
for i in range(1, 100001):
    q.put(i)

q.join()

# Sortieren und Ausgeben der Ergebnisse
results.sort()
print("Lychrel numbers between 1 and 100000:")
for n in results:
    print(n)

In diesem Python-Programm werden Lychrel-Zahlen zwischen 1 und 100000 gefunden. Eine Lychrel-Zahl ist eine Zahl, die nach der Anwendung einer bestimmten Operation (die Addition dieser Zahl mit ihrer Spiegelzahl) keine Palindromzahl erzeugt. Wir definieren eine Funktion is_lychrel(n), um dies zu überprüfen.

Wir verwenden 8 Threads, um die Berechnungen zu beschleunigen. Jeder Thread wird durch die Funktion worker() repräsentiert, die in einer Endlosschleife läuft und Warteschlangenaufgaben verarbeitet. Wenn ein Thread eine Zahl aus der Warteschlange dequeues, überprüft er mit is_lychrel(n), ob es sich um eine Lychrel-Zahl handelt. Wenn ja, fügt er sie zur Liste results hinzu.

Wir erstellen eine Queue q und füllen sie mit den Zahlen von 1 bis 100000. Jede Zahl wird als Aufgabe in die Queue eingereiht, die die Threads verarbeiten können.

Nachdem alle Aufgaben in der Queue abgeschlossen sind (q.join()), sortieren wir die Ergebnisse und geben sie aus. Dies stellt sicher, dass die Ausgabe richtig sortiert ist und erst nach Abschluss aller Berechnungen erfolgt.

Ausführung:

time python3 test.py
...
99947
99953
99958
99961
99973
99974
99979
99990
99999

real    0m1,918s
user    0m1,635s
sys     0m0,971s

Bearbeitet von sebix:

Forensyntax verbessert.

Marc_BlackJack_Rintsch Team-Icon

Ehemalige
Avatar von Marc_BlackJack_Rintsch

Anmeldungsdatum:
16. Juni 2006

Beiträge: 4650

Wohnort: Berlin

@verdooft: Man muss halt vorsichtig mit so etwas sein ob die Fehler die diese Sprachmodelle machen am Ende nicht falsche Ergebnisse produzieren. Und man kann den Erklärungen und Kommentaren nicht glauben, und damit eignet es sich nur für Leute die schon programmieren können, und das richtig einschätzen können, aber nicht für Leute die damit programmieren lernen wollen.

long long wäre mir zu ”unsicher”, ich würde da einen Typ verwenden in dem die Bitanzahl festgelegt ist. Und vielleicht auch ein assert einbauen das prüft ob ein Überlauf stattgefunden hat. Der Datentyp muss ja mindestens 174 Bits aufnehmen können. Tut er das bei Dir? Für n=89099 sind wir nach hundert Schritten bei 13185663245681373721819658007579081282730876314656813.

Das da Zahlen bis 100.000 geprüft werden ist mir zu indirekt ausgedrückt. Wenn man die Anzahl der Threads ändert, muss man immer selber daran denken die beiden literalen 12.500-Werte auch zu ändern.

In einem Kommentar steht etwas davon das der mutex was mit Konsole und Vector zu tun hat, im Erklärungstext ist nur die Konsole erwähnt — mit der Konsole hat das aber gar nichts zu tun.

Beim Python-Programm sind die Threads falsch. Da kann das LLM nicht wirklich etwas dafür weil explizit nach Threads gefragt wurde, aber die verlangsamen das in CPython weil immer nur ein Thread Python-Bytecode ausführen kann. Threads sind für „CPU bound tasks“ also keine gute Lösung es sei denn man weiss, dass da viel in Bibliotheken abgearbeitet wird, die in C geschrieben sind, und die das „global interpreter lock“ (GIL) freigeben.

Was fehlt ist ein Lock/Mutex zum Absichern von result.append(n). Das man damit durchkommt liegt am GIL. Bei Python-Implementierungen ohne dieses globale Lock könnte das auf die Nase fallen.

Dann sind die globalen Variablen unsauber und das worker() da einfach so magisch auf q und results zugreift, ohne die als Argumente übergeben bekommen zu haben. Wer jetzt denkt, ach scheiss doch auf saubere Programmierung, es funktioniert doch: modulglobale Variablen sind langsamer als lokale Variablen in Funktionen und Methoden.

Dann lande ich bei so etwas:

 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#!/usr/bin/env python3
import threading
from queue import Queue


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


def worker(queue, results, lock):
    while True:
        n = queue.get()
        if is_lychrel(n):
            with lock:
                results.append(n)
        queue.task_done()


def main():
    thread_count = 8

    queue = Queue()
    results = []
    lock = threading.Lock()

    for _ in range(thread_count):
        threading.Thread(
            target=worker, args=[queue, results, lock], daemon=True
        ).start()

    for i in range(1, 100001):
        queue.put(i)

    queue.join()

    results.sort()
    print("Lychrel numbers between 1 and 100000:")
    for n in results:
        print(n)


if __name__ == "__main__":
    main()

Mein Rechner ist schon etwas älter, hier die Zeit:

real  0m3,916s
user  0m3,880s
sys   0m1,242s

Das macht ja nur Sinn wenn das auch tatsächlich schneller ist als ohne Threads:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#!/usr/bin/env python3


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


def main():
    for n in filter(is_lychrel, range(1, 100001)):
        print(n)


if __name__ == "__main__":
    main()

Laufzeit:

real  0m1,063s
user  0m1,046s
sys   0m0,017s

Mit Threads also deutlich langsamer!

Da kann man noch mal was raus holen in dem man das Umwandeln in eine Zeichenkette und das umdrehen der Ziffern nicht unnötig mehrfach macht:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#!/usr/bin/env python3


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():
    for n in filter(is_lychrel, range(1, 100001)):
        print(n)


if __name__ == "__main__":
    main()

Laufzeit:

real  0m0,658s
user  0m0,649s
sys 0m0,009s