[Java] Euler project 'probleem 3' met zeef (spoiler inside)

[BikkelZ]

Ik heb het probleem gekraakt met de volgende methode:

Java:

import java.util.*;
import java.math.*;

public class PrimeCalculator {

    /**
     * @param args
     */ 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        //PrimeCalculator prCalc = new PrimeCalculator(13195);
        String max = "317584931803";
        // ik zeg dat ieder priemgetal gevonden kan worden in de reeks onder de wortel van het hoofdgetal
        // daar heb ik geen bewijs voor
        long maxi = Long.parseLong(max);
        PrimeCalculator prCalc = new PrimeCalculator(maxi);
        System.out.println(prCalc.toString());
    }
    
    private int maxPrime = 1;
    
    PrimeCalculator() {
    }
    
    PrimeCalculator(long maxi) {
        for (int i=3; i < Math.sqrt(maxi); i+=2) {
            // als het getal het getal kan delen
            if (maxi % i == 0) {
                if (checkPrime(i)) maxPrime = i;
            }
        }
    }
    
    public static boolean checkPrime(long n) {
        boolean prime = true;
        for (long i = 3; i <= Math.sqrt(n); i += 2)
            if (n % i == 0) {
                prime = false;
                break;
            }
        if (( n%2 !=0 && prime && n > 2) || n == 2) {
            return true;
        } else {
            return false;
        }
    }
    
    public String toString() {
        return "" + maxPrime;
    }
}

Toch heb ik het gevoel dat dit suboptimaal is. Ik heb geprobeerd het via de zeef-methode te doen, die leek me sneller, maar ik krijg het niet helemaal voor elkaar met de maximale grootte van array/ArrayList/Vector, veel gedoe met out of bounds.

http://nl.wikipedia.org/wiki/Zeef_van_Eratosthenes

Aangezien het probleem eigenlijk al opgelost is, kan iemand me uitleggen of de zeef methode te doen is qua geheugen, en zo ja hoe?

[Verwijderd]

dit

Java:

public static boolean checkPrime(long n) { 
        boolean prime = true; 
        for (long i = 3; i <= Math.sqrt(n); i += 2) 
            if (n % i == 0) { 
                prime = false; 
                break; 
            } 
        if (( n%2 !=0 && prime && n > 2) || n == 2) { 
            return true; 
        } else { 
            return false; 
        } 
    } 

kan volgens mij al herschreven worden naar:

Java:

public static boolean checkPrime(long n) { 
        //misschien nog wat checks op getallen < 3
        long sqrt = Math.sqrt(n); 
        for (long i = 3; i < sqrt; i += 2) { 
            if (n % i == 0) { 
                return false; 
            } 
        }
        return true; 
    } 

Een relatief eenvoudig winstje valt nog te behalen door enkel te delen door voorgaande(/reeds gevonden) priemgetallen.

[ Voor 7% gewijzigd door Verwijderd op 20-09-2007 15:01 ]

[Marcj]

Als je standaard begint met een zeef die een array is van 317584931803 lang, nee dan gaat het niet in het geheugen passen. Maar je kunt natuurlijk wel eerst alle priemgetallen tot sqrt(317584931803) = 563547 berekenen. Deze passen natuurlijk wel in het geheugen en hiermee kun je wel berekenen of dat getal een priemgetal is.

Of deze zeef-methode wel de snelste is weet ik niet, zeker niet qua geheugen

ps. In java kun je wel direct een long neerzetten door

Java:

long max = 317584931803l;

[BikkelZ]

Ja je hebt gelijk, maar in dit geval zie je dat het geen even getal is. En als ik de uitkomst niet kreeg < 1 min door deze methode te gebruiken, zou ik inderdaad intern een lijstje met priemgetallen aanhouden. Maar volgens mij is de zeef-methode theoretisch het efficientst, omdat hij met een simpele bit check (boolean) al weet of het volgende getal een priem is of niet.

[Verwijderd]

Marcj schreef op donderdag 20 september 2007 @ 15:04:

Java:

long max = 317584931803l;

En daarbij dan de tip om dit altijd met een hoofdletter te doen zodat het niet op een 1 lijkt.

Java:

long max = 317584931803L;

[BikkelZ]

Marcj schreef op donderdag 20 september 2007 @ 15:04:
Als je standaard begint met een zeef die een array is van 317584931803 lang, nee dan gaat het niet in het geheugen passen. Maar je kunt natuurlijk wel eerst alle priemgetallen tot sqrt(317584931803) = 563547 berekenen. Deze passen natuurlijk wel in het geheugen en hiermee kun je wel berekenen of dat getal een priemgetal is.

Ah ja, natuurlijk.

Marcj schreef op donderdag 20 september 2007 @ 15:04:Of deze zeef-methode wel de snelste is weet ik niet, zeker niet qua geheugen

68MB, mits hij alle booleans direct achter elkaar zet. Als hij een byte pakt om een bit te beschrijven kun je het vergeten

Marcj schreef op donderdag 20 september 2007 @ 15:04:ps. In java kun je wel direct een long neerzetten door

Java:

long max = 317584931803l;

Ja dat leek mij nou ook al, maar Eclipse begon er over te mauwen.

OK I see ik moet er een L achter poten om het te laten werken.

[ Voor 24% gewijzigd door BikkelZ op 20-09-2007 15:17 ]

[Marcj]

Nu je het zegt, in dit lettertype lijken ze hetzelfde, maar in Eclipse kan ik ze makkelijk uit elkaar halen

[BikkelZ]

Ik denk dat zodra die 68MB ingeladen is in het geheugen dat het bloedsnel is. Ik zal het nog eens gaan testen. Hoe bereken ik hoe lang een bepaald stuk van mijn code er gemiddeld over doet om uitgevoerd te worden?

[Marcj]

Met System.currentTimeMillis() of System.nanoTime() kun je de huidige tijd opvragen. Als je dit aan het begin en einde doet kun je het verschil berekenen Trouwens, boolean worden in java helaas wel als bytes opgeslagen en dat is dus niet de meest efficiente manier. Misschien is het verstandiger om een array met integers te vullen met getallen die priemgetallen zijn?

[KabouterSuper]

Het is trouwens niet zo moeilijk te bewijzen dat je alleen factoren hoeft te zoeken die kleiner zijn dan of gelijk zijn aan de wortel van je getal:
Als a=b*c, dan geldt dat ofwel b=c ofwel min(b,c)<sqrt(a). Ergo: min(b,c) is een factor van a die kleiner is dan of gelijk is aan sqrt(a).

Edit: check even de gelijkheid...in jouw code is 9 nu een priemgetal.

[ Voor 14% gewijzigd door KabouterSuper op 20-09-2007 15:26 ]

[PiepPiep]

Als je alleen wilt weten of een getal priem is of niet kan je ook de Fermat primality test doen, deze is zeker sneller dan de zeef en een van de makkelijkste om te programmeren.
http://en.wikipedia.org/wiki/Fermat_primality_test

[BikkelZ]

PiepPiep schreef op donderdag 20 september 2007 @ 19:09:
Als je alleen wilt weten of een getal priem is of niet kan je ook de Fermat primality test doen, deze is zeker sneller dan de zeef en een van de makkelijkste om te programmeren.
http://en.wikipedia.org/wiki/Fermat_primality_test

Dat is iets te incrowd wiskundig voor mij. Is dit ook ergens te vinden wat wel voor mij te behappen is?

[Marcj]

Je kunt proberen om dit zelf te implementeren, maar je kunt ook gewoon kijken naar de BigInteger. Deze heeft namelijk een functie isProbablePrime(int), welke twee verschillende tests (Miller-Rabin en Lucas Lehmer) doet om er redelijk zeker van te zijn dat dat getal een priemgetal is. Echter kan deze nooit garanderen dat het een priemgetal is.

[BikkelZ]

OK, dus het meest efficiente zou zijn een hardcoded lijst met Carmichael nummers en die functie van BigInteger gebruiken? Volgens mij is het dan waterdicht.

Ik ben in ieder geval weer een stukje wijzer geworden, bedankt

[Marcj]

Cormichael nummers zitten uitrekenen is helemaal niet nodig, want dit is een probleem van de Fermat methode, niet van die andere twee. Plus dat de methode van BigInteger met een parameter van 150 de kans op een false positive nog maar richting de 10⁴⁵ is. Deze methode wordt ook zo direct gebruikt wordt voor encryptie, waar meestal priemgetallen van 1024 bits of nog groter hiermee gegenereerd worden Ik weet niet waar jij het voor wilt gebruiken?

[BikkelZ]

Nou, bijvoorbeeld:

http://projecteuler.net/index.php?section=problems&id=7

Lijkt mij dat een false positive ergens in de reeks een foute uitkomst oplevert (al kan ik niet inschatten of die afwijking daadwerkelijk gaat optreden, zo wiskundig onderlegd ben ik niet).

Maar niks zeggen tot ik hem eerst zelf opgelost heb

[de wandelaar]

BikkelZ schreef op donderdag 20 september 2007 @ 14:45:

Toch heb ik het gevoel dat dit suboptimaal is. Ik heb geprobeerd het via de zeef-methode te doen, die leek me sneller, maar ik krijg het niet helemaal voor elkaar met de maximale grootte van array/ArrayList/Vector, veel gedoe met out of bounds.

Hieronder een uitwerking van de Zeef. Ik gebruik een BitSet die per priemgetal een bit reserveert.

Op mijn pc (P4, 3,2Ghz) duurt het ongeveer 3 minuten om alle priemgetallen onder maxint uit te rekenen. Afdrukken op stdout duurt behoorlijk langer.

Out of bounds ontstaan als je over max int heen gaat, ik heb een i>0 toegvoegd om dan af te kappen.
[code=java]
import java.util.BitSet;

public class Zeef {

public static void main(String[] args) {

int MAX = Integer.MAX_VALUE; //Alle priems in int bereik
int SQRT_MAX = (int)Math.sqrt(MAX); //Genereer x-vouden tot de wortel
long t = System.currentTimeMillis();

// init: stel alle oneven getalllen zijn priem en 2 is ook priem
BitSet bs = new BitSet(MAX);
for (int i = 1; i< MAX; i+=2)
{
bs.set(i, true);
}
bs.set(2, true);

// loop over de zeef, 1,2 zijn priem. start met 3-vouden, 4-vouden
for (int xvoud = 3; xvoud <= SQRT_MAX; xvoud++)
{
// als priem, verwijder alle meervouden van priem
if (bs.get(xvoud))
{
for (int i = xvoud*xvoud; i <= MAX && i>0; i+=xvoud)
{
bs.set(i, false);
}
}
}
System.out.println("Time to caclulate(ms) all primes under: "+ MAX
+ " is: "+ (System.currentTimeMillis()-t));
}
[/code=java]

afdrukken kan op deze manier, maar voor grote resultaten zou ik ik een StringBuffer toevoegen.
[code=java]
// BitSet.toString() heeft bugje bij max value int, gaat waarschijnlijk over max int heen
// Drukt nl. {} af terwijl juiste antwoorden wel in BitSet zitten.
static void printResult(BitSet bs)
{
for (int i = bs.nextSetBit(0); i>0; i=bs.nextSetBit(i+1))
{
System.out.print(i+", ");
}
}
[/code=java]

[BikkelZ]

de wandelaar schreef op vrijdag 21 september 2007 @ 10:29:
[...]Op mijn pc (P4, 3,2Ghz) duurt het ongeveer 3 minuten om alle priemgetallen onder maxint uit te rekenen. Afdrukken op stdout duurt behoorlijk langer.

Aangezien maxint lager ligt dan het getal wat berekend moet worden mag ik zeer veilig aannemen dat het een stuk langzamer is dan brute force, laat staan via de wat geavanceerdere ingebakken functie van BigInteger?

Ik denk dat de zeef methode dus alleen zoden aan de dijk zet op het moment dat de getallen al in het geheugen staan.

Wel netjes gebouwd in ieder geval, en jammer dat het dus niet met een getal groter dan maxint gaat.

[Marcj]

Je hoeft de zeef maar natuurlijk uit te rekenen tot de wortel van dat getal. Daarna heb je alle priemgetallen die je moet controleren. En de wortel van 317584931803 is 'maar' 563547. Dit is prima binnen een seconde uit te rekenen (heb ik hier net ff gedaan )