Primitiver Lucas-Lehmer-Test hängt sich auf

Status
Nicht offen für weitere Antworten.

felixthepimp

Mitglied
Servus!

Ich hab mir ein paar Java-Kenntnisse angeeignet und mir den relativ simplen Lucas-Lehmer-Algorithmus zur Aufgabe gemacht, um Mersennsche Primzahlen zu erzeugen. Da man da mit dem Standard-Integer-Datentyp schnell an das 32bit-Limit stößt, hab ich ein wenig im Inet gestöbert und bin auf die BigInteger gestoßen, deren Anwendung eigentlich recht simpel ist. Das Programm soll im Wesentlichen eine gewisse Anzahl (vom Benutzer eingegeben) an großen Mersennsche Primzahlen erzeugen. Das klappt auch bestens bis zur Zahl 5 (=Anzahl), dann hängt sich die CMD auf. Ich poste ma den Code:
[Java]
/*
Ziel dieses Programms ist es, grosse Mersennsche Primzahlen zu generieren.
*/

import java.math.BigInteger;
import static jsTools.Input.*;
public class Primzahlerzeugung{

public static void main(String args []){
BigInteger nix=new BigInteger("0");
BigInteger eins=new BigInteger("1");
BigInteger zwei=new BigInteger("2");
BigInteger vier=new BigInteger("4");
BigInteger p1=new BigInteger("3");
BigInteger p2;
BigInteger s=new BigInteger("4");
BigInteger i;
BigInteger j;
String hilf=readString("Geben Sie an, wieviele Primzahlen Sie erzeugen wollen:\n");
BigInteger anzahl=new BigInteger(hilf);
System.out.println("\n");

for(j=eins;j.compareTo(anzahl)<=0;j=j.add(eins)){
s=vier;

//Primzahl p2 berechnen
p2=eins;
for(i=eins;i.compareTo(p1)<=0;i=i.add(eins)) p2=p2.multiply(zwei);
p2=p2.subtract(eins);

//Primzahl p2 pruefen
System.out.println("Es wird geprueft, ob\n2^"+p1+"-1="+p2+"\neine Primzahl ist:");
System.out.println("s(1)=4");
for(i=zwei;i.compareTo(p1)<0;i=i.add(eins)){
s=s.multiply(s);
s=s.subtract(zwei);
s=s.mod(p2);
System.out.print("s("+i+")=");
System.out.println(s);
}
System.out.print("Die Zahl "+p2+" ist ");
//Wenn p2 keine Primzahl ist, muss man eine Berechnung mehr ausfuehren und man muss p1 derart verändern, dass es eine Primzahl wird
if(s.compareTo(nix)!=0){
System.out.print("k");
//Primitiver Primzahltest
for(i=zwei;i.compareTo(p1)<0;i.add(eins))
if((p1.mod(i)).compareTo(nix)==0){
p1=p1.add(zwei);
i=zwei;
}
j=j.subtract(eins);

}
//Falls p2 eine Primzahl ist, muss man p1=p2 setzen
else p1=p2;


System.out.println("eine Primzahl.\n");

}
}
}
[/Java]

Ich muss zu meiner Entschuldigung sagen, dass die readString()-Funktion von wem anderen stammt. Die sollte aber nicht das Problem sein, die ist von meinem Prof, das sollte wohl passen (hoffe ich^^).
Ich schreibe den Code der Übung halber im Editor ohne Highlighter oder andere Hilfmittel, Compiler ist der javac. Es scheint nicht an der Syntax zu liegen, sonst würde der Compiler ja aussteigen, es liegt vermutlich an der Semantik, eventuell sogar nur an der Optimierung des Codes.
Ich würde gerne alle üblichen BigInteger-Funktionen, die Primzahlen betreffen, weglassen, es geht mir um den Übungseffekt. Mir ist durchaus bewusst, dass die java.math.BigInteger da Funktionen zuhauf bietet, ich habe bewusst darauf verzichtet, man will ja lernen ;-).
Also, wenn ich das Programm ausführe, läuft es wunderbar bis zu der vierten generierten Primzahl, dann hört er kommentarlos auf.
Ich freue mich auf eventuelle Lösungen oder Fehlerfunde oder andere Beitäge, die helfen das Problem zu verstehen (muss ja net gleich ne Lösung sein).

LG FelixthePimp

P.S: Ich weiß, der Code is sehr primitiv, aber es ging nur ums Ausprobieren. Besonders das mit den BigInteger-Variablen ist, äh, verbesserungswürdig.
 

Landei

Top Contributor
Soweit ich das überblicke, funktioniert dein Code. Aber wenn du als fünfte Zahl schon eine riiiiieeeesige Mersenne-Primzahl hast, und dann 2^RiiiiiiieeeesigeMersennePrimzahl-1 testen willst, braucht dein Programm schon einige Zeit (keine Ahnung von wieviel Gazillionen Jahren wir hier reden - vorausgesetzt der Speicher macht nicht schlapp). Schon eine Schleife über alle ints, die nicht von Compiler wegoptimiert werden kann, braucht eine Weile, und da reden wir gerade mal über 2^32 Zahlen.
 

felixthepimp

Mitglied
Das hab ich mir schon gedacht. Allerdings sollte er ja die S(i), also die Zwischenergebnisse ausgeben. Er macht aber nix. Es scheint also an der Berechnung von p2 zu liegen. Und die Errechnung von p2 ist ja nur ne (zugegebenermaßen recht fette) Potenzierung von 2. Und natürlich die gemeine Subtraktion^^. So stark kann er ja noch net gefordert sein, oder?
 

vinculum

Mitglied
Ich würde empfehlen einmal das Programm mit top unter Unix bzw. mit dem Taskmanager unter Windows zu analysieren. Dann kannst du rausbekommen, ob der Speicher überläuft oder der Prozess einfach nur lange dauert.
Wenn der Speicher volläuft kannst du mit -Xms1024m (-Xms(Megabyte)m) den anfänglich verfügbaren und mit -Xmx1024m (-Xmx(Megabyte)m) den maximal verfügbaren Speicher für das Programm erhöhen auch um mehr falls vorhanden, den limitiert die Java VM nämlich künstlich.
Damit könntest du die Grenze vielleicht etwas nach oben schrauben, ansonsten bleibt nur zu sagen, dass dein Algorithmus mehr exponentielle Laufzeit hat, x^n wobei x dann die Zeit für einen Durchlauf und n die Anzahl der Zahlen ist über die deine äußere Schleife läuft. Eine Zeitlimitierung erlegt die JVM ihren Prozessen aber nicht auf.
 

felixthepimp

Mitglied
Ok, die Taskmanageranalyse ergab, dass es am Ram nicht zu liegen scheint, java.exe gönnt sich lediglich ca 10mb. Die Auslastung liegt bei ca 50% +/-5% und das auf beiden Kernen.
Ich hab dennoch "java Primzahlerzeugung -Xmx2048m" in die CMD eingegeben, brachte aber das selbe Ergebnis. Sieht also so aus, als ob ich das Potenzieren etwas optimieren sollte. Ich hab da so ne Idee, die Potenzierung nur durch Addition und Schleife auszudrücken, ich schau mal, ob ich das hinbekomme.
 

Landei

Top Contributor
Gib es auf. Um mal deutlich zu machen, wie weit du von der Realität entfernt bist: Der Mersenne-Primzahl-Rekord liegt zur Zeit bei 2^43112609-1 ( Mersenne Prime Search - German Mirror ), und die Leute dort suchen schon jahrelang und portionsweise verteilt mit hochoptimiertem Code (bestimmt nicht mit Java und ganz bestimmt nicht mit BigInteger).
 
Zuletzt bearbeitet:

felixthepimp

Mitglied
Das hab ich mir schon gedacht. War mehr so just for fun, das Ganze. Ich hab meine Facharbeit fürs Abitur (a bayrisches, kniet nieder^^) über die Primzahlen geschrieben, wollt mal sehn, wie weit mein Rechner kommt. Er hat also bei:
2^(170141183460469231731687303715884105727) -1
die Grätsche gemacht, gekommen ist er also bis:
170141183460469231731687303715884105727=2^127 -1
Schad eigentlich. Aber ma sehn, ich studier Informatik im ersten Semester, vielleicht geht da noch was^^.
EDIT: Kann geschlossen werden.

EDIT2: Hier noch die Ausgabe, wen es interessiert:
Code:
Geben Sie an, wieviele Primzahlen Sie erzeugen wollen:
4


Es wird geprueft, ob
2^3-1=7
eine Primzahl ist:
s(1)=4
s(2)=0
Die Zahl 7 ist eine Primzahl.

Es wird geprueft, ob
2^7-1=127
eine Primzahl ist:
s(1)=4
s(2)=14
s(3)=67
s(4)=42
s(5)=111
s(6)=0
Die Zahl 127 ist eine Primzahl.

Es wird geprueft, ob
2^127-1=170141183460469231731687303715884105727
eine Primzahl ist:
s(1)=4
s(2)=14
s(3)=194
s(4)=37634
s(5)=1416317954
s(6)=2005956546822746114
s(7)=4023861667741036022825635656102100994
s(8)=148295852275705128589952510455019292911
s(9)=17934813421766634732012365957609373869
s(10)=85902463759488963702490017444612081724
s(11)=116475895319100247619106962527555061737
s(12)=49976279066382381059963127566460774395
s(13)=160668395611328156886231636609761589125
s(14)=94281146402315220816856494248417316624
s(15)=108007687823445325965842618064742685120
s(16)=31734492925565095550179541226941707640
s(17)=40502963312906587195023713454534295598
s(18)=94088105965254764875368473681747882892
s(19)=144493995864766378690749087262700586682
s(20)=20955297820352149233036565636331346012
s(21)=158915090152235934934479130912004389942
s(22)=52870398708381174466959392316679307296
s(23)=151490860312186869918440828859019512842
s(24)=95080894369933623491452109744508211636
s(25)=16832551656452962969322409924830603304
s(26)=50174049518004850581182191673210576861
s(27)=144336566379264365321651202616996055222
s(28)=130822199398052164937252409514558681721
s(29)=102532921936216636347982935976260898227
s(30)=113510945853789792879800143796642024867
s(31)=818764630715300415439121721750598757
s(32)=98873676748258741042292766411306359072
s(33)=115157140590183601330851495358050270577
s(34)=61932212331753972177049746744878494891
s(35)=162235341974786734396644569954762754962
s(36)=138222088850540840559618349986527965434
s(37)=12643335933642280592896036123803678462
s(38)=107874906898446614736459591766452551411
s(39)=105127310369349743611680099371735190865
s(40)=9288955258648756974993511313169148987
s(41)=22544078789156567134084495007232388871
s(42)=145330281715042877722945273276030728719
s(43)=2984059486841025471869552930115409684
s(44)=37572228739714097091268646718694828173
s(45)=137863838131209681188612129313912947511
s(46)=56951438527019760670940985275669549587
s(47)=33425539749822146052823924594117170181
s(48)=107032723030256277290622289200228566672
s(49)=53753380576481396758706859471945799623
s(50)=47099113889942965118806100149717565037
s(51)=99592518053374632198667753856515678006
s(52)=71264320053401377760498554706288870501
s(53)=93303582026251481068288102203876023525
s(54)=120228733067825856598036469060895809969
s(55)=118032048866201789290845587608054171643
s(56)=2650987091797688081935257855065994022
s(57)=145145919991993592884437642677980118562
s(58)=62997327855360484015702535758367792966
s(59)=83098680626625704955924126176100860767
s(60)=47102745120534589629594563604260423772
s(61)=23086037567407917159207583474834256176
s(62)=1648903944353085502350569803700249218
s(63)=146001941445125883362200107861188525242
s(64)=58072554876864005167998859270477790277
s(65)=85183974222777764635811000451869083253
s(66)=2178744815368192602929511049691246435
s(67)=142650016674409483015140356448611524239
s(68)=131180293024080215139431333296642157751
s(69)=23796400979692190167798559040061980681
s(70)=94691321662907057932605046718559371950
s(71)=28963125299159837855551115831455735161
s(72)=151145149675516943070949943379933758640
s(73)=76394190749566845285279900410093015143
s(74)=47725036928709433877841763022477907753
s(75)=104312534247659063865391654129512337576
s(76)=18945859719359721770108285233329380324
s(77)=164494116784207012462580689820261092953
s(78)=19312431404447051481513679243141178566
s(79)=27736528190775597167138586218006816402
s(80)=2300146040010405501321960790364494805
s(81)=148671707681260870148526487891403027688
s(82)=44689644596926350087083033086752357927
s(83)=114252518218238942159527597790043383515
s(84)=132347767817386283653136701980558442215
s(85)=82898165451862550147177322318323559762
s(86)=82550532064404830850169960592302750413
s(87)=75643059898515530266520341907002980339
s(88)=123982986142288470036528246058979625829
s(89)=82251894353697560270857485942566454845
s(90)=138612996512155828504361896311563427332
s(91)=38110442230077683457296715174480894554
s(92)=139824088758964839080901930176959179789
s(93)=91384193027872879688983922241190087851
s(94)=169520666637091361903503058366366526051
s(95)=169025277276139840475937137620617270244
s(96)=75767585679605360512739263520802144959
s(97)=49956247714329574425552443869563509087
s(98)=183690004880779837464570338561315540
s(99)=163703822629639553167738612906045835358
s(100)=169082445910970886147479859194469813067
s(101)=4415171566587865141382642765195174023
s(102)=110059221777184243569539344972552339165
s(103)=5064148876153793895511724877772701976
s(104)=26339871245616999480560619437480231895
s(105)=92058826383142394228174232088236221101
s(106)=25358529928264030171413979572591657174
s(107)=57391611503696291044494362875786761933
s(108)=4628408976566823773472049228202071599
s(109)=62888400681175191832847866264356373833
s(110)=83454791660308671184475704797189993564
s(111)=134424104788780027271116197574228580517
s(112)=15898780365670245164798848628558077094
s(113)=158133952358979283618604204477670831346
s(114)=6721506539191163416499937441762326133
s(115)=882594379818242655466533853441665046
s(116)=161925513938892243375929285060210027401
s(117)=80309984059206838477625980764275616860
s(118)=111061271103311825402106204765050643448
s(119)=8300180540889597001844078179358966103
s(120)=132515367850942399280896079195237732275
s(121)=46864209815407210576219476880150425377
s(122)=51366641762479717422620116634081008320
s(123)=142797848550190257259709111711506044974
s(124)=87676307088191859152273331489412200665
s(125)=18446744073709551616
s(126)=0
Die Zahl 170141183460469231731687303715884105727 ist eine Primzahl.
 
Zuletzt bearbeitet:
Status
Nicht offen für weitere Antworten.

Ähnliche Java Themen

Neue Themen


Oben