IhopeonlyReader hat folgendes geschrieben :

Mein Maximum liegt bei ca 12.884.901.890 Millarden.. somit kann ich maximal alle Primzahlen bis 12,8 Milliarden errechnen.. mit der Optimierung dass ich nur "ungerade" zahlen verwende (+1 wegn der 2) dann käm ich bis ca 25 Milliarden..

ohne Optimierung kann ich (wie vorrausgesagt) bis ca 12,5 Mrd. die Primzahlen berechnen !

Es gibt bis 12 Mrd 541.555.851 Primzahlen
kann das mal wer nachprüfen ob das stimmt?

Edit: die abgespeicherte Datei mit allen 541 Mio Primzahlen ist ca 6,08 GB groß.. OpenOffice, Word, Editor.. alle versagen kennt wer ein prog. das solch RIESEN Dateien "einigermaßen schnell" öffnen kann?

Hallo,

IhopeonlyReader hat folgendes geschrieben :

Es gibt bis 12 Mrd 541.555.851 Primzahlen kann das mal wer nachprüfen ob das stimmt?

Genau wird heute abend nicht mehr. Aber für den Integrallogarithmus ergibt sich
Li(12000000000) = 541562074
d.h. etwa der Wert. Mit der zuerwartenden Abweichung wird es also wohl stimmen.

Beste Grüße
Mathematiker

Nachtrag: Ich habe 541555852 beim exakten Sieben gezählt. Ist bei Dir die 2 dabei?

Hallo,

schade das Gammatester mit seinem Primepi32 nur bis Longint kommt.
www.entwickler-ecke....eration&start=20 und in seiner Multipräzisions-Arithmetik integriert.
Das müßte sich doch auf 64-Bit erweitern lassen.

Gruß Horst

Horst_H hat folgendes geschrieben :

Das müßte sich doch auf 64-Bit erweitern lassen.

Ja es läßt sich auf 64-Bit erweitern (die Hauptbremse wäre die Legendre-Funktion lsumphi), obwohl wahrscheinlich die Rechenzeit dramatisch ansteigen wird, 'execution time balloons to several hours near 1e15 or 1e16' wie Thomas R. Nicely für seinen C-Code schreibt.

In der Zwischenzeit (bis Horst_H das optimiert hat ), kann man statt Li(x) die Funktion RiemannR(x) aus meinen Speziellen-Funktionen benutzen, die etwas bessere Werte liefert, zB für x=12e9: Mathematiker-Sieb 541555852, RiemannR 541556725, Li 541562075.

Gruß Gammatester

Edit: Bevor die Beiträge eh zusammengefaß werden:

Mathematiker hat folgendes geschrieben :

Nachtrag: Ich habe 541555852 beim exakten Sieben gezählt. Ist bei Dir die 2 dabei?

Dann haben Du bzw. Dein Sieb sich wohl verzählt, denn www.primefan.ru/stuff/primes/10(07)11.txt und Wolfram Alpha sagen PrimePi(12E9) = 541555851

Mathematiker hat folgendes geschrieben:

Nachtrag: Ich habe 541555852 beim exakten Sieben gezählt. Ist bei Dir die 2 dabei?

ja ALLE Primzahlen bis 12 Milliarden...

danke für die Seiten Gammatester , ich rechne gerade Primzahlen bis 13,5 Milliarden aus, da die Grenze bei Delphi scheinbar zwischen 1,5 und 1,6 GB liegt... weiß der Geier warum ... kann mir bitte jemand mal die Antwort vom Geier nennen?

.. ich habe bei mir einen Fehler in der Berechnung bemerkt !

Als der Fehler (noch) drin war, habe ich folgende Ergebnisse gehabt:

Bis 12 Mrd gibt es 541.555.851 Primzahlen
Bis 13,5 Mrd gibt es 606.022.680 Primzahlen

nach den "Tabellen" sind diese Angaben richtig !

Ich werde das ganze nochmal "ohne" den Fehler berechnen und schauen ob ich Glück gehabt habe, das bei solch kleinen Zahlbereichen (bis 15 Mrd) der Fehler noch nicht in Kraft getreten ist, aber eigentlich müsste sich der Fehler ab ca 4Mrd +8 zeigen..

Hallo,

da wollte Gammatester mich wohl foppen
Ich habe mal seine Version etwas modifiziert, ohne das ganze "Gedöhns" seiner umfangreichen Ganzzahlarithmetik drumherum.Dadurch natürlich wesentlich langsamer, denn ich wollte diesen rückwärts Index nicht ala PrimIndex16(4)= 2.
Wollte ich das für die Primzahlen bis 1e9 machen, hätte ich keinen Speicher dafür.
Also schätze ich den Index ab Pi(x)= Index ~ sqrt(x)/(ln(sqrt(x))-1.08366) und suche dann in den Primzahlen, entsprechen rauf oder runter.
Als anderes wäre mir noch eingefallen, eine Tabelle für 65536 Zahlen ( X shr 16 ) mit dem Index ins Primzahlen Feld und dann linear mit (X MOD 65536) zu interpolieren und dann suchen. ( Tabelle[0]= 1,Tabelle[1] = 6542, )
Etwas lahm:

Natürlich hätte ich für kleine X Primes16Index behalten können, das wird am häufigsten gebraucht.

Gruß Horst
EDIT:
Neue Version das bringt doch einiges...


Ich habe vergessen zu sagen es Funktioniert nur bis 1e12, wie Primes1E6 vermuten lässt
Aaaaahhhhhh Edit3:
Zu wenig Int64 eingesetzt, denn bei mehr als 2x1e9 Primzahlen gab es wunderliche Ergebnisse.Deshalb jetzt ein Test bis 1e12:

Das passt.

Sehr cool

Horst_H hat folgendes geschrieben :

Ich habe vergessen zu sagen es Funktioniert nur bis 1e12, wie Primes1E6 vermuten lässt

Es funktioniert auch darüber hinaus, wenn man ein Anpassungen vornimmt (FPC und D9+, Source im Anhang) und ein wenig Zeit hat, hier für den 10fachen Wert = 120 Milliarden


Gruß Gammatester

Edit: Mist, zu spät.

so, für alle die einige Probleme mit deinem Projekt haben..

Hallo,

Uups, wieso muss man das ausdrücklich umwandeln? Bei Freepascal 2.6.2 nicht.
Ist ja zum Glück aber auch nur ein kleines Problem, das Gammatester in seiner Version richtig gemacht hat.

Gruß Horst
P.S.
Alles sehr Offtopic

Hallo Horst_H,
die Bestimmung der Primzahlanzahl ist superschnell. Starke Leistung! Genau das habe ich für int64 schon längere Zeit gesucht. Vielen Dank.

@IhopeonlyReader
Bei meinem Siebversuch bis 12 Milliarden habe ich wohl eine Primzahl "doppelt" gezählt. Entschuldigung.

Beste Grüße
Mathematiker

Mathematiker hat folgendes geschrieben :

@IhopeonlyReader Bei meinem Siebversuch bis 12 Milliarden habe ich wohl eine Primzahl "doppelt" gezählt. Entschuldigung.

Klar, kein Problem Und wie gesagt, ich habe in meinem Sieb ebenfalls ein Fehler drin^^, ich rechne gerade nochmal bis 13,5 Milliarden aus... (scheint aber so, als wenn der fehler sich automatisch ausgeglichen hätte (const+1 = const) <- war so^^.. dadurch hat sich der Fehler scheinbar selbst behoben^^.. aber ich rechne lieber nochmal ohne fehler

Nachtrag:

Horst_H hat folgendes geschrieben :

P.S. Alles sehr Offtopic

Ich glaube wir sollten mal einen Mod? bitten ob er ab Seite 2 (meiner Unit Veröffentlichung) das ganze mal trennt in ein neues Topic namens "allg. Primzahlenprobleme"

Nachtrag 2:

Mathematiker hat folgendes geschrieben :

Bei meinem Siebversuch bis 12 Milliarden

wie lange hat dein Rechner dafür gebraucht?

Achtung!
Beim Aufruf der von Gammatester angegebenen Seite
www.primefan.ru/stuff/primes/10(07)11.txt
meldet mein Virenscanner:
"Exploit:HTML/IframeRef.gen" Schwerwiegende Warnstufe!
Also entweder spinnt der Virenscanner oder irgendetwas läuft im Moment schief. Jahrelang gab's so etwas bei mir nicht und jetzt in wenigen Tagen das 2.Mal.

Sorry, war eine Fehlmeldung.

Beste Grüße
Mathematiker

Also, die Endung .ru ist in dem Link schon höchst verdächtig. Eine rumänische Seite!!! Na, wenn das man nicht wieder ein Trojaner-Ding ist.

Zum Thema "ich habe ein Fehler eingebaut"

Fehlerbehebung (automatisch):
Ich habe ein 2D Array angelegt, um den Index weiterhin "vernünftig" angeben zu können, somit unterteile ich bei meinem Sieb die zu berechnenden Zahlen in Vmrd -Teile (4 Milliardener Schritte) somit geht das 1 BitBoolean Array (mit dem Index 0) von der Zahl 0 bis hin zur Zahl 4Mrd-1
da ich die Bytes voll ausnutzen wollte unterteilte ich das Array nicht in 4Mrd-Schritte sondern in (4Mrd+7)er Schritte...
instinktiv (oder glück ) nutzte ich nun um herauszufinden in welchem "Teil" das BitBoolean liegt die Div variante mit VMrd+1 (also zB. 1Mrd div (VMrd+1) =0 also im Teil mit dem index 0)
Dies führt natürlich zu einem Fehler (theoretisch), da das 4 Mrd + 7 bit-boolean ja gar nicht im teil mit dem index 0 existiert, ABER ich habe ja zur Grundlage ein Byte und dieser besteht aus 8 Bits, da 4Mrd+7 nicht durch 8 Teilbar ist, bleibt 1 "ungenutztes" Bit.. dies wurde dadurch RICHTIG beschrieben und genutzt...

Wenn ich als Grundlage eine Zahl, die ein vielfaches von 8 ist, genommen hätte, hätte ich direkt eine exception erzeugt... So hatte ich glück.. ich habe nun alle (VMrd+1) durch ein VMrdD ersetzt (soll soviel heißen wie VMrd Divisor) dieser setzt sich nun folgender Maßen zusammen: VMrdD = VMrd + (VMrd mod 2);

Falls ihr euch fragt "nur weil man ungeschriebene bits nicht genutzt hat, soll dein Ergebnis falsch sein?"
so hier die Antwort: Nein, nicht direkt weil man ungeschriebene bits nicht nutzt, sondern weil die zahl VMdr ungerade ist!, denn ich setzte die Bytes auf 170 also 10101010 (gerade zahlen auf false, ungerade auf true) ist nun aber der Teil ungerade, so wird in jedem Teil, deren Index ungerade ist (1,3 ...) jede gerade zahl auf true und jede ungerade zahl auf False gesetzt..

Behebung: ich könnte jetzt natürlich VMdrD = VMdr + (VMdr mod 8 ) schreiben, um wirklich ALLE "erstellen" bits zu nutzen, da ich ich aber erstmal nur FEHLER vermeiden will, bringe ich es auf eine "gerade" zahl also mod 2 !

Mathematiker hat folgendes geschrieben :

meldet mein Virenscanner: "Exploit:HTML/IframeRef.gen" Schwerwiegende Warnstufe!

Also die URL zeigt bei mir auf eine stinknormele Textdatei. Da ist kein bisschen html Code. Ich würde daher (falls der Fehler immer noch besteht) mal auf deinen PC tippen.

Tranx hat folgendes geschrieben :

Also, die Endung .ru ist in dem Link schon höchst verdächtig. Eine rumänische Seite!!! Na, wenn das man nicht wieder ein Trojaner-Ding ist.

Und .ru ist natürlich Russland

Hallo,

jfheins hat folgendes geschrieben :

Mathematiker hat folgendes geschrieben : meldet mein Virenscanner: "Exploit:HTML/IframeRef.gen" Schwerwiegende Warnstufe! Also die URL zeigt bei mir auf eine stinknormele Textdatei. Da ist kein bisschen html Code.

Nachdem ich per Hand alle(!) temporären Internetdateien gelöscht habe, gibt's bei mir auch keine Meldung mehr. Der Virenscanner hatte wohl doch nicht alles gelöscht.
Damit hat sich meine Warnung als Fehlmeldung erwiesen. Tut mir leid für die "Panikmache".

Beste Grüße
Mathematiker

So, ich habe mein Programm nun soweit PERFEKTIONIERT, dass es alle Primzahlen bis ((4 Mrd+^2) -1 ausrechnen kann.. bis auf eine kleiner Ausnahme^^ Delphi7 erzeugt *32 Anwendungen, diesen wird nun einmal nicht mehr als 2 GB zur Verfügung gestellt, und diese 2GB müssen sich auch noch ALLE Programm teilen...
deshalb habe ich mich mal versucht zu informieren: www.3dcenter.org/art...e-address-aware-flag
somit komme ich nun "nur" auf 1,6 GB nutztbaren Arbeitsspeicher (ram) also 1,6*1024^3 *8 Booleans und somit "Werte" also bis 13,7 Milliarden, da ist bei mir Schluss.. so ist selbst bei Vollausnutzung (2GB) der Maximalwert bei 17,18 Mrd erreicht... (abgesehen davon, dass solche abgespeicherten Primzahlen.txt s 10 GB groß wären) ist mir das zu wenig...

was ich tun werde:
Optimierung auf:
1. UngeradenArray+2 so steht dann das erste Bit für folgende zahlen
BitNr (0-7) Zahl (wert)
0................1
1................3
2................5
3................7
4................9
5................11
6................13
7................15

Um auszurechnen welche zahl das bit eigentlich wiedergibt würde ich dann (BitNr+1)*2-1 = (BitNr+0.5)* 2 oder 2*BitNr +1
Um auszurechnen in welchem Bit die Zahl steht ensprechend (Zahl-1) div 2 bzw. Zahl div 2 (da DIV ja immer abrundet)

Ersparnis: 50% (Primzahlen bis max. 35 Mrd möglich, unter "normalen" Auslastungen nur bis 27 Mrd)

2. Nach der Berechnung bis VMrd (ein Teil), so "kürze" ich diesen..

Beispiel: aus dem 10 BitBooleans enthaltenenden Array von 0 bis 9
ArrayIndex steht für Zahl Wert
0................1................False //eigentlich True, wird aber am anfang direkt auf false gesetzt, da es ja keine Primzahl ist
1................3................True
2................5................True
3................7................True
4................9................False
5................11................True
6................13................True
7................15................False
8................17................True
9................19................True

wird ein neues Array, allerdings nicht aus booleans sondern aus Int64 (hier würde Byte reichen, aber es geht ja bis 16x10^18 hoch) zahlen
ArrayIndex Inhalt
0................3
1................5
2................7
3................11
4................13
5................17
6................19

das wird weiter auf den Abstand zur vorherigen primzahl gekürzt, so wird aus einem Int64 Array ein Word Array (16 Bit sollten reichen, oder wird ein Abstand>65535 bei zahlen bis 16x10^18 erreicht?).. vor der 3 wird die "2" jetzt als 1 Primzahl vorrausgesetzt (diese wird nicht errechnet sondern als bekannt vorgegeben)
ArrayIndex Inhalt
0................1
1................2
2................2
3................4
4................2
5................4
6................2

Gesamte Ersparnis (an Ram) ist abhängig von der Höhe der Primzahlen! in kleineren Bereichen gibt es viele Primzahlen und somit ist die Ersparnis hier gering (sogar negativ), in höheren Bereichen (wie 1 Milliarde) ist nur noch durchschnittlich jede 20te zahl eine Primzahl, da allerdings aus 1 Bit (boolean) zu 16 bits (word) werden, ist auch hier die Ersparnis gering ca 20% des gesamten Arbeitsspeichers
(Berechnung bis ca 42 Mrd. maximal möglich! bei "normaler" Auslastung nur bis 33 Mrd)

Und durch die 1ste Optimierung fällt kaum Rechenzeit hinzu, hier hingegen eine Beträchtliche kürzungszeit.. deshalb ist es fraglich die 2te Optimierung überhaupt durchzuführen

IhopeonlyReader hat folgendes geschrieben :

also bis 13,7 Milliarden, da ist bei mir Schluss.. so ist selbst bei Vollausnutzung (2GB) der Maximalwert bei 17,18 Mrd erreicht... (abgesehen davon, dass solche abgespeicherten Primzahlen.txt s 10 B groß wären) ist mir das zu wenig...

Wenn der Speicher zum Sieben nicht reicht, kann man auch eine Datei auf der Festplatte dazu verwenden. Bei einer Größe von z. B. 250 GB kannst Du die Zahlen bis zu zwei Billionen untersuchen. Bei größeren Dateien entsprechend mehr. Um die Festplattenzugriffe etwas zu reduzieren, kann man die Datei mit vorgesiebten Werten initialisieren (Primzahlen 2, 3, 5, 7). Je mehr Primzahlen, desto weniger Festplattenzugriffe, desto schneller. Danach die Primzahldatei auswerten (Primzahlen als Klartext in eine Textdatei wegschreiben und die riesige Datei wieder löschen).

An Festplattenausweichung habe ich auch schon gedacht.. aber das würde das ganze natürlich nocheinmal EXTREM verlangsamen...
Aber eine Möglichkeit wäre es natürlich ... würdest du mir allerdings helfen, wie ich eine Datei auf die Festplatte auslagere?

Nachtrag:

Gerd Kayser hat folgendes geschrieben :

z. B. 250 GB kannst Du die Zahlen bis zu zwei Billionen untersuchen

sogar bis und 250(Festplatte)*2(weil ich nur ungerade zahlen verwenden werde)*1024^3(GB->B)*8(Bit pro Byte) = 250*2*1024^3 *8 = 2^32 *10^3 (ca 4Billionen)
da eine Festplatte (HDD) allerdings nur 1/1000 bit(oder Byte?!)/s liest, würde dies aber schon bis 1 Milliarde ca. 10Min dauern (antatt max. 1min)