Fastprime Quadrupel und Primzahlvierlinge

Gammatester · Beiträge: 328 Erhaltene Danke: 101

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 · 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.

markieren

Quelltext

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 user profile icon

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

Horst_H hat folgendes geschrieben :

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 ....

Beim Fermattest für eine Zahl mit n Bits werden n Quadrierungen, n Montgomery-Reduktionen und durchschnittlich n/2 Shifts+Addition benötigt. Wenn man sehr vereinfacht annimmt, daß man sich dauernd im Karatsuba-Bereich befindet, sollten die Zeiten ungefähr wie a*bitsize^1.59 bzw. b*Stellenzahl^1.59 skalieren.

Horst_H · 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.

markieren

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

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 · 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. :wink:

Ich habe beim Erzeugen der Primzahlen in deren Liste jetzt ein paar Primzahlquadrate aufgenommen.

markieren

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 · 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....

Gammatester · Beiträge: 328 Erhaltene Danke: 101

Mathematiker hat folgendes geschrieben :

Ich habe beim Erzeugen der Primzahlen in deren Liste jetzt ein paar Primzahlquadrate aufgenommen.

markieren

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:

markieren

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.

Mathematiker · 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 · 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. :autsch:

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

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

markieren

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:

markieren

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.

Gammatester · Beiträge: 328 Erhaltene Danke: 101

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 · 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

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 · 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 · 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

Horst_H · 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

Horst_H · Verfasst: Mo 07.08.17 21:43

Hallo,

ich habe mal user profile icon

Mathematiker's Rev 5 etwas modifiziert.
Um immer die passende Langzahl zu haben, werden zwei davon ständig aktualisiert.

markieren

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

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:

//nachfolgende Quadrupelzahl
              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:

markieren

Quelltext

1:	Zeit: 00:00:04.395

mit Suche auf 1 min + fertig machen begrenzt:
Jetzt als Lazarus-Win32 Exe unter wine 2.0

markieren

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 :-)

markieren

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:

markieren

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!

Gammatester · Beiträge: 328 Erhaltene Danke: 101

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

markieren

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.

Mathematiker · Verfasst: Mo 07.08.17 22:49

Hallo Horst,

Horst_H hat folgendes geschrieben :

ich habe mal user profile icon

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 :flehan:

und vielen Dank
Steffen

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme