Autor |
Beitrag |
Gammatester
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: Do 03.08.17 16:39
Horst_H hat folgendes geschrieben : | Hallo,
die Crux an diesem Problem ist, dass man nicht einfach nur ausstreichen muss, wie bei einem Primzahlsieb, sondern zählen muss.Die Treffer durch Primzahlen zählen muss.Die gesuchten Quadrupel sind eben keine Primzahlquadrupel, da gibt es viel mehr zu testen.
Am Ende steht und fällt es mit den Langzahltest auf prim. |
Nicht unbedingt: Die Fermat-Tests und die vertrackte Logik sind die Bremsen. Ich denke, daß man Deine Methode noch ein wenig aufbohren könnte: Ist ein kleiner kleiner Teiler gefunden, wird sofort der Fermattest gemacht, der aber (hoffentlich) fehlschlägt, wenn m3 einen Teiler hat, der >= dem gefundenen kleinen kleinen Teiler ist. Also könnte man auch m3 nochmal mit kleinen Teilern bearbeiten, damit ein Fermattest nicht unnötig gemacht werden muß. Allerdings ist dies keine garantierte Verbesserung, sondern hängt von der Primfaktorzerlegung der großem Quadrupel ab.
Besonders blöd wäre es, wenn bei der vierten Quadrupelzahl zwei kleine Teiler gefunden würden, die dann drei Fermattests in die Tonne treten. Irgendwie müßte alle vier Quadrupelzahlel simultan sieben bzw. nach kleinen Faktoren durchsuchen.
Edit: Ich sehe gerade, daß dieser Beitrag vielleicht teilweise überholt ist durch die Darstellung in matheplanet.com/math...mp;start=40#p1677261 .
|
|
Horst_H
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Do 03.08.17 21:33
Hallo,
Ich wollte die Zeit für einen Langzahltest abschätzen, eigentlich die Division /TeilerX und anschliessendem Primtest.+ und - braucht keine Zeit dagegen.
ich habe mal kleine Experimente gemacht mit einer Zahl mit 150 Stellen und dabei die Anzahl der Siebprimzahlen und zum Ende die Größe des Siebes verzehnfacht.
Es lohnt sich bei so hohen Stellenzahlen viele Primzahlen zu nutzen.
Wenn das Feld ohnehin nicht mehr in den CPU Cache passt , kann man es noch größer machen.
Die Primzahlen sind ja schon ab 664579 ? ( da war mal was ) im Bereich von Bereich 10 Mio ~ Siebgröße, die streichen nur jedes 2.te mal, meist wird nur der Übertrag um eine Sieblänge korrigiert, deshalb steigt Siebzeit nur sehr gering.
Von 0,8s -> 1s für 1,5 Mio -> 16.8 Mio Primzahlen. // ~11x
Die Laufzeit sinkt von 2m40s auf 1m48, das ist nicht wenig.
Weil der Langzahltest überproportional mit der Stellenzahl zeitaufwändiger wird, braucht es noch mehr Primzahlen.
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:
| Groesse Sieb = 2*3*5*7*....*17*19 = 9.699.690 ~40 Mb Testzahl '1' gefolgt von 149x'0' ---------- 1.....01824150031 = 71 * 140845....39776761 1.....01824150033 = 61 * 163934....43018853 1.....01824150037 = 2767 * 3614....26318811 1.....01824150039 = 23 * 434782....66267393 Zeit: 00:02:40.802 Anzahl Siebungen 200 Anzahl Langtests 364418 Anzahl TestBereich 1833241410 // 500.000 Primzahlen ---------- Zeit zum vorsieben 00:00:00.082 Zeit zum 10x Sieben 00:00:00.811 = 71 * 1408.. = 61 * 1639.. = 2767 * 36.. = 23 * 4347.. Zeit: 00:02:15.972 -> 135,972 - 16,22 => 119,752 / 297804 == 402 µs / Langtest Anzahl Siebungen 200 -> 16,22 s Anzahl Langtests 297804 Anzahl TestBereich 1833241410 //1.500.000 Primzahlen
Zeit zum vorsieben 00:00:00.124 Zeit zum 10x Sieben 00:00:00.843 = 71 * 1408.. = 61 * 1639.. = 2767 * 36.. = 23 * 4347.. Zeit: 00:02:07.192 -> 127,192-16,86 s =110,332 -> 405 µs /Langtest Anzahl Siebungen 200 -> 16,86s Anzahl Langtests 272081 Anzahl TestBereich 1833241410 //2.500.000 Primzahlen
Zeit zum vorsieben 00:00:00.230 // Primzahlen Suche langsam Zeit zum 10x Sieben 00:00:00.887 = 71 * 1408.. = 61 * 1639.. = 2767 * 36.. = 23 * 4347.. Zeit: 00:01:59.447 = 119,447-17,74-0.230 = 101,477s/ 242129 = 419 µs Anzahl Siebungen 200 -> 17,74 Anzahl Langtests 242129 Anzahl TestBereich 1833241410 //5.000.000 Primzahlen
Zeit zum vorsieben 00:00:00.737 // Primzahlensuche langsam Zeit zum 10x Sieben 00:00:01.049 = 71 * 1408.. = 61 * 1639.. = 2767 * 36.. = 23 * 4347.. Zeit: 00:01:55.149 = 115,149-20,98-0,737 = 93,432s/ 199546 = 468 µs /Langzahltest Anzahl Siebungen 200 -> 20,98s Anzahl Langtests 199546 Anzahl TestBereich 1833241410 //16.777.215 Primzahlen ( 1 shl 24 -1) ---------- Jetzt Sieb 10x ---------- 10x Sieb - >10* 2*3*5...*17*19 = 96.996.900 x4Byte ~ 400 Mb Zeit zum vorsieben 00:00:00.966 // Vorsieb ist auch 400 Mb Zeit zum 10x Sieben 00:00:09.520 = 71 * 1408.. = 61 * 1639.. = 2767 * 36.. = 23 * 4347.. Zeit: 00:01:48.360 0 108,36s- 19,046-0,966 = 88,348s => 443 µs Anzahl Siebungen 20 sein -> 19,046s Anzahl Langtests 199546 Anzahl TestBereich 1842941100 //16.777.215 Primzahlen ( 1 shl 24 -1)
Bei 200 Stellen dauert ein Lanzahltest etwa 920 µs Bei 250 Stellen dauert ein Lanzahltest etwa 1650 µs, die habe ich nur einmal gemessen ;-) |
Stellenzahl ^ n = Laufzeit passt nicht, der Exponent steigt von 1,19..(150)--> 1,34..(250)
n ^ Stellenzahl = Laufzeit passt auch nicht n =1.04--> 1.03
nicht übel ist
n^ sqrt(Stellenzahl) = Laufzeit n = 1,63 -> 1,597
Blödes rumgerate ....
Da kann man besser mit einem Programmschnipsel der nur eine Primzahl der Größe testet abschätzen.
Lange Rede, keinen Sinn es dauert lange....
Wie das HyperG auf matheplanet geschafft hat ?
Zitat: | So, mit 13 parallelen Prozessen und 3,8 Stunden später
habe ich eine 410 stellige Zahl gefunden! |
Wie kommt man auf 410 Stellen ? Grob umgerechnet 49,4 h
1,6^(sqrt(410)) -> etwa 13,6 ms pro Test ( ~ 34x von 150 Stellen ), sieben wird nicht teuerer.
-> 73,6 Test/s ->13.089.024 Tests
13 MIo/200000 = 65x 1842941100 bei etwa +119*1e9 da müsste das Quadrupel aufgetaucht sein.
Das müsste Mathematiker in Erfahrung bringen können.
Natürlich kann man parallel sieben lassen, dann müssten die Überträge seperat geführt werden.
Und ab und an neu berechnen, wenn man jeden Thread 10 Sieb-Abstand gibt.eben alle 10x .
Oder aber man siebt und sammelt die möglichen Quadrupel, aka merkt sich die Position j im Sieb/zahl.
Das dauert ja nur einen Wimperschlag.Dazu braucht es ein m0 als Startzahl des Siebes, das alle threads nutzen können.
Die verteilt man dann auf die n-Threads und gut ist.Im großen Sieb waren das 10000.Da sind die schon gut beschäftigt
Gruß Horst
|
|
Gammatester
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: Do 03.08.17 22:21
|
|
Horst_H
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Do 03.08.17 23:27
Hallo,
das ist ja mal ein Anhaltspunkt.Wobei natürlich der Test nicht immer ganz durchläuft, wenn nicht-prim festgestellt ist.
Ich habe die Zeiten nur für sieben gemessen um feststellen, ob ein mögliches fast primes Quadrupel vorliegt.Komplett ohne mp_inc / copy und div ausser bei der erstmaligen Bestimmung der Überträge ins Sieb.Wer hätte gedacht das nur mp_inc(m1), m4 und das ein copy schon 10% == 0.2 Sekunden ausmachen.
Das kann man im Programm über j/j4 auch regeln und nur bei Bedarf rechnen.Ob ich 145Mio 1 raufzähle oder nur 20000 mal ein longInt mp_add mache, sollte man merken.
Die Laufzeiten sind für alle Stellenzahlen, wie erwartet konstant mit 2s.
Auch die Anzahl der zu testenden Quadrupel in einem Bereich ist auch sehr konstant.
Da gibt es keine Abnahme, bedingt durch begrenzte Anahl an Siebprimzahlen.
Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23:
| Stellenzahl 50 Zeit: Vorsieben 00:00:03.586 // für 1 shl 24 -1 Primzahlen und Bestimmung der Überträge Zeit: Sieben 00:00:02.001 // Zeit für sieben und finden(zählen) Anzahl Siebungen 15 Anzahl Testquadr 20358 Anzahl Langtests 0 TestBereich 145495350 ---------- Stellenzahl 150 Zeit: Vorsieben 00:00:08.611 Zeit: Sieben 00:00:01.988 Anzahl Siebungen 15 Anzahl Testquadr 20561 Anzahl Langtests 0 TestBereich 145495350 ---------- Stellenzahl 450 Zeit: Vorsieben 00:00:24.994 Zeit: Sieben 00:00:01.988 Anzahl Siebungen 15 Anzahl Testquadr 20352 Anzahl Langtests 0 TestBereich 145495350 |
Also sind es 10000 Quadruple/Sekunde, die es zu testen gilt.
Bei 13,6 ms Zeit/Quadruple ( geraten für 410 Stellen ) wären dazu 136 threads nötig
Nicht wirklich mein Rechner.
Bei 100 Stellen reichen vier Threads zum testen und einer zum sieben.
Vielleicht ist gmp viel schneller beim Test auf prim?
Gruß Horst
|
|
Gammatester
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: Do 03.08.17 23:52
Horst_H hat folgendes geschrieben : |
Vielleicht ist gmp viel schneller beim Test auf prim?
Gruß Horst |
Glaube ich nicht, jedenfalls nicht für den Bereich um 200-400 Stellen und den Standard-Primtest: This function performs some trial divisions, then reps Miller-Rabin probabilistic primality tests. Wobei die MR-Tests mit Zufallsbasen gemacht wird. Wenn GMP, dann solltest Du einfach testen, ob 2^(m3-1) = 1 mod m3 ist.
Natürlich ist GMP schneller als MPArith, die Skalierung sollte aber ähnlich sein. Wäre schon interessant zu wissen, um wie viel schneller.
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Fr 04.08.17 07:19
Hallo,
als ich heute früh aufgestanden bin, hatte ich eine "Eingebung". Ich weiß, dann sollte man schnellsten zum Arzt gehen.
Ich habe beim Erzeugen der Primzahlen in deren Liste jetzt ein paar Primzahlquadrate aufgenommen.
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19:
| const quadratzahl = 13; quadrate : array[1..13] of integer = (9,27,81,3*3*3*3,49,7*7*7,121,169,289,361,23*23,29*29,31*31); begin ... for i:=1 to quadratzahl do begin mp_mod_int(m4, quadrate[i], rest); mp_mod_int(m4, 2 * quadrate[i], rest2); with primzahlen[i+1] do begin prPrimZ := quadrate[i]; if (rest <> rest2) then prUebertrag := 2 * prPrimZ - rest else prUebertrag := prPrimZ - rest; end; end; ... end; |
Damit werden auch alle Zahlen ausgesiebt, die z.B. zwei kleine Primfaktoren 3 haben, usw.
Das Ergebnis war für mich überraschend.
Statt 4,1 s bei der Startzahl sind es jetzt noch 3,2 s; also doch etwas Gewinn. Ob man dies noch ausbauen kann, weiß ich nicht.
Steffen
Nachtrag: Beim Experimentieren ist mir aufgefallen, dass ein maximaler kleiner Teiler (jetzt 1000000) bei großen Startzahlen jetzt besser ist. Begründen kann ich es nicht.
Für die Startzahl 10^199 sind es dann nur noch 70 s. Nicht schlecht.
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Horst_H
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Fr 04.08.17 08:46
Hallo,
Zitat: | Nachtrag: Beim Experimentieren ist mir aufgefallen, dass ein maximaler kleiner Teiler (jetzt 1000000) bei großen Startzahlen jetzt besser ist. Begründen kann ich es nicht. |
Der maximal kleine Teiler sollte am besten die größte Primzahl sein, mit der gesiebt wird.
Du erweiterst damit Anzahl der möglichen FastPrim-Quadrupel und scheinbar sind Zahlen, die schon von 999999 kleinen Primzahlen nicht getroffen wurden, auch öfter im zweiten Faktor prim.
Man könnte mal als Obergrenze die höchtse Siebprimzahl einsetzen.
Es geht auch andersherum, wenn man das Ziel schon kennt
Nimm mal des Testbeispiel mit 100 Stellen und schränke auf die Lösungsmenge ein:
untere Grenze 7, obere 1291.Das ist eine ganze Ecke schneller.
Ich vermute, die Anhebung der unteren Grenze wirkt noch viel stärker.
Gruß Horst
P.S.
Zitat: | maximaler kleiner Teiler (jetzt 1000000) |
Ich dachte im Programm wäre es 1 Mio Primzahlen und nicht nur die < 1Mio
P.S.S
Bezüglich Deiner Eingebung, hatte ich jetzt gerade auch eine ( ich wohne neben einer katholischen Kirche, das hilft.Das Spaghetti-Monster ist in Deutschland gescheitert )...
Wir haben doch mal Befreundete Zahlen gesucht.
Dabei habe ich doch parallel beim Eintragen des Faktors auch die Potenz mitgeführt.
Hier brauchte es nur bis zur zweiten Potenz, um Fastprim auszuschliessen.
Aber wie bekomme ich dann die Anzahl bis zum ersten p^2 heraus?
Wenn ich also bei Startzahl mod p= r1 erhalte, müsste ich noch Startzahl mod (p*p)=r2 berechnen, um zu bestimmen, bei welcher Zahl ich auch durch p^2 teilen könnte.Dann wäre mein momentaner Faktor f= r2/r1.
Stimmt nicht ganz, denn wenn r2=r1 wäre f=1, aber ich starte ich schon mit p*p, ich lasse 1 mal gelten.
Wenn Faktor = 1 -> höherere Potenz , dann erhöhe ich mit jedem streichen den Faktor f und wenn er dann p ist bin ich wieder bei einer höheren Potenz von p angelangt und erhöhe dort die Anzahl Streichungen um 2 und beginne wieder bei 1.
Dann muss ich Vorsiebfeld ändern auf 2*3*3*5*7*7*11*11 = 533610 ( 2 und 5 interessieren hier ja nicht).
Bis zu welcher Primzahl lohnt sich der Aufwand?
Bei 997 würde alle 997 besser alle 2x997( gerade fallen weg )um 2 statt um 1 raufgezählt. Das ist ist im Abstand 2*997*997 ~ 2Mio , Bei einer Zahl 1e6 -> 1e12 , dass lohnt sicher nicht
Wenn mindestens einmal im Sieb ein Treffer mit 2 sein sollte, hätte mal ja ein Kriterium.
Bei großen Testzahlen kann sich das vielleicht auch weiter lohnen.
Ich habe mein Programm jetzt zerschossen...Mist....
Zuletzt bearbeitet von Horst_H am Fr 04.08.17 09:27, insgesamt 1-mal bearbeitet
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Gammatester
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: Fr 04.08.17 09:23
Mathematiker hat folgendes geschrieben : | Ich habe beim Erzeugen der Primzahlen in deren Liste jetzt ein paar Primzahlquadrate aufgenommen.
Delphi-Quelltext 1: 2: 3:
| const quadratzahl = 13; quadrate : array[1..13] of integer = (9,27,81,3*3*3*3,49,7*7*7,121,169,289,361,23*23,29*29,31*31); |
Damit werden auch alle Zahlen ausgesiebt, die z.B. zwei kleine Primfaktoren 3 haben, usw.
|
Wäre es nicht günstiger etwa folgende Liste zu verwenden:
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7:
| const quadratzahl = 15; quadrate : array[1..quadratzahl] of integer = (2*3, 3*7, 3*11, 3*13, 3*17, 7*7, 7*11, 7*13, 7*17, 11*11, 11*13, 11*17, 13*13, 13*17, 17*17); |
IMHO sind bei Dir die höheren Primzahlpotenzen 3^3,3^4,7^3 etc überflüssig, weil sie schon durch p^2 erschlagen werden (oder liege ich hier völlig falsch?).
Leider kann ich meinen Vorschlag nicht testen, da ich nicht auf dem aktuellsten Quellcode-Stand bin (habe in Dein Zip vom 1.8. Horst's Unit eingebaut und dort wieder (an vielleicht falscher Stelle) den Vorschlag. Das Programm scheint aber endlos zu laufen.
Für diesen Beitrag haben gedankt: Horst_H, Mathematiker
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Fr 04.08.17 10:04
Hallo Gammatester,
Gammatester hat folgendes geschrieben : |
Leider kann ich meinen Vorschlag nicht testen, da ich nicht auf dem aktuellsten Quellcode-Stand bin (habe in Dein Zip vom 1.8. Horst's Unit eingebaut und dort wieder (an vielleicht falscher Stelle) den Vorschlag. Das Programm scheint aber endlos zu laufen. |
Da sind mir jetzt schon 2.
Ich habe mir gerade meinen Text zerschossen, als ich ihn unter Delphi kompilieren wollte.
Ich melde mich, sobald ich es im Griff habe.
Steffen
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Fr 04.08.17 10:40
Hallo Gammatester,
im 1.Beitrag ist die aktuelle Delphi-Variante.
Ich musste erst einmal die Delphi und Lazarus-Dateien "entwirren". Ich sollte auch nicht 2 Projekte im gleichen Ordner halten.
Zum Sieben mit den Quadratzahlen:
Wenn eine Testzahl z.B. zweimal den Primfaktor 3 hat, wird sie bisher im Feld nur einmal gestrichen und nach dem Siebvorgang hat sie den Streichwert 1 und ist ein Kandidat.
Das wollte ich verhindern.
Streichen mit höheren Potenzen ist Quatsch. Das war eine dumme Idee von mir.
Streichen mit Produkten zweier kleiner Primzahlen brauchen wir nicht, da ja mit jeder der kleinen gestrichen wird.
Im aktuellen Delphi-Text habe ich jetzt für die ersten 20 Primzahlen + die 3 das Streichen mit dem Quadrat drin.
Etwas schneller ist es schon.
Beste Grüße
Steffen
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Gammatester
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: Fr 04.08.17 10:43
Horst_H hat folgendes geschrieben : | Vielleicht ist gmp viel schneller beim Test auf prim? |
Da jetzt offensichtlich alle ihren Quellcode zerschossen habe, habe ich mal zwischendurch einen kleinen Speed-Test gemacht mit dem MPArith/64-Bit-Rechner www.wolfgang-ehrhard...mp_intro.html#t_calc und
Quelltext 1: 2:
| GP/PARI CALCULATOR Version 2.9.3 (released) amd64 running mingw (x86-64/GMP-6.1.2 kernel) 64-bit version |
Für den Bereich 10^400 ist GMP ca 2.1 mal schneller: 16ms vs. 34ms, für 10^1000 sind die Werte 3.3, 63ms, 213ms.
Dabei wurde in mp_calc die Test-Funktion belegt mit:
Delphi-Quelltext 1: 2: 3:
| _TEST: begin mp_set(r,ord(s_mp_is_psp2(v1)) and 1); end; |
Wenn der Algorithmus ausgereizt und 10^1000 realistisch ist, könnte man also noch einen Faktor 2-3 herausholen.
Zuletzt bearbeitet von Gammatester am Fr 04.08.17 10:57, insgesamt 1-mal bearbeitet
Für diesen Beitrag haben gedankt: Horst_H, Mathematiker
|
|
Gammatester
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: Fr 04.08.17 10:54
Mathematiker hat folgendes geschrieben : | Zum Sieben mit den Quadratzahlen:
Wenn eine Testzahl z.B. zweimal den Primfaktor 3 hat, wird sie bisher im Feld nur einmal gestrichen und nach dem Siebvorgang hat sie den Streichwert 1 und ist ein Kandidat.
Das wollte ich verhindern.
Streichen mit höheren Potenzen ist Quatsch. Das war eine dumme Idee von mir.
Streichen mit Produkten zweier kleiner Primzahlen brauchen wir nicht, da ja mit jeder der kleinen gestrichen wird. |
Mach mich mal schlau: Ein Kandidat ist ein Zahl k*(großer Wert) mit k=kleiner Teiler und (kleiner Teiler) wird gesiebt? Wer hindert (großer Wert) daran noch einen kleinen Teiler >= k zu haben?
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Fr 04.08.17 11:01
Gammatester hat folgendes geschrieben : | Mach mich mal schlau: Ein Kandidat ist ein Zahl k*(großer Wert) mit k=kleiner Teiler und (kleiner Teiler) wird gesiebt? Wer hindert (großer Wert) daran noch einen kleinen Teiler >= k zu haben? |
Niemand. Nur scheinbar, sonst wäre es ja nicht etwas schneller (oder habe ich einen bösen Denkfehler), gibt es hinreichend viele Kandidaten, die wohl z.B. zweimal durch 3 aber durch keine weitere kleine Primzahl < maximaler kleiner Teiler teilbar sind.
Anders kann ich es mir nicht erklären.
Steffen
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Gammatester
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: Fr 04.08.17 11:29
Irgendetwas ist bei mir noch faul an Deinem letzten Quellcode: Sowohl D6 (auf zwei Rechnern) aus auch D25/Starter melden Exception: Class TSpinEdit not found. Sehr merkwürdig!
|
|
Horst_H
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Fr 04.08.17 11:31
Hallo,
aus den Backup Dateien neu zusammen gefügt.
Ich habe ein SpinEdit eingbaut, um mir n[1..9] *50 Testzahlen zu erstellen.
Mit Quadrate kleiner Primzahlen werde ich nach dem WE mal testen, natürlich streichen die Quadrate kleiner Primzahlen ein Menge aus.
3*3 kommt sozusagen alle 18 vor ( 9 (18 ist gerade) 27 45 63, streicht also mehr als eine 19, OK da sind noch zusätzlich Treffer anderer Zahlen, aber alle 9x Primzahl werden erwischt und aussortiert.
Gruß Horst
Einloggen, um Attachments anzusehen!
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Fr 04.08.17 11:39
Gammatester hat folgendes geschrieben : | Irgendetwas ist bei mir noch faul an Deinem letzten Quellcode: Sowohl D6 (auf zwei Rechnern) aus auch D25/Starter melden Exception: Class TSpinEdit not found. Sehr merkwürdig! |
Schau mal in die dfm-Datei.
Wenn dort noch Spinedit drin steht, bitte dieses Objekt löschen.
Steffen
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Für diesen Beitrag haben gedankt: Gammatester
|
|
Horst_H
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Sa 05.08.17 17:21
Hallo,
apropos höhere Potenzen von Primzahlen.
Wer hindert einen daran, mit 3*3 7*7 ..11*11.. p*p zu sieben.
Man könnte normal sieben und anschliessend mit ein paar tausend Quadraten von ersten Primzahlen und
dort dann einfach nur eine 2 einzutragen.
Nix mit inc(Speicherstelle) Read-modify-write, bäh...
Alternativ diese Quadratprimzahlen in die Liste der Siebprimzahlen einfügen.Muss ja nicht sortiert sein, wenn es auch Cache-freundlicher wäre.Die Primzahl selbst erhöht mindestens auf eins und die Quadratzahl dann eben passend auf 2.
Das Vorsieb, mit dem man die zeitaufwändigen Primzahlstreichungen der kleinen Primzahlen einspart, macht schon ab 7 wenig Sinn. Denn alle 7*7= 49 wird ein Feld auf 2 gesetzt, da siebe ich doch lieber mit 13,17 , die viel dichter liegen.
Ich habe es umständlicher gemacht, indem ich von den ersten 167 Primzahhlen nicht nur den Übertrag ins Sieb sondern auch deren Quadrates bestimme.Die Differenz als Vielfaches/Multiplikator der Primzahl ist dann ein Zähler, nach p Schritten ist dann wieder eine Quadratzahl erreicht.
Das brachte auch schon etwas. Die 150-stellige Zahl '100...00' wird mit 5 Mio Siebprimzahlen in 1min 36 statt in 00:01:59.447 gefunden.
Gruß Horst
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Horst_H
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Mo 07.08.17 21:43
Hallo,
ich habe mal Mathematiker's Rev 5 etwas modifiziert.
Um immer die passende Langzahl zu haben, werden zwei davon ständig aktualisiert.
Delphi-Quelltext 1: 2:
| mp_inc(m1); mp_inc(m4); |
Dabei gibt es noch die Int-Variablen j und j4, die auch den Index in zahl[..] merken.Deshalb berechne ich die Langzahl nur, wenn eine Testzahl vorliegt, eine Integer-Addition auf die Langzahl geht schnell und ist nur etwa alle 500 nötig.
Auch war eine Teiler von 5 Abfrage im Test auf Quadrupel drin, was einiges an Rechenzeit kostet
Delphi-Quelltext 1: 2: 3: 4: 5:
| mp_add_d(m1, 2, m1); mp_mod_int(m1, 5, rest); if rest = 0 then mp_add_d(m1, 2, m1); |
Das spart schon einiges.
Dann habe ich die Quadratzahlen von kleinen Primzahlen in ein Extra-Feld gepackt.
Zum Vergleich für 100 Stellen:
Die Original Delphi Win32-Exe unter wine 2.0 braucht bei mir:
Quelltext
mit Suche auf 1 min + fertig machen begrenzt:
Jetzt als Lazarus-Win32 Exe unter wine 2.0
Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10:
| 100 53397971 43, 1291, 7, 463 00:00:03.398 101 77526031 7, 3, 3769, 3 00:00:04.662 102 358907441 1481, 7, 359, 1699 00:00:20.449 103 118981061 9421, 7109, 6947, 7 00:00:07.031 104 99900031 19, 3, 37, 3 00:00:06.102 105 61471311 3, 7, 3, 37 00:00:04.189 106 22944281 7, 19, 47, 127 00:00:01.915 107 4261061 31, 7, 1031, 11 00:00:00.761 108 313530491 31, 11, 13, 19 00:00:21.028 Zeit: 01:09.975 |
Jetzt als Lazarus-Linux64.Endlich unter 2 Sekunden für 100-stellig
Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18:
| 100 53397971 43, 1291, 7, 463 00:00:01.685 101 77526031 7, 3, 3769, 3 00:00:02.364 102 358907441 1481, 7, 359, 1699 00:00:10.356 103 118981061 9421, 7109, 6947, 7 00:00:03.539 104 99900031 19, 3, 37, 3 00:00:03.093 105 61471311 3, 7, 3, 37 00:00:02.075 106 22944281 7, 19, 47, 127 00:00:00.925 107 4261061 31, 7, 1031, 11 00:00:00.324 108 313530491 31, 11, 13, 19 00:00:10.424 109 18090611 109, 9463, 17, 563 00:00:00.796 110 20713731 3, 7, 3, 29 00:00:00.869 111 46265411 59, 809, 17, 1163 00:00:01.725 112 140371061 787, 2459, 11, 887 00:00:04.801 113 76378171 7, 3, 31, 3 00:00:02.756 114 137102771 19, 4129, 3739, 521 00:00:05.150 115 181983221 857, 17, 151, 11 00:00:06.984 116 624238811 43, 179, 19, 2789 00:00:23.886 Zeit: 01:21.959 |
Deutlich zu sehen, dass 64-Bit doppelt so schnell ist.
Warum aber die Win64-Version immer ~20% länger brauchen will sich mir nicht erschliessen.
Gruß Horst
[Edit]
Neue Version:
Nur ungerade Zahlen werden gesiebt.Diesmal für für sehr lange Zahlen optimiert.
Alleine das Vorbereiten des Zahlsiebes und die Berechnung der Überträge der 16.777.215 Primzahlen dauert 20 Sekunden bei mir.Dafür wird es insgesamt schneller:
Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12:
| Zuvor: 301 1557971731 4349, 11, 3847, 13 00:09:36.374 jetzt: 301 1557971731 4349, 11, 3847, 13 00:08:22.480 302 250233211 7, 97, 19, 152419 00:01:36.130 303 1800073801 303917, 79, 17, 43 00:09:55.318 304 4587564621 3923, 3, 269, 3 00:24:58.628 305 2078310421 47, 53, 5591, 13721 00:11:28.176 306 1530771211 79, 26029, 1423, 1381 00:08:38.098 307 1386249451 7, 849221, 11, 43 00:07:49.874 308 407647731 661, 3, 13, 3 00:02:31.984 309 4995074881 13, 43, 7, 1039 00:27:41.190 |
Einloggen, um Attachments anzusehen!
Zuletzt bearbeitet von Horst_H am Sa 12.08.17 14:48, insgesamt 1-mal bearbeitet
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Gammatester
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: Mo 07.08.17 22:19
Horst_H hat folgendes geschrieben : | Deutlich zu sehen, dass 64-Bit doppelt so schnell ist.
Warum aber die Win64-Version immer ~20% länger brauchen will sich mir nicht erschliessen. |
Das könnte zB am lahmen Default-Memory-Manager liegen, habe ich schon häufiger gesehen. Mit der aktuellen MPArith V1.35.07 habe ich bei mir den Effekt, daß die Zeiten für 500000! mit Default-MM 7.972s und mit cmem 7.158s, also ca 11% (reproduzierbar). Für FPC füge ich beim uses im Hauptprogramm nur ein Delphi-Quelltext 1: 2: 3:
| {$ifdef FPC} cmem, {$endif} | Ich weiß allerdings nicht, ob es unter Lazarus möglich ist, den cmem-MM zu verwenden, da ich Laz nicht benutze.
Für diesen Beitrag haben gedankt: Horst_H, Mathematiker
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Mo 07.08.17 22:49
Hallo Horst,
Horst_H hat folgendes geschrieben : |
ich habe mal Mathematiker's Rev 5 etwas modifiziert.
...
Deutlich zu sehen, dass 64-Bit doppelt so schnell ist.
|
Wie machst du das? Langsam wird es mir umheimlich.
Für die Startzahl 10^199 braucht mein Rechner nur noch 60 s, also wieder deutlich schneller.
Ich werde mir alles genau ansehen und kann nur lernen.
Tiefe Verbeugung und vielen Dank
Steffen
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
|