Primzahlenberechnung in BASIC (wie SM Baker on a Z8000 CoPro)

    Im YT Video "Trump Card Z8000 PC Coprocessor card Part 2" von smbakeryt bei Minute 15 und 37 Sekunden wird die Primzahlenrechnung getestet gegen den original IBM XT in BASICA und dann gegen die eingebaute Tump Z8000 CoPro Card - interpretiert und kompiliert


    Ich habe den kurzen Source mal in slenz "Stefan's BASIC v1.4" getestet auf meinem ESP32 Lite ;)




    Im Input 64 gab es mal einen Wettbewerb zur schnellen Primzahlberechnung. Das war das einzige Programm, das ich je auf dem C64 (meines Bruders) geschrieben habe. Die Auflösung des Rätsels und die schnellsten Programme sind in Heft 1/86 ab Seite 25, den Scan findet man im Netz. Das Siegerprogramm hat nur halb so lang gebraucht wie meins, das war vielleicht enttäuschend, menno!

    Quote from guidol


    Ansonten sind auch 1 und 2 Primzahlen :)

    Die 1 wird nicht zu den Primzahlen gezählt. Ansonsten wäre die Eindeutigkeit der Primzahlzerlegung nicht mehr gegeben:


    6 wäre dann 2*3 aber auch 1*2*3 oder 1*1*2*3 usw


    Ein anderes Argument: es gilt der Satz, dass das Produkt zweier verschiedener Primzahl keine Primzahl ist. Das wäre mit 1 als Primzahl aber nicht mehr gegeben


    Roland

    Quote from BlindGerMan

    Nein, 1 ist keine Primzahl!

    Test bestanden :xmas:


    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97


    Sorry guidol


    Quelle Google :

    Die Zahl 1 sieht auf den ersten Blick wie eine Primzahl aus. Schließlich ist sie sowohl durch 1 als auch durch sich selbst teilbar. Allerdings: Eine Primzahl hat genau zwei Teiler – die 1 hat jedoch nur einen Teiler, nämlich 1. Daher ist auch sie keine Primzahl.


    Quote from ThoralfAsmussen

    Kann den eine potentielle Primzahl (d.h. eine darauf zu testende) einen Teiler haben, der größer als ihre eigene Hälfte ist ?

    Man braucht beim Suchen nach Teilern sogar nur bis zur Quadratwurzel aus der Zahl zu gehen.

    Und die Quadratwurzel ist bei Zahlen ab 4 aufwärts immer kleiner gleich der Hälfte der Zahl, bei größeren Zahlen sogar deutlich kleiner:

    sqrt100)=10

    sqrt(900)=30

    Beim Listing wird die Anfangszeit in Zeile 16 genommen.

    Somit wird die manuelle Eingabezeit mitgezählt.

    Ich würde diese Zeile zwischen die Zeilen 30 und 40 verschieben.

    Quote from Gerd5

    Ich würde diese Zeile zwischen die Zeilen 30 und 40 verschieben.

    Danke! Mein Fluechtigkeitsfehler - habe jetzt aus der 16 eine 35 gemacht:

    30 INPUT L

    35 SM=MILLIS(1)

    40 FOR N=2 TO L


    Jetzt wundern mich auch nicht mehr die unterschiedlichen Ergebnisse :)

    Ohne die Eingabezeit geht es jetzt auch flotter ;)

    It took 2.79099 secs


    ChatGPT hat mir eine andere Variante vorgeschlagen, die ist viel schneller - aber wohl etwas unsauber beim verlassen der I-FOR/NEXT-Schleife in 40


    It took 0.292 secs

    Quote from ThoralfAsmussen

    sqr kann man ja meiden, aber shiften - d.h. binär halbieren - kostet fast nichts)

    Ja, die Wurzel sqrt kostet einmal etwas Zeit (sicher mehr als ein Shift).

    Spart danach aber jede Menge Schleifendurchläufe, in denen munter dividiert wird.

    Und mit sqr ist doch normalerweise das Quadrieren (hoch 2) gemeint.


    Hängt natürlich von konkreten Basic-Dialekt ab :tüdeldü:

    guidol

    1) Du kannst die Hälfte der N-Schleife einsparen: nach der 2 kann keine gerade Zahl mehr Primzahl sein, also brauchen nur ungerade Zahlen noch getestet zu werden.

    Entweder (falls in der Basic-Syntax vorhanden) STEP 2

    Oder mit Hilfsvariable

    M=INT(1000/2)

    N=1

    FOR X=1 TO M

    N=N+2


    2) Du kannst noch ausprobieren, ob die Vermeidung von zweimaliger Division N/I was bringt:

    J=N/I : IF INT(J) = J THEN P=0 : GOTO 60


    3) Du kannst weiterhin ausprobieren, ob INT(SQR(N)) bei der Schleife immer wieder berechnet wird:

    K=INT(SQR(N))

    FOR I=1TO K


    LG Gerd

    Quote from Gerd5

    guidol

    1) Du kannst die Hälfte der N-Schleife einsparen: nach der 2 kann keine gerade Zahl mehr Primzahl sein, also brauchen nur ungerade Zahlen noch getestet zu werden.

    Entweder (falls in der Basic-Syntax vorhanden) STEP 2

    Das kann man sogar noch ausbauen: man kann I in 6er-Schritten (2*3) ab 6 hochzählen und jeweils nur I-1 und I+1 testen, also nur noch ein Drittel der Kandidaten prüfen. Die ersten Primzahltreffer (2,3) sind damit festgelegt.

    Das geht (Sieb des Eratosthenes) beliebig weiter: ab 30 in 30er (2*3*5)- Schritten und nur bei I +/- 1, +/-7, +/-11 und +/- 13 prüfen. jetzt werden nur noch ca ¼ der Kandidaten geprüft.

    Damit spart man FOR-NEXT Overhead (mehr Prüfungen in einer Schleife), verliert aber etwas durch die Rechnung I +/- d


    Roland

    Ich weiß nicht, ob das Zeit spart aber zusätzlich zu den ungraden Zahlen könnte man jede Zahl ausschließen, die mit 5 endet.


    Da gab es mal Regeln, wie man schnell checken kann, ob sich durch 3,7,9 teilen lässt?

    Quote from Roland_t29

    Das geht (Sieb des Eratosthenes) beliebig weiter: ab 30 in 30er (2*3*5)- Schritten und nur bei I +/- 1, +/-7, +/-11 und +/- 13 prüfen. jetzt werden nur noch ca ¼ der Kandidaten geprüft.

    Im Netz habe ich solch eine Version gefunden ;) und habe die mal in MBASIC abgetippt ;)



    Sehr schön ! Es ist spät und ich habe gerade keinen Rechner zur Hand, aber folgende Optimierung sollte noch etwas Zeit in einer inneren Schleife einsparen. Es erspart die wiederholte Berechnung von I*I, und das Hochzählen von J um I wird durch eine wiederholte Addition und nicht über eine Multiplikation erledigt. Über den Startpunkt für J (I*I) habe ich etwas nachdenken müssen, ich hätte bei I angefangen, aber I*I ist wirklich clever.


    260 J = I * I

    280 REM (entfällt)

    ...

    310 J = J + I

    320 GOTO 290

    ...


    Roland

    Quote from Roland_t29

    aber I*I ist wirklich clever


    erklär mal ... ich hätte bei 2*I angefangen


    (edit: der mögliche "andere" Faktor ist immer kleiner als I, für alle Produkte zwischen 1*I und I*I - und darum schon ausmaskiert im Array, weshalb man auch bei I*I anfangen kann)



    Noch schneller gehts, wenn man das auf Chars umbaut, oder Pokes. Interessant wäre ein Vergleich /Benchmark zu dem von oben.

    Also, ob das Ur-BASIC das kann, weiß ich nicht. Muß man jeweils nachsehen. Der 64er kann es https://www.c64-wiki.de/wiki/Operatoren , mit (Pfeil nach oben). Der Sharp da sicherlich auch.


    Nur: ob das wirklich was bringt ... (?) ; den in der ALU selbst steht ganz am Ende sowieso entweder noch ein zweites I als Counter und es wird per Schleife durchaddiert (diese Chips können i.a. kein Multiplizieren) ODER es wird einfach in einer Tabelle nachgeschaut, wobei dann gar keine Rechnerei passiert.

    Muß man wahrscheinlich einfach mal ausprobieren,was schneller ist: mein Tip wäre ja, daß es sich nichts nimmt, weil ganz zwanglos I2 vom Interpreter als I*I "gelesen" wird.

    Der macht für 9x9 also 8 Additionszyklen?

    Dann hätte ich noch eine andere Idee, aber die ist wohl besser in Assemblersprache umzusetzen:


    Nehmen wir mal an: 9 x 9

    Man könnte auch rechnen: 9*2 hoch 3 + 9.

    Das sieht aufwendiger aus, ist aber nur ein Bitshift:

    9 = 1001

    72=1001000

    Dann nur noch 72 + 9


    Dürfte wohl besonders bei großen Zahlen einen Vorteil bringen.

    Genau. Üblicherweise wird da einfach addiert. Ein Faktor wird dabei zur Laufvariablen (die lädt man also in ein Register und das zählt man dann einfach bis 0 runter), der andere kommt in den Akku. Geschickterweise natürlich so, daß man möglichst die kleinere Zahl runterzählt.


    Deine Zahlenzerlegung macht schon auch Sinn, aber, das mußt Du dann auch "generisch" können, also für beliebige Zahlen. Bei einer kann man sich das schon schön hinschreiben, aber das 2 hoch 3 sucht man ja explizit raus, weil es hier so schön paßt und die 9 extra kommt auch noch dazu. Sowas gibt es aber natürlich und macht insbesondere Grafik manchmal immens viel schneller.


    edit: von BASIC Seite aus macht es manchmal (meist?) wesentlich mehr Sinn, sich zu überlegen, ob man nicht Berechnungen generell reduzieren oder vermeiden kann (das was Roland_t29 oben mit dem Auflösen der Multiplikation in Zeile 280 vorgeschlagen hat, z.B. (vermeidet dort einfach das "teure" Multiplizieren komplett)) und vor allem natürlich dann, wenn es in Schleifen oder gar geschachtelten Schleifen auftaucht.

    Ein andere Sache, die oft viel bringt, ist Fließkommazahlen zu vermeiden. Das ist in BASIC manchmal ein wenig hakelig, v.a. wenn das "gebastelt" werden muß, aber das bringt i.a. sehr viel schneller Erfolg, als sich Gedanken über die Umstellung der Matheroutinen zu machen. Trotzdem ist auch das ein guter Ansatz, aber eben dann schon das "advanced" Level. (macht aber auch Spaß - kannst ja mal schauen, wie weit Dein Ansatz da trägt) Interessant sind diesbezüglich auch alte Computerzeitschriften so von um 1980. Da gitb es ganz viele solche Optimierungsüberlegungen und Artikel, wie man was schneller bekommen könnte. Kreise etwa sind da ein beliebtes Thema (da geht auch ganz viel). Das meiste davon kann man auch schön verstehen, eine heutige Optimierung versteht man vmtl nicht mehr so einfach (Grafikkarte mitbenutzen, SSE Einheiten, Vektorprozessoren, Nebenläufigkeit gut ausnutzen usf.).




    ---------- ---------- ---------- ---------- ---------- ----------


    noch zu / aus #12


    Quote from guidol

    ChatGPT hat mir eine andere Variante vorgeschlagen, die ist viel schneller - aber wohl etwas unsauber beim verlassen der I-FOR/NEXT-Schleife in 40


    Quote from guidol

    It took 0.292 secs


    und hier - Commodore Plus/4 (xplus4) - braucht es VIEL MEHR Zeit ...


    ( und MEHR ist doch immer besser, oder wie war das noch (?) )



    100 Primzahlen , 5.3 secs1000 Primzahlen , 75.8 secs

    Naja kommt drauf an: entweder du musst die nächstkleineren Potenz von 2 in der Schleife mitlaufen lassen oder du analysierst die Zahl im Speicher wo die erste 1 ist.

    Quadrat von 00100010 = 5 Nullen hinten dran, "10" also 2x mal muss zusätzlich addiert werden.


    Das ist alles sehr komplex, aber wird wohl keine hunderte Zyklen brauchen als wenn 3-stellige Zahlen quadriert werden?