Array-Index nur als Integer möglich?

[Jan A]

Hallo Java-Programmierer,

ich bin ein totaler Anfänger in Java und stehe jetzt vor einem Problem:
Ich habe ein Programm geschrieben, welches Primzahlen bis zur vorgegebenen Höhe mit
dem Sieb des Erathosthenes berechnet. Dabei wird mit einem eindimensionalen Array gearbeitet, in dem die Zahlen gestrichen werden. Wenn ich aber Primzahlen höher als 46348 ausrechnen möchte, kommt immer diese Fehlermeldung:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -2146737495

Unter 46347 funktioniert aber alles. Wer den Fehler selber sehen möchte, kann sich hier das JAR-
Archiv herunterladen: http://intech.in.funpic.de/java/primzahlen/primzahlen.zip
Parameter:





-w Primzahlen in Textdatei schreiben
-m Höchste Primzahl
-s Textdatei

-s Primzahlen anzeigen
-m Höchste Primzahl

-c Prüfen, ob Zahl Prim
-m Zu prüfende Zahl

Neben dem Java-Archiv ist der Quellcode mit im ZIP.
Ich dachte schon, dass die Integerbegrenzung mir in die Quere kommt, und habe versucht, einen long als Array-Index festzulegen. Da meckert dann aber der Compiler, int ist benötigt und long gefunden. Ich hoffe ihr könnt mir weiterhelfen,

MfG Jan

 

[Wildcard]

int geht deutlich höher als 46000. Wie dir die Fehlermeldung zu sagen versucht, übergibst du auch keine 46348, sondern -2146737495. Du wirst also irgendeinen seltsamen Fehler im Code haben. Nimmst du den Index vielleicht zum Quadrat?

 

[SlaterB]

genau, und 46348^2 ist höher als der maximale int-Wert,

der ist 2147483647, 2.1 Milliarden, das sollte genug sein für alle Arrays, die in der Länge mindestens 8 GB groß sind 😉

 

[Jan A]

Das ist richtig, die Integervariable mit der höchsten zu errechnenden Primzahl wird quadriert, da alle Vielfachen der aktuellen Zahl mit i*i beginnend als false im Array markiert werden. Also wird bei 46348^2 die Integergrenze überschritten. Könnte man Arrays mit einem Long definieren würde das erstmal nicht passieren, oder?
Trotzdem: Könnte man nicht ein 2D-Array erstellen mit zweimal 46347 und alles über 46347 im ersten werden dann zum zweiten umgeleitet?
Also so:

int[][] array= new int[5][5];


array[0][1]=1;
array[1][1]=2;
array[2][1]=3;
array[3][1]=4;
array[4][1]=5;

array[0][2]=6
array[1][2]=7;
array[2][2]=8;
array[3][2]=9;
array[4][2]=10;

array[0][3]=11;
array[1][3]=12;
array[2][3]=13;
array[3][3]=14;
array[4][3]=15;

Wenn die Zahlen dann jew. "umgeleitet" werden, kostet dass bestimmt extrem
viel Zeit oder?


Jan

 

[SlaterB]

was du willst ist immer noch unklar,
aber nur zur Wiederholung: ein Array der Länge 46348^2 belegt 8 GB Arbeitsspeicher (!),
das ist mehr als jedes Betriebssystem braucht und meisten PCs überhaupt haben

was um alles in der Welt kann dein kleines Programm damit nur machen?

 

[0x7F800000]

Da scheint jemand einen sehr fortgeschrittenen sieb des eratosthenes zu programmieren. Die neue version von Jan A ist nicht nur in der lage festzustellen, ob eine Zahl prim (=ja=1=true) oder nicht prim (=nein=0=false) ist, sondern auch noch 31 weitere wichtige eigenschaften der Zahl als nebenprodukt auszurechnen 😉 Daher braucht's entsprechend viel platz 😉

so, und wenn du mit der korrektur des ersten malheurs fertig bist, siehst du dir bei der Wikipedia diese zeile nochmal genauer an:

Sobald das Quadrat der Primzahl größer als die Schranke S ist, sind alle Primzahlen kleiner oder gleich S bestimmt

und den quadrat rechnest du bitte auch nicht zig tausend mal neu aus, okay? 😉

 

[Jan A]

Da scheint jemand einen sehr fortgeschrittenen sieb des eratosthenes zu programmieren. Die neue version von Jan A ist nicht nur in der lage festzustellen, ob eine Zahl prim (=ja=1=true) oder nicht prim (=nein=0=false) ist, sondern auch noch 31 weitere wichtige eigenschaften der Zahl als nebenprodukt auszurechnen 😉 Daher braucht's entsprechend viel platz 😉

Die Zahl 46347^2 tritt doch alleine deshalb schon auf, da der erste Schritt, wenn eine Zahl prim ist, das Quadrat derselben im Array als false=nicht prim zu setzen, ist.


Also um das mal klarzustelllen: Mit AutoIT ging das ohne Probleme! Und zwar mit 1GB Arbeitsspeicher und nach demselben Prinzip

Edit: Also nicht bis 46347^2, aber bis 1000000 bestimmt


Jan

 

[Jan A]

Scheiße wie peinlich - ich hab ja i=j*j und nicht i=j eingegeben
😳 😳 😳 😳 😳 😳 😳 😳 😳
Jan 😀 😀 😀

i ist prim, streiche seine Vielfache mit i*i beginnend

Das hat mich verwirrt!

 

[0x7F800000]

Da wir hier ja keinerlei code zu sehen bekamen, sagt uns das leider nicht viel 😉 Aber wenn's funktioniert: gut :toll:
was dauert's denn in etwa, bis du mit der methode die größtmögliche int-Primzahl ausgerechnet hast?

 

[Jan A]

Äähm=> kein Quelltext?
Schau mal auf meinen ersten Post (und vor allem die verlinkte Datei :wink: )

Neben dem Java-Archiv ist der Quellcode mit im ZIP.

Jan

 

[Jan A]

was dauert's denn in etwa, bis du mit der methode die größtmögliche int-Primzahl ausgerechnet hast?

Wenn ich die Primzahlen in eine Textdatei schreiben lasse, keine Sekunde (Zahlen bis 2500000). Ins DOS-Fenster ausgeben dauert ungefähr fünfzehnmal so lange.

Hier die ausführbare JAR: http://intech.in.funpic.de/java/primzahlen/prim.jar
Parameter stehen im ersten Post

Cheers,
Jan

 

[0x7F800000]

Bis 2.5 Millionen etwa in größenordnung einer sekunde? naja, Integer.MAX_VALUE ist irgendwas deutlich über 2 Milliarden, dann wird das doch bisschen dauern, da kann man schon eine runde Kaffee trinken gehen 😉

Das kann man womöglich auch irgendwie geschickt auf mehrere threads aufteilen, dass die sich nicht gegenseitig zerfleischen... mich würd mal brennend interessieren, ob das bei multicore prozessoren was bringt. ???:L
ich brobiere das mal aus, wenn ich nix besseres zu tun hab 😛

 

[Jan A]

Komisch, über 3 Millionen komm ich nicht drüber wech. :?
Fehler:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at primzahlenberechnung.Erathosthenes.showPrims(Erathosthenes.java:85)
at primzahlenberechnung.Main.main(Main.java:60)



Muss ma n bisschen googlen


Edit: Habs raus= Heap vergrößern!
Dann kriege ich 50 Millionen in zwei Sekunden.
Aber größer als 1GB krieg ich den Heap nicht. Man müsste mal das Programm so ändern,
dass es die Festplatte als "Arbeitsspeicher" nutzt. Wäre wahrscheinlich 20 mal langsamer,
aber man könnte ja fast unendlich lange rechnen.
Würde man zwei Wochen im Arbeitsspeicher lang durchrechnen, käme man bis 20 Billionen, und einer Speichernutzung von sage und schreibe 12 Terabyte.
Mit Festplatte käme man also bis 500 Milliarden, und einer Größe von 300 Gigabyte. Irgendwie kommt mir das sehr wenig vor
😀

Jan

 

[0x7F800000]

Da hilft der (anscheinend überall präsente :shock: ) Marco13 wieder mal:
http://www.spotlight-wissen.de/archiv/message/1468799.html
hast bestimmt dasselbe gefunden, solang wir dasselbe google benutzen^^ 😛

 

[Jan A]

Ne, den Thread fand ich überhaupt nicht hilfreich :wink:

Jetzt im ernst hab kein Bock mich da durch 5 Links zu quälen
Da sauge ich das lieber beim scrollen auf! 😀
Mir hat der geholfen: http://www.fachschaftsrat.info/allg...rogrammierung/4196-java-heap-space-vergr-ern/

 

[Jan A]

Das kann man womöglich auch irgendwie geschickt auf mehrere threads aufteilen, dass die sich nicht gegenseitig zerfleischen... mich würd mal brennend interessieren, ob das bei multicore prozessoren was bringt. ???:L
ich brobiere das mal aus, wenn ich nix besseres zu tun hab 😛

Ich glaube, mit dem Sieb des Erathosthenes geht das nicht., da man immer bei 2 anfängt, und letztendlich die Threads genau dasselbe tun. Man könnte das mal mit dem Sieb des Atkin versuchen, denn da kann man vorgeben, von welcher Zahl begonnen werden soll. Dann könntest du ja den einen Thread bis 1 Milliarde und den zweiten bis zu zwei Milliarden rechnen lassen.

Jan