[java] Mersenne priem getallen

[Sv3n]

Ben bezig met een programma dat mersenne priem getallen berekend, nou werkt dit op zich al best goed, de eerste 9 lukken (na even rekenen )

een mersenne priemgetal, is een priemgetal dat voldoet aan de volgende regel:
2^<<priemgetal>>-1 = <<een willekeurige ander priemgetal>>

Maar nou zit ik met een probleem, zoals ik al zei tot 9 werkt het prima, in de parameter van de functie geef ik het aantal mee dat ie moet gaan berekenen, bij bijv. 5 gaat dit prima, echter geef ik 10 mee dan klapt ie er na de 9 uit
Heb al lopen debuggen, maar kan niet vinden waar de fout nou zit

code:

    public Set mersennePriemGetallen(int aantal){
        Set priemGetallen = new HashSet();
        Set mersenne = new HashSet();
        priemGetallen = berekenPriem(aantal*20);
        Iterator i = priemGetallen.iterator();
        int aantalGevonden = 0;
        long uitkomst = 0;
    
        
        while (i.hasNext() && aantalGevonden < aantal){
                int priem = ((Integer)i.next()).intValue(); //haal volgende uit set
                uitkomst = (long)(Math.pow(2, priem) - 1); //bereken 2^n-1
                Integer integer = new Integer(priem); //maak een integer
                if (isPriem(uitkomst)){ //kijk of uitkomst een priemgetal is
                    System.out.println(priem); //om te testen
                    mersenne.add(integer); //voeg toe aan nieuwe set
                    aantalGevonden++; //hoog gevonden aantal op
            
                }   
        }
        

        return mersenne;
    }

Dit is de functie die dus een set met mersenne priemgetallen terug moet gaan geven, de set priemgetallen word goed aangeleverd. Alles lijkt ook goed te gaan tot die 10e dus, dan stopt het programma er direct mee, ik weet even niet waar ik het nog moet zoeken, iemand

[FendtVario]

geeft i.hasNext() niet toevallig false terug als je de negende hebt gehad?

[Sv3n]

FendtVario schreef op woensdag 09 maart 2005 @ 17:44:
geeft i.hasNext() niet toevallig false terug als je de negende hebt gehad?

nee want het 10e getal is 61 en die zit wel bij de eerste 200 priem getallen

[bigbeng]

Geef anders de Exception en de stacktrace van wanneer het fout gaat. Dat debugt iets makkelijker.

[Nick_S]

Als hij er uit klapt, dus zonder error neem ik aan, dan is of i.hasNext() gelijk aan false of aantalGevonden < aantal gelijk aan false.

Ik zou dus aan het eind (maar er dus wel binnen) van je while loop even een paar debug messages plaatsen om te kijken, waarom hij er uit klapt.

[bigbeng]

Ik vermoed overigens dat het iets te maken heeft met het feit dat een double (waarmee Math.pow rekent) want die heeft maximaal 8bytes. Volgens mij wordt een deel van die 8 bytes gebruikt voor de mantisse en pos/neg representatie, dus de kans dat 2^61 te groot is voor Math.pow is zeer wel aanwezig.

[Verwijderd]

Di's een standaard gevalletje debuggen, en ik weet niet of het nou zo zinvol is om uit te besteden aan mensen hier. We kunnen wel tips geven hoe dit te debuggen. Je hebt overigens ook niet gezegd wat de waarde van aantal is, en niet de code van isPriem en berekenPriem megegeven, waardoor het een beetje raden is waar het fout gaat.

[bigbeng]

Ander puntje, je kunt regel 2 net zo goed vervangen door

code:

Set priemGetallen;

want je laat daarna in regel 4 de functie berekenPriem een nieuwe HashSet maken.
/mierenneukmodus

[Sv3n]

raar probleem, tot 31 is ie heel hard aan het rekenen, daarna gaat het heel snel en knalt ie eruit omdat ie door z'n set met priem getallen heen is, maar dan issie in de 3500(priem variable), hetlijkt wel of ie stopt met rekenen na de 31

//edit
bij 2^61-1 geeft isPriem false terug omdat het 2305843009213693951 is maar er word afgerond naar 2.305843009213694E18 Het laatste nummer is een even getal en dus vind mijn code dat het geen priem getal is.

wat nu, met bigints gaan werken ofzo

[ Voor 120% gewijzigd door Sv3n op 09-03-2005 18:54 ]

[bigbeng]

Ik vrees dat je daar niet aan ontkomt, want zelfs een long is maar 8 bytes en dat is dus maar net genoeg om 2^61 te bevatten.
Je kunt trouwens wel een eigen machtsverhef functie schrijven die echt met longs werkt en niet met doubles, maar als je nog hoger wil doorrekenen, dan is bigints the way to go. Gewoon effe googlen, je kunt waarschijnlijk zo een aantal classes downloaden.

[Robtimus]

bigbeng schreef op woensdag 09 maart 2005 @ 20:54:
Ik vrees dat je daar niet aan ontkomt, want zelfs een long is maar 8 bytes en dat is dus maar net genoeg om 2^61 te bevatten.

Uit de Java API voor java.long.Long#MAX_VALUE:

A constant holding the maximum value a long can have, 2⁶³-1.

Dis die 2⁶¹ haal je nog net wel, maar veel verder niet.

[Verwijderd]

Laat maar

[ Voor 97% gewijzigd door Verwijderd op 10-03-2005 14:21 ]