Fastprime Quadrupel und Primzahlvierlinge - Algorithmen, Optimierung und Assembler - Sonstige Programmierung - Entwickler-Ecke

Entwickler-Ecke

▼ Forum: Delphi, C#, WebDev

Login

Registrieren

Autor

Beitrag

Delphi-Laie
ontopic star

Beiträge: 1600
Erhaltene Danke: 232

Delphi 2 - RAD-Studio 10.1 Berlin

Verfasst: Mo 31.07.17 20:30

Mathematiker hat folgendes geschrieben :

2. Kann jemand von euch den Quelltext einmal mit einem 64bit-Delphi übersetzen und mir die Exe senden (ich weiß nicht, ob das legal ist)?

Die Weitergabe der Compilate ist rechtlich unproblematisch.

Ansonsten gib den Versuch auf, in bezug auf Geschwindigkeit die Nase vorn zu behalten. Sofern der gleiche Algorithmus zugrundeliegt, ist es aussichtslos, Delphi- mit C-Compilaten mithalten zu lassen (sofern nicht mit Assembler "gemogelt" wird). Delphi hat andere Stärken, so z.B. tendenziell geringere Entwicklungszeiten.

Für diesen Beitrag haben gedankt: Mathematiker

Horst_H
ontopic star

Beiträge: 1652
Erhaltene Danke: 243

WIN10,PuppyLinux
FreePascal,Lazarus

Verfasst: Mo 31.07.17 20:49

Hallo,

@ user profile icon

Gammatester
s_mp_nextprime_sieve kann man schneller machen, wenn man vorgesiebte Zahlen nimmt.
Wenn man 2,3,5,7,11,13 siebt wiederholt sich das Muster alle 2*3*5*7*11*13 = 30030, wenn man die 1 wieder setzt und 2,3,5,7,11,13 entfernt.Das kann noch weiter (17,19.. ) treiben, wird aber unhandlich.
Wenn Deine Siebgröße ein Vielfaches von 30030 wäre, könntest Du diese vorgesiebten Zahlen direkt einfügen und bräuchtest erst mit 17 beginnen.Wenn man dann noch in 8 Bit die möglichen Primzahlen von 1..30 ( fehlen eben Vielfache von 2,3,5 ) nutzt, wird es sehr kompakt. mit 1001 Byte pro 30030 bei 32KB Level-1 Cache kommt man schon auf 32*30030= 960960 Zahlen für ein Sieb.

Siebnummer = Zahl / 30030;
Sieboffset = Zahl mod 30030

Etwas rechnerischer Aufwand wäre die erstmalige Bestimmung des Übertrages der 800.000 Streichprimzahlen, bei den riesigen Zahlen... (800.000 * 11 Division ( 100 Dezimalen im 2^31 longint- Format, sind 11 LongInts ( 2^(11*31 ) ) etwa 1 Sekunde schätze ich) )
Wenn ich jetzt sehe, das nach 64 Mio schon ein Quadrupel gefunden wird...
Du nutzt ja nur ungerade Zahlen als Bits gespeichert.
Habe ich auch mal mit boolean getan, bei Sieb mit Startzahl.Um 4 Sekunden für 4e9 ( immer noch Haswell 3.5 Ghz )
Wenn man einmal die Überträge hat, kann man einfach kontinuirlich sieben, indem man nicht die absolute Zahl speichert sondern nur die Anzahl der Siebe bis man wieder mit einer Zahl streichen muss und den Übertrag dort.Bei jedem Durchgang zählt man die um eins runter und bei Null beginnt man bei dem gespeicherten Übertrag weiter zu machen.
Also ein Sieb mit begrenzter Zahl an Siebprimzahlen sieben und dann nur die möglichen Quadrupel auf probably prime testen.
Ich gespannt,was das hier ergibt,

Gruß Horst

Einloggen, um Attachments anzusehen!

Für diesen Beitrag haben gedankt: Gammatester, Mathematiker

Gammatester
ontopic star

half ontopic star

Beiträge: 328
Erhaltene Danke: 101

Verfasst: Mo 31.07.17 21:31

Horst_H hat folgendes geschrieben :

Hallo,

@ user profile icon

Gammatester
s_mp_nextprime_sieve kann man schneller machen, wenn man vorgesiebte Zahlen nimmt.

Kann sein, aber wie Du schon geschrieben hast, die Bestimmung der Primzahlen macht den Kohl nicht fett, die meiste Zeit wird für dem Fermat- und den BPSW-Test verbraucht.

@ user profile icon

Mathematiker Hier eine dramatische Verbesserung:

ausblenden

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:

Primzahlberechnung: 0,2378 s 
Test bis 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110 + 20000000
Kandidaten = 4385
Test bis 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111131111110 + 20000000
Kandidaten = 4535
Test bis 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111151111110 + 20000000
Kandidaten = 4490
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509081
  = 43 · 25839793281653746770025839793281653746770025839793281653746770025839793281653746770025839794523467
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509083
  = 1291 · 860659264996987692572510543075996213099234013254152680953610465616662363370341681728203804155313
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509087
  = 7 · 158730158730158730158730158730158730158730158730158730158730158730158730158730158730158730166358441
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509089
  = 463 · 2399808015358771298296136309095272378209743220542356611471082313414926805855531557475401967957903
Zeit: 8,719 s 
----------

Dies wird erreicht durch die Ersetzung

ausblenden

Delphi-Quelltext

1:
2:
3:

 
//ergeb:=mp_is_pprime(m3);
ergeb :=  mp_is_spsp_d(m3,2) and mp_is_slpsp(m3);

damit spart man sich den doppelten Test auf kleine Faktoren.

Für diesen Beitrag haben gedankt: Mathematiker

Mathematiker Threadstarter

half ontopic star

Beiträge: 2622
Erhaltene Danke: 1447

Win 7, 8.1, 10
Delphi 5, 7, 10.1

Verfasst: Mo 31.07.17 21:32

Hallo,
und erst einmal an alle Danke für die vielen Anregungen.
Ich habe jetzt einiges berücksichtigt, u.a. die Ausgaben während der Rechnung reduziert, aber vor allem Gammatesters Primzahlsieb eingebaut. Das ist richtig schnell.

Außerdem bin ich zum Delphi 5-Compiler zurück, da die Exe ein klein wenig fixer ist. Die maximale Stackgröße muss aber auf $00800000 gesetzt werden.

Im Matheforum haben sich die Anderen darauf geeinigt, für den Primzahltest nur einen Fermattest zur Basis 2 zu verwenden, da sehr große Tupel ohnehin über www.alpertron.com.ar/ECM.HTM nachgeprüft werden.
Deshalb habe ich auch Gammatesters Fermattest eingebaut.

Alle zusammen dauert die Rechnung für (10^100-1)/9 - 1 nur noch 9,14 s. Hauptursache ist der schnellere Fermattest.
Der Anhang ist wieder geändert.

@Delphi-Laie: Dass C i.A. schnellere Exen liefert, ist klar. Aber ohne eine sehr schnelle Langzahlarithmetik, wie mp_arith, geht es nicht.
Wir werden sehen, wie schnell das Programm sein wird.

Die anderen Hinweise sehe ich mir noch an, insbesondere das Primzahlsieb. Vielleicht kann noch etwas Zeit gewonnen werden.
Eigentlich ist die Suche nach diesen Zahlen vollkommen ohne Bedeutung. Ich finde es aber gerade reizvoll zu testen, wie weit man ein Verfahren noch optimieren kann.
Mein allererster Versuch benötigte für (10^64-1)/9 noch 1053 Sekunden, jetzt sind es noch 1,04 s. So etwas finde ich schön.

Beste Grüße und nochmals Danke für die bisherige Hilfe
Steffen

@Gammatester: Ich habe gerade den neuen Eintrag gesehen. Danke.

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

Gammatester
ontopic star

half ontopic star

Beiträge: 328
Erhaltene Danke: 101

Verfasst: Mo 31.07.17 22:02

Mathematiker hat folgendes geschrieben :

Dass C i.A. schnellere Exen liefert, ist klar. Aber ohne eine sehr schnelle Langzahlarithmetik, wie mp_arith, geht es nicht.
Wir werden sehen, wie schnell das Programm sein wird.

Richtig, aber schnelle Arithmetik ist nicht alles. gmplib.org/ ist wahrscheinlich sau-schnell, aber es fehlen halt einige High-Level-Funktionen für Zahlentheorie (Fermat-Test ist wohl vorhanden, weil der für Miller-Rabin/RSA gebraucht wird). Soweit ich das sehe, gibt es für eine ältere Version ein GMP-FPC-Interface.

Für diesen Beitrag haben gedankt: Mathematiker

Horst_H
ontopic star

Beiträge: 1652
Erhaltene Danke: 243

WIN10,PuppyLinux
FreePascal,Lazarus

Verfasst: Di 01.08.17 17:23

Hallo,

ein bisschen was geht beim Sieben.Bei mir jetzt statt fast 7s nun 5,6s.
Ich speichere bei den Primzahlen die Überträge mit ab, sodass nur bei der Erstellung der Primzahlliste der erste Übertrag ins Siebfeld berechnet werden muss und nicht bei jedem neuen Sieb.Das Sieb habe ich 1e6 verkleinert, dass es in den Level-2 Cache passt, das bringt ungefähr nichts bis garnichts ;-)

;-)

Aber mit 1,5 bis 3,5 Mio Primzahlen zu sieben bringt etwas.Wenn man bedenkt, das die Primzahlen schon erheblich größer als das Sieb sind.
Mir fehlt eine zündende Idee die kleine Primzahl auch zu kompakt im Sieb zu speichern.Momentan schwebt mir etwas wie Anzahl als Byte und Streichprimzahlnr shl 8 vor. Dann hätte ich 24 Bit für Primzahlindex-> 16,7 Mio..
Da es keine 250 Streichungen für Zahlen mit 100 Dezimalen gibt, könnte das klappen.
Damit hätte man den kleinen Teiler < Obergrenze == 10000 schon sicher gefunden und könnte bei einem Index > 1228 ( die 5 fehlt ) schon direkt eine Prüfung sparen.

Gruß Horst

Zuletzt bearbeitet von Horst_H am Mi 02.08.17 12:07, insgesamt 1-mal bearbeitet
Für diesen Beitrag haben gedankt: Mathematiker

Mathematiker Threadstarter

half ontopic star

Beiträge: 2622
Erhaltene Danke: 1447

Win 7, 8.1, 10
Delphi 5, 7, 10.1

Verfasst: Di 01.08.17 18:41

Hallo Horst,
Danke für deine Änderungen.
Ich habe es probiert und bin begeistert, da deutlich schneller.

Seit 1 Stunden versuche ich nun herauszufinden, warum bei den Startzahlen
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110
und
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111120
völlig unterschiedliche Zahlen herauskommen.
Im 1.Fall tolle 7,84 s, im 2.Fall das Doppelte, nämlich 15,2 s.
Ich habe keine Ahnung.

Beste Grüße
Steffen

Nachtrag: Ich habe es gefunden. Bei

ausblenden

Delphi-Quelltext

1:
2:
3:
4:
5:

  with primzahlen[1] do
  Begin
    prPrimZ :=3;
    prUebertrag := 3-rest;
  end;

war ein p 'reingerutscht.
Super, damit sind es 15 % Zeitgewinn.

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

Gammatester
ontopic star

half ontopic star

Beiträge: 328
Erhaltene Danke: 101

Verfasst: Di 01.08.17 19:38

Mathematiker hat folgendes geschrieben :

Hallo Horst,
Danke für deine Änderungen.
Ich habe es probiert und bin begeistert, da deutlich schneller.

Seit 1 Stunden versuche ich nun herauszufinden, warum bei den Startzahlen
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110
und
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111120
völlig unterschiedliche Zahlen herauskommen.
Im 1.Fall tolle 7,84 s, im 2.Fall das Doppelte, nämlich 15,2 s.
Ich habe keine Ahnung.

Ich habe ähnliches festgestellt (mit Deinem alten Progamm), wenn ich die Einstellung kleiner Teiler maximal ändere. Hier für
default 10000

ausblenden

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:

1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509081
  = 43 · 25839793281653746770025839793281653746770025839793281653746770025839793281653746770025839794523467
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509083
  = 1291 · 860659264996987692572510543075996213099234013254152680953610465616662363370341681728203804155313
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509087
  = 7 · 158730158730158730158730158730158730158730158730158730158730158730158730158730158730158730166358441
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509089
  = 463 · 2399808015358771298296136309095272378209743220542356611471082313414926805855531557475401967957903
Zeit: 13,7 s

und für 1000

ausblenden

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:

1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111253982611
  = 7 · 158730158730158730158730158730158730158730158730158730158730158730158730158730158730158730179140373
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111253982613
  = 13 · 85470085470085470085470085470085470085470085470085470085470085470085470085470085470085470096460201
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111253982617
  = 23 · 48309178743961352657004830917874396135265700483091787439613526570048309178743961352657004837129679
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111253982619
  = 673 · 1650982334489020967475648010566286940729734191844147267624236420670298827802542512795113092502203
Zeit: 30,2 s

Ich vermute, daß eine andere Kandidatenwahl stattfindet, d.h. daß die Kandiatenwahl von diesem (und ev. anderen Parametern abhängt) und nicht für alle Parameter dieselbe ist. Bei kleineren max. Teiler, dürften sonst nur ein paar Zahlen beim Elimiminieren der kleinen Teiler als prim durchgehen, die dann aber durch den Fermat-Test erschlagen werden.

Für diesen Beitrag haben gedankt: Mathematiker

Mathematiker Threadstarter

half ontopic star

Beiträge: 2622
Erhaltene Danke: 1447

Win 7, 8.1, 10
Delphi 5, 7, 10.1

Verfasst: Di 01.08.17 19:45

Hallo Gammatester,

Gammatester hat folgendes geschrieben :

Ich habe ähnliches festgestellt (mit Deinem alten Progamm), wenn ich die Einstellung kleiner Teiler maximal ändere.

Das ist klar. Ich nutze deine Funktion

ausblenden

Delphi-Quelltext

1:	mp_small_factor(m1,minteiler,maxteiler,teilerx);

Dann wird im 2.Beispiel die 1291 aus dem 1. nicht erkannt.

Beste Grüße
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

Gammatester
ontopic star

half ontopic star

Beiträge: 328
Erhaltene Danke: 101

Verfasst: Di 01.08.17 19:49

Mathematiker hat folgendes geschrieben :

Das ist klar. Ich nutze deine Funktion

ausblenden

Delphi-Quelltext

1:	mp_small_factor(m1,minteiler,maxteiler,teilerx);

Dann wird im 2.Beispiel die 1291 aus dem 1. nicht erkannt.

Natürlich, jetzt kommt es wieder. Du suchst ja Semi-Primzahlen, und der (zeitaufwendige) Test findet nur für den großen Teiler statt. Richtig?

Mathematiker Threadstarter

half ontopic star

Beiträge: 2622
Erhaltene Danke: 1447

Win 7, 8.1, 10
Delphi 5, 7, 10.1

Verfasst: Di 01.08.17 19:51

:zustimm:

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

Gammatester
ontopic star

half ontopic star

Beiträge: 328
Erhaltene Danke: 101

Verfasst: Di 01.08.17 20:47

Noch eine kleine Verbesserung: Mit den neuen Erkenntnissen habe ich auch für den Primzahlcheck des großen Teilers eine Suche nach kleinen Faktoren eingefügt. Dies bringt bei Delphi6 aus der IDE ca. 7% (von 10.6s nach 9.9). Die Code-Änderungen in Button1Click:

ausblenden

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

const
    MAXTM3 = 512;       {maximaler kleiner Teiler für m3}
var
    tb: mp_digit;
...
            mp_div(m1,m2,m3);
            //Primzahltest des grossen Faktors  ergeb ist true, wenn Primzahl
            if teilerx <= MAXTM3 then begin
              mp_small_factor(m3,teilerx,MAXTM3,tb);
            end
            else tb := 0;
            ergeb:= (tb=0) and s_mp_is_psp2(m3);       //Fermattest

Für diesen Beitrag haben gedankt: Mathematiker

Mathematiker Threadstarter

half ontopic star

Beiträge: 2622
Erhaltene Danke: 1447

Win 7, 8.1, 10
Delphi 5, 7, 10.1

Verfasst: Di 01.08.17 21:14

Hallo Gammatester,
Danke für die Verbesserung. Bei mir sind es knapp 10 %.

Beste Grüße
Steffen

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

Horst_H
ontopic star

Beiträge: 1652
Erhaltene Danke: 243

WIN10,PuppyLinux
FreePascal,Lazarus

Verfasst: Mi 02.08.17 12:02

Hallo,

endlich komme ich mit Lazarus 1.8 RC1 Linux-64Bit unter 3s und mit Lazarus 1.8 RC3 unter Wine 2.0 32-Bit unter 5s

Aber nur, wenn ich die Labelausgabe abschalte, die kostet enorm Zeit :-(

:-(

-> unter wine dann 6s.
Ein bisschen Trickserei ist nötig, denn unter CPU64 ist mparith auch fast doppelt so schnell und deshalb lohnt sich das exzessive sieben auch nicht.Also nur 0.75 statt 1.8 Mio Siebprimzahlen.

ausblenden

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:

const
{$IFDEF CPU64}
  groesse = 1000 * 1000;
  anzahl_primzahlen = 750 * 1000;
{$ELSE}
  groesse = 1000 * 1000;
  anzahl_primzahlen = 1800 * 1000;
{$ENDIF}
  MAXTM3 = 512;

Ich siebe jetzt mit doppelter Schrittweite, dafür muss der Übertrag anders bestimmt werden.
Das bringt nicht mehr viel.

ausblenden

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:

  prime_sieve_init(sieve, 7);
  i := 2;
  repeat
    p := prime_sieve_next(sieve);
    mp_mod_int(m4, p, rest);
    mp_mod_int(m4, 2 * p, rest2);
    with primzahlen[i] do
    begin
      prPrimZ := p;
      if (rest <> rest2) then
        prUebertrag := 2 * prPrimZ - rest
      else
        prUebertrag := prPrimZ - rest;
    end;
    Inc(i);
  until i > anzahl_primzahlen;// war vorher = -> die letzte primzahlen war 0 , nicht nett ;-)
  prime_sieve_clear(sieve);

Die Multiplikation der vier aufeinanderfolgenden Werte habe ich durch eine if-Kette ersetz, das ist ein paar ms schneller, eher in der Messtoleranz.
Mein Versuch mit der Abspeicherung von TeilerX brachte noch nichts, irgendwann hatte ich einen Wurm oder doch nur einen Käfer drin.

ausblenden

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:

//i ist der Index in die Primzahlen shl 8 aka *256 
    while (isieb <= groesse) do
    begin
      zahl[isieb] := ((zahl[isieb] + 1) and $000000FF) + i;
      Inc(isieb, p);
    end;
    inc(pPrim);
    inc(i,256);

und dann

ausblenden

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

const
  deltaP: array[1..4] of integer = (0, 2, 6, 8 );
...
if ((zahl[j] and $FF) = 1) and ((zahl[j + 2] and $FF) = 1) and
        ((zahl[j + 6] and $FF) = 1) and ((zahl[j + 8] and $FF) = 1) then
      begin
        Inc(testzahl);
        p := 1;
        repeat
          ergeb := False;
          //kleinen Faktor hervorkramen
          teilerx := primzahlen[Zahl[j + deltaP[p]] shr 8].prPrimZ;

Schauen mer mal, denn sehen mer schon....

Gruß Horst

[EDIT]
Fehler gefunden, bei der Vermeidung der Bestimmung von teilerX.Unter 64-Bit doch deutliche 0.6s schneller.
Statt 2.9s nun 2.3s :-)

:-)

ausblenden

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509081
  = 43 * 25839793281653746770025839793281653746770025839793281653746770025839793281653746770025839794523467
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509083
  = 1291 * 860659264996987692572510543075996213099234013254152680953610465616662363370341681728203804155313
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509087
  = 7 * 158730158730158730158730158730158730158730158730158730158730158730158730158730158730158730166358441
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509089
  = 463 * 2399808015358771298296136309095272378209743220542356611471082313414926805855531557475401967957903
Zeit: 00:00:02.269
----------

32-bittig ist es nur 0.1 s schneller, 4.8s statt 4.9s
[EDIT 2]
Ich habe mal cross-compilieren probiert, geht ja einfach...
32-bittig wird schneller

ausblenden

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

Linux 64 fpc 3.1.1  ( experimentell )
...  = 463 * 2399808015358771298296136309095272378209743220542356611471082313414926805855531557475401967957903
Zeit: 00:00:02.407
----------
Win64 und wine 2 fpc 3.1.1
...   = 463 * 2399808015358771298296136309095272378209743220542356611471082313414926805855531557475401967957903
Zeit: 3.308 s 
----------
Linux32 fpc 3.1.1
...   = 463 * 2399808015358771298296136309095272378209743220542356611471082313414926805855531557475401967957903
Zeit: 00:00:04.273
----------
Win32 und wine 2 fpc 3.1.1
...   = 463 * 2399808015358771298296136309095272378209743220542356611471082313414926805855531557475401967957903
Zeit: 4.809 s 
----------

Einloggen, um Attachments anzusehen!

Zuletzt bearbeitet von Horst_H am Mi 02.08.17 17:30, insgesamt 1-mal bearbeitet
Für diesen Beitrag haben gedankt: Mathematiker

Mathematiker Threadstarter

half ontopic star

Beiträge: 2622
Erhaltene Danke: 1447

Win 7, 8.1, 10
Delphi 5, 7, 10.1

Verfasst: Mi 02.08.17 15:26

Hallo Horst,
Danke für deine Verbesserung.
Leider komme ich erst morgen nachmittag an meinen Rechner 'ran.
Ich werde es dann sofort ausprobieren.

Steffen

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

Mathematiker Threadstarter

half ontopic star

Beiträge: 2622
Erhaltene Danke: 1447

Win 7, 8.1, 10
Delphi 5, 7, 10.1

Verfasst: Do 03.08.17 12:46

Hallo Horst,
vielen Dank für deine neuerlicher Verbesserung des Programms.
Es wird mir immer rätselhafter, wie du immer wieder noch mehr aus einem Algorithmus herausholen kannst. Einfach sensationell.

Ich habe das Programm getestet und es war bei mir wieder eine Sekunde für die Startzahl aus den vielen Einsen.
Noch besser wurde es bei der 200stelligen Startzahl 10^199.
Danach habe ich deine Lösung unter dem aktuellen Lazarus als 64bit-Programm kompiliert und war überrascht.

Bei meinem Win8 braucht das Programm nur noch 144 Sekunden für 10^199, im Gegensatz zu den mehr als 200 s im 32bit-Fall. Ob das auch bei anderen so ist, weiß ich nicht.

Ich hänge hier das Lazarus-Projekt an. Hoffentlich habe ich alle notwendigen Dateien im ZIP-File.

Nochmals Danke
Steffen

Einloggen, um Attachments anzusehen!

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

Horst_H
ontopic star

Beiträge: 1652
Erhaltene Danke: 243

WIN10,PuppyLinux
FreePascal,Lazarus

Verfasst: Do 03.08.17 13:35

Hallo,

wie oben schon einmal bemerkt, mparith von user profile icon

Gammatester wird mit 64-Bit auch fast doppelt so schnell.

Ich habe gerade das Sieb geändert und auf eine Länge von 2*3*5*7*...*17 = 510510 gebracht.
Das dann wie beim wheel-sieving genutzt werden kann.Alle 510510 wiederholen sich die Streichungen für Primzaheln von 2..17.
Das Feld berechnen ich nur einmal und kopiere es beim Sieben in zahl[] und siebe dann ab 19.
Ich dachte zuerst, ich müsste auch erst den Übertrag des Feldes in die riesige Zahl berechnen.Tut aber nicht nötig, denn es ist ein Rad und wo ich beginne ist Wurst-egal, die Runde bleibt gleich lang, solange die Groesse von Zahl ist ein Vielfaches davon ist, kein Problem.
Wie Du Dir denken kannst bringt das nichts :-(

:-(

ausblenden

Quelltext

1:
2:
3:

  = 463 * 2399808015358771298296136309095272378209743220542356611471082313414926805855531557475401967957903
Anzahl Siebungen 105
Zeit: 00:00:02.314

Die Prüfung der Zahlen ist der Verbrecher ;-)

;-)

Es wäre zu überlegen, die Anzahl der Siebprimzahlen zu erhöhen, je länger die Zahlen werden.
Auf 10^199 habe ich nicht warten wollen...

Gruß Horst

Für diesen Beitrag haben gedankt: Mathematiker

hydemarie
ontopic star

Beiträge: 475
Erhaltene Danke: 51

Verfasst: Do 03.08.17 14:25

Mathematiker hat folgendes geschrieben :

PS: Es wäre nicht schön, wenn so ein "komisches" C-Programm unser geliebtes Delphi schlägt. :wink:

:wink:

Schreib's doch in Inline-ASM.

(Allerdings: In puncto Geschwindigkeit wird's wohl schwierig, hochoptimierte C++-Compiler davon abzuhalten, die neuesten fiesen CPU-Funktionen auszunutzen.)

32-Bit-ASM auf 64 Bit zu portieren ist jetzt aber kein allzu gewaltiges Problem, wenn das Programm hinterher nicht allzu viel können muss. Die Register heißen nur anders und einige Zahlen sehen anders aus. (Das ist jetzt etwas vereinfacht ausgedrückt.)

Horst_H
ontopic star

Beiträge: 1652
Erhaltene Danke: 243

WIN10,PuppyLinux
FreePascal,Lazarus

Verfasst: Do 03.08.17 14:56

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.
Bei der Beispielzahl des Programmes sind es bis zur Erreichung der Lösung nur etwa 11000 Langzahl-Divisionen und -Primtests(, bie 500.000 Testprimzahlen.

Gruß Horst
P.S:
Einmal mit 16.777.215 Primzahlen( mehr geht so einfach nicht ) im 2*3*..*17*19 (=9.699.690 ) grossen Sieb gesucht:
Alleine die Zeit bis zur ersten Anzeige( Erstellung der Primzahlen, erstes Sieb (0.2 s) ) war 6s und paar gequetschte.
Zeit bis zur Lösung bei [99x]1_0 fast 5000 weniger Langzahltests.
und für [198x1]_0 // war über 7min20smit 5 Mio Primzahlen.

ausblenden

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:

1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509081
  = 43 * 25839793281653746770025839793281653746770025839793281653746770025839793281653746770025839794523467
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509083
  = 1291 * 860659264996987692572510543075996213099234013254152680953610465616662363370341681728203804155313
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509087
  = 7 * 158730158730158730158730158730158730158730158730158730158730158730158730158730158730158730166358441
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111164509089
  = 463 * 2399808015358771298296136309095272378209743220542356611471082313414926805855531557475401967957903
Zeit: 00:00:07.963
Anzahl Siebungen   6
Anzahl Langtests   6094
TestBereich 58198140
----------
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111114621127981
  = 113 * 9832841691248770894788593903638151425762045231071779744346116027531956735496558505408062930186823992133726647000983284169124877089478859390363815142576204523107177974434611602753195673549686912637
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111114621127983
  = 11 * 101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101329193453
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111114621127987
  = 37 * 30030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030030124895351
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111114621127989
  = 193 * 5757052389176741508347725964306275187104202648244099021301093839953943580886586067933218192285549798503166378814047207829591249280368451352907311456534254461715601611974668969487622337363288192373
Zeit: 00:06:41.681
Anzahl Siebungen   362
Anzahl Langtests   377211
TestBereich 3511287780
----------

Für diesen Beitrag haben gedankt: Mathematiker

Gammatester
ontopic star

half ontopic star

Beiträge: 328
Erhaltene Danke: 101

Verfasst: Do 03.08.17 15:50

hydemarie hat folgendes geschrieben :

32-Bit-ASM auf 64 Bit zu portieren ist jetzt aber kein allzu gewaltiges Problem, wenn das Programm hinterher nicht allzu viel können muss. Die Register heißen nur anders und einige Zahlen sehen anders aus. (Das ist jetzt etwas vereinfacht ausgedrückt.)

Das Umschreiben auf 64-Bit-Assembler ist das kleinste Problem.

Das Hauptproblem, die zitierte Funktion 64-bittig zu machen, ist daß der Algorithmus geändert werden. Für 32-Bit-Tests reichen halt drei starke Pseudoprimzahltests mit den Basen 2,7,61, aber nicht für 64-Bit. Für n < 341550071728321 ~ 2^48 reichen SPSP mit 2, 3, 5, 7, 11, 13 und 17, siehe primes.utm.edu/prove/prove2_3.html ).

Durch komplettes Nachrechnen habe einige Leute rausgefunden, daß für 64-Bit ein BPSW-Test reicht (das ist der gleiche Test, den mein mp_ispprime genutzt), nur ist der nicht mehr so billig zu haben. (Eine Liste von SPSP brauchte CPU-Jahre zum Berechnen, www.janfeitsma.nl/math/psp2/index, Many CPU years have been spent on the computating facilities of the University of Groningen). Mit dieser Liste wurde BPSW-64 verifiziert. Eine 64-Bit-C-Implementation findet man hier: www.trnicely.net/misc/bpsw.html. Wenn Du genau hinsieht, entdeckst Du, daß dort ein SPSP-2 gemacht wird.

Im Kontext sind allerdings die kleinen Primzahltests hier völlig irrelevant und werden entweder durch prime_sieve_next oder is_prime32 erschlagen; und wie es aussieht, ist das Suchen nach nach wesentlich größeren Teilern als ein paar Millionen sogar kontraproduktiv (für die Geschwindigkeit).

Gruß Gammatester

Für diesen Beitrag haben gedankt: Mathematiker

Entwickler-Ecke.de rev.276b99aea638 based on phpBB
Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!

Impressum | Datenschutzerklärung | Kontakt zum Team