[Haskell] Slim priemfactoren bepalen

[Boudewijn]

Hoihoi

Ik doe voor de fun wat dingen met haskell voor projecteuler.net (wat basis wiskunde dingen uitrekenen) en zit nu de priemfactoren van een vrij groot getal te berekenen.
Hiervoor heb ik dit stukje software geschreven:

code:

module Main where


main::IO()
main = do
        --even als testje
        putStrLn "The prime factors of 13195 should be:  5, 7, 13 and 29."
        print (filter isPrime (determineFactors 13195))
        putStrLn "Max primefactor of 600851475143  : "
        print (maximum(filter isPrime (determineFactors 600851475143)))





determineFactors :: Int -> [Int]
determineFactors n =
                filter (/=1) (map ( (\x y -> if (x `mod` y) == 0 then y else 1 ) n) [1..(ceiling(fromIntegral((n)`div` 2)))] )


isPrime :: Int -> Bool
isPrime n = if ((even n) || not( null(determineFactors n )))  then False else True

Hoe kan ik dit nou netter doen?

Ik dacht eerst dat de :

code:

 not( null(determineFactors n )))

De zaak traag maakt ,maar ik neem aan dat de null lazy evaluated wordt... dus dat kan het niet zien.

Waar zit dan het probleem?

Aan de andere aknt, ik begin bij het factor-ontbinden bij 1 en ga naar getal/2 .
Dit moet omgedraaid als je de grootste het eerst wil vinden .


edit:

code:

determinePrimeFactors :: Int -> [Int]
determinePrimeFactors n = filter (isPrime)  (map ( (\x y -> if (x `mod` y) == 0 then y else 1 ) n) (reverse([1..(ceiling(fromIntegral((n)`div` 2)))])) )

Zou beter moeten werken, maar doet het ook niet echt.

[ Voor 9% gewijzigd door Boudewijn op 19-06-2008 16:53 ]

[RayNbow]

Het ligt aan je algoritme. Eerst bepaal je alle delers en daarna bepaal je alle delers van de gevonden delers om uit te vogelen of je een priemfactor hebt of niet. Dit is enorm veel werk.

Een sneller algoritme maakt gebruik van het feit dat een getal als volgt op te schrijven is:

p₁ * p₂ * p₃ * ... * p_n = m

[ Voor 8% gewijzigd door RayNbow op 19-06-2008 16:58 ]

[Boudewijn]

Ja ik weet dat het aan mijn algoritme ligt, en zie ook dat het veel werk is.

Alleen vraag ik me af hoe ik jouw algoritme in het geval van een priemgetal in mijn programmatje kan implementeren.

[RayNbow]

Stel dat m deelbaar is door p₁ = 2. Dan weet je in ieder geval dat 2 een priemfactor is. Probeer dan nu de grootste priemfactor te vinden in p₂ * p₃ * ... * p_n = m / p₁.

Maar als het getal niet door 2 te delen was, dan probeer je of p₁ = 3. Als dat niet werkt, dan probeer je p₁ = 4, etc. (Het getal 4 hoef je eig. niet te controleren, maar maakt het algoritme wel simpeler)

[Zoijar]

Dat lijkt me ook het simpelste. Je kan het beste blijven delen, totdat het niet meer lukt, en dan pas je getal verhogen. Op die manier krijg je niet ineens 4 als factor van 8 bv. (als een getal niet deelbaar is door p, dan ook nooit door p^n) (plus dat je maar tot sqrt(n) hoeft te zoeken, als je dan geen factor hebt is het restant priem)

[ Voor 31% gewijzigd door Zoijar op 19-06-2008 17:28 ]

[Verwijderd]

http://www.cacr.math.uwaterloo.ca/hac/, hoofdstuk drie, factoring probleem.

Noot:"Slim" kan niet echt --> dan heeft RSA niet veel zin.

Het algo doet ongeveer wat hierboven al gezegt word:

Voor een set kleine priemgetallen --> haal die uit het getal.
Voor priems groter dan die set --> doe ingewikkeldere algorithmen die simpel zij.
Voor priems die ook daar te groot voor zijn --> 'bruteforcen'

[ Voor 49% gewijzigd door Verwijderd op 19-06-2008 18:16 ]

[Boudewijn]

Het is voor http://projecteuler.net/index.php?section=problems&id=3

Ze zeggen dat je alle puzzeltjes binnen 1 minuut moet kunnen laten lopen, dus het is te doen met een niet-super-slim algoritmetje.

Ik ga zo eens wat beters schrijven .

[RayNbow]

Boudewijn schreef op donderdag 19 juni 2008 @ 18:19:
Ze zeggen dat je alle puzzeltjes binnen 1 minuut moet kunnen laten lopen, dus het is te doen met een niet-super-slim algoritmetje.

*Problem3> :s +s
*Problem3> findLargestPrimeFactor 600851475143 2
***antwoord***
(0.02 secs, 0 bytes)

Die minuut is meer dan genoeg.

[pkuppens]

Probleem 35:
http://www.haskell.org/haskellwiki/99_questions/31_to_41

[RayNbow]

pkuppens schreef op donderdag 19 juni 2008 @ 19:04:
Probleem 35:
http://www.haskell.org/haskellwiki/99_questions/31_to_41

En een uitwerking van probleem 3 staat ook ergens op de Haskell wiki. Het probleem is alleen dat iemand niet echt leert als je het hem voorkauwt.

[Boudewijn]

Nice raynbow.


Vanavond dus weer wat te puzzelen.
Ik wil inderdaad niet een voorbeeldje, maar zelf doen. Ook omdat ik dit puur voor de fun doe en niet als practicum oid .

[Boudewijn]

Ik ben er weer eens mee bezig geweest en snap een paar dingen nog niet helemaal geod.
Ook nav bijvoorbeeld: Wikipedia: Priemfactor

Als ik het algoritme van de wiki uitwerk krijg ik dit:

Neem getal X --willen we ontbinden
Deel X in m en n -- waarbij X == m*n

M en n net zo lang blijven delen tot je alleen maar priemgetallen overhoudt.

Stel : ik wil 32 ontbinden...
Nu kan ik zowel voor 4*8 als 2*16 gaan... hierbij ga ik voor de laatste omdat ik bij 1 begin met delingen proberen (en dus eerst 2 en 16 vind).

2 is priem, dus onthouden we even.

Vervolgens ga ik 16 opdelen in factoren, 2* 8 , waarbij ik dus uitendelijk op een stel 2'en uitkom:

te weten 2*2*2*2*2. Dit is inderdaad een geldige representatie van 32...

Klopt deze denkwijze?

[g4wx3]

Ik heb niet alles proberen te begrijpen, ik ken geen haksell, maar misschien kan ik je helpen met wat php (lijkt op C)
ik heb wiki wel gelezen, en besluit dat je het zo kunt doen:

PHP:

<?php
$priemgetallen = array(2); 
$testgetal = $priemgetallen[0]+1;
for( $testgetal ; $testgetal<100 ; $testgetal++) //priem tot 100
{
  $delers = $priemgetallen;
  $delers[] = 1;
  foreach( $delers as $deler )
  {
  if( ($testgetal%$deler)==0 ) break;
  }
  if( $deler == 1)
  {
   $priemgetallen[] = $testgetal;
  }
}
echo '<pre>';
print_r($priemgetallen);
echo '<pre>';
?>

//NIET boven 10000 gaan zoeken, anders word je systeem misschien onstabiel


EDIT: Nu snap ik pas precies wat er gevraagd is.

"vorm het getal x als product van priemgetallen"

dat wordt iets om later te puzellen...
alle even getalen kan ik wel al verzinnen,
de oneven getallen zijn wat moeilijk.
Misschien da'k nog iets orgineel kan doen met logaritmes.

(Vreemd, da'k toch zo'n slecht punten krijg op school, voor wiskunde, en informatica(word&excel)..)

[ Voor 22% gewijzigd door g4wx3 op 24-06-2008 02:53 ]

[Verwijderd]

Sowieso kan je volgens mij een kleine optimalisatieslag doen door ipv tot de helft van 't getal tot de wortel van 't getal te checken voor factoren.
Stel je hebt 100 als getal dat je wilt ontbinden. Als je eenmaal de 10 gepasseerd bent zal ieder getal dat je probeert een kleinere andere factor hebben in de vermenigvuldiging:
20 -> 5x20 DUS je deelt al eerder door 5.
50 -> 2x50 DUS je deelt al eerder door 2.

Uiteraard zal je in 't geval van 20 al eerder door 2 hebben gedeeld, maar dat terzijde ;-)

Voor 't vinden van priemgetallen denk ik aan de Zeef van Eratosthenes. Is er niet ook zoiets voor dit probleem? 't lijkt me nogal brute-force om 't op deze manier te doen.

[edit]
Wikipedia. Een pagina over 'Integer Factorization', met een aantal linkjes naar algoritmen voor dit probleem. Wellicht handig?

[ Voor 12% gewijzigd door Verwijderd op 24-06-2008 09:34 ]

[Janoz]

g4wx3 schreef op dinsdag 24 juni 2008 @ 02:41:
Ik heb niet alles proberen te begrijpen, ik ken geen haksell, maar misschien kan ik je helpen met wat php (lijkt op C)

C is een imperatieve taal. Deze werken fundamenteel anders dan een functionele taal. Imperative code voorbeelden zijn daarom dus niet zo heel zinvol.

[RayNbow]

Boudewijn schreef op dinsdag 24 juni 2008 @ 00:59:
Als ik het algoritme van de wiki uitwerk krijg ik dit:

Neem getal X --willen we ontbinden
Deel X in m en n -- waarbij X == m*n

[...]

Klopt deze denkwijze?

Dit is ook wat Zoijar en ik eerder in de draad aanraden.

Verwijderd schreef op dinsdag 24 juni 2008 @ 09:32:
[edit]
Wikipedia. Een pagina over 'Integer Factorization', met een aantal linkjes naar algoritmen voor dit probleem. Wellicht handig?

Trial division is de meest simpele om te implementeren en is al in deze draad aangeraden (en voldoet qua snelheid). De andere algoritmen die er staan zijn ingewikkelder en sommige zijn probabilistisch (zie: Pollard's rho algoritme).

[Verwijderd]

Janoz schreef op dinsdag 24 juni 2008 @ 09:39:
[...]

C is een imperatieve taal. Deze werken fundamenteel anders dan een functionele taal. Imperative code voorbeelden zijn daarom dus niet zo heel zinvol.

Ik kan elk algoritme dat in C is geschreven eenvoudig omzetten naar iets dat ongeveer net zo snel werkt in Haskell. Dat jij dat niet kan wil niet zeggen dat een beschrijving dan niet zinvol is.

Hoe Haskell werkt is trouwens niet eens gedefinieerd, alleen een gedeelte van de semantiek.

[Verwijderd]

g4wx3 schreef op dinsdag 24 juni 2008 @ 02:41:
Ik heb niet alles proberen te begrijpen, ik ken geen haksell, maar misschien kan ik je helpen met wat php (lijkt op C)
ik heb wiki wel gelezen, en besluit dat je het zo kunt doen:

PHP:

<?php
$priemgetallen = array(2); 
$testgetal = $priemgetallen[0]+1;
for( $testgetal ; $testgetal<100 ; $testgetal++) //priem tot 100
{
  $delers = $priemgetallen;
  $delers[] = 1;
  foreach( $delers as $deler )
  {
  if( ($testgetal%$deler)==0 ) break;
  }
  if( $deler == 1)
  {
   $priemgetallen[] = $testgetal;
  }
}
echo '<pre>';
print_r($priemgetallen);
echo '<pre>';
?>

//NIET boven 10000 gaan zoeken, anders word je systeem misschien onstabiel


EDIT: Nu snap ik pas precies wat er gevraagd is.

"vorm het getal x als product van priemgetallen"

dat wordt iets om later te puzellen...
alle even getalen kan ik wel al verzinnen,

Nee, dat kun je niet.

[Confusion]

Verwijderd schreef op dinsdag 24 juni 2008 @ 09:32:
Voor 't vinden van priemgetallen denk ik aan de Zeef van Eratosthenes.

Dat is overkill voor dit probleem. Voor een van de latere problemen in de lijst heb je die wel nodig.

@Boudewijn: mijn Python oplossing voor het probleem bevat 1 regel import, 3 regels initialisatie, 5 regels code, waarvan 1 for en 1 if. Vervolgens nog 1 regel om de uitkomst te printen. Does that help? Seriously though: misschien eerst het probleem even oplossen in een taal die je goed kent en daarna pas implementeren in Haskell. Nu maakt het feit dat je nog geen goed algoritme hebt het gewoon moeilijker om iets fatsoenlijks in Haskell neer te zetten.

[ Voor 41% gewijzigd door Confusion op 24-06-2008 23:13 ]

[RayNbow]

Verwijderd schreef op dinsdag 24 juni 2008 @ 22:50:
[...]

Ik kan elk algoritme dat in C is geschreven eenvoudig omzetten naar iets dat ongeveer net zo snel werkt in Haskell. Dat jij dat niet kan wil niet zeggen dat een beschrijving dan niet zinvol is.

Tuurlijk kan dat..., maar levert dat altijd mooie Haskell programma's op?

C:

#include <stdio.h>

int main(int argc, char *argv[]) {
    int n = 12345;
    int p = 2;
    while (p*p < n) {
        if (n % p == 0)
            n /= p;
        p++;
    }
    p = p > n ? p : n;
    printf("p: %d\n", p);
}

Vertalen naar Haskell:
 

Haskell:

module Main where

largestPrime n
 = go n 2
 where go n p | p * p < n   =  if n `mod` p == 0 then
                                   go (n `div` p) (p+1)
                               else
                                   go n (p+1)
              | otherwise   =  max n p

main = print $ largestPrime 12345

Hierin wordt de functie go var1 .. varN gebruikt om de while-loop na te bootsen, waarbij de parameters corresponderen met de lokale variablen in de C versie.
De eerste guard van deze functie correspondeert met de while-conditie in de C versie. De bijbehorende expressie waarin go recursief wordt aangeroepen met nieuwe waardes correspondeert met de nieuwe waardes die de lokale variabelen in de C versie hebben gekregen na een enkele iteratie.
De laatste guard correspondeert met het verlaten van de while-loop.

[Boudewijn]

Verwijderd schreef op dinsdag 24 juni 2008 @ 22:50:
[...]

Ik kan elk algoritme dat in C is geschreven eenvoudig omzetten naar iets dat ongeveer net zo snel werkt in Haskell. Dat jij dat niet kan wil niet zeggen dat een beschrijving dan niet zinvol is.

Hoe Haskell werkt is trouwens niet eens gedefinieerd, alleen een gedeelte van de semantiek.

Dan heb je dus niet door wat functioneel programmeren is .

Het is me ondertussen in haskell gelukt, ik zal het morgen even posten (heb de code atm niet bij de hand).

[ Voor 10% gewijzigd door Boudewijn op 25-06-2008 00:31 ]

[Janoz]

Verwijderd schreef op dinsdag 24 juni 2008 @ 22:50:
[...]

Ik kan elk algoritme dat in C is geschreven eenvoudig omzetten naar iets dat ongeveer net zo snel werkt in Haskell. Dat jij dat niet kan wil niet zeggen dat een beschrijving dan niet zinvol is.

Hoe Haskell werkt is trouwens niet eens gedefinieerd, alleen een gedeelte van de semantiek.

Dat je het kunt is heel leuk en aardig. Dat ik het niet kan heb ik nergens gezegd. Wat ik nu wel ga zeggen is dat ik het nooit zou doen. Dat komt op mij net zo over als zeggen dat je OO gaat proggen in java, maar vervolgens elke class als een module gebruikt en alle methoden static maakt (dus eigenlijk gewoon procedureel blijft programmeren)

De kracht van een functionele taal is dat je je 'functioneel' uit kunt drukken (itt het meer gebruikelijke imperatief). Gebruik je dat niet dan is het gewoon niet zinvol om een functionele taal te gebruiken.

[Verwijderd]

Boudewijn schreef op woensdag 25 juni 2008 @ 00:30:
[...]

Dan heb je dus niet door wat functioneel programmeren is .

Het is me ondertussen in haskell gelukt, ik zal het morgen even posten (heb de code atm niet bij de hand).

Wat is nu weer de reden om te claimen dat ik niet zou weten wat functioneel programmeren is?

[Verwijderd]

Janoz schreef op woensdag 25 juni 2008 @ 08:58:
[...]

Dat je het kunt is heel leuk en aardig. Dat ik het niet kan heb ik nergens gezegd. Wat ik nu wel ga zeggen is dat ik het nooit zou doen. Dat komt op mij net zo over als zeggen dat je OO gaat proggen in java, maar vervolgens elke class als een module gebruikt en alle methoden static maakt (dus eigenlijk gewoon procedureel blijft programmeren)

De kracht van een functionele taal is dat je je 'functioneel' uit kunt drukken (itt het meer gebruikelijke imperatief). Gebruik je dat niet dan is het gewoon niet zinvol om een functionele taal te gebruiken.

Je begrijpt dat dit impliceert dat je dan niet alle algoritmen efficient kunt uitdrukken? Elk "real-world" Haskell programma heeft wel ergens niet functionele code zitten. Dus dit betekent dat jij nooit zo'n programma zult schrijven.

[Janoz]

Nee, dat impliceert het niet. Wat ik 'impliceer' is dat je een algorithme anders moet uitdrukken. Als je een C oplossing rechtstreeks naar Haskell aan het porten bent, ben je gewoon onhandig bezig.

[Verwijderd]

Janoz schreef op woensdag 25 juni 2008 @ 15:33:
Nee, dat impliceert het niet. Wat ik 'impliceer' is dat je een algorithme anders moet uitdrukken. Als je een C oplossing rechtstreeks naar Haskell aan het porten bent, ben je gewoon onhandig bezig.

Wat is een algorithme?

Het impliceert het wel, want niet voor alle problemen zijn efficiente functionele algoritmen bekend (en die zullen er waarschijnlijk ook nooit komen). Stel jij voor om voor alles waarvoor geen functionele manier bekend is, de FFI te gebruiken?

[ Voor 27% gewijzigd door Creepy op 25-06-2008 16:34 ]

[RayNbow]

Verwijderd schreef op woensdag 25 juni 2008 @ 14:49:
Elk "real-world" Haskell programma heeft wel ergens niet functionele code zitten.

Ten eerste, wat versta je onder een "real-world" Haskell programma?
Ten tweede, wat valt bij jou onder niet-functionele code? (Noem voorbeelden/algoritmen?)

[Boudewijn]

Ik gok dat hij haskells IO bedoelt .

Ja dat is niet super sexy gedaan, met die monads, maar het werkt op zich prima .

[RayNbow]

Niet sexy? Monads zijn juist heel erg sexy en elegant. Het zorgt er juist voor dat zelfs IO referential transparent is:

quote: http://geekrant.wordpress.com/2008/06/23/misconceptions/

[...]
Here’s the kicker: this evaluation model means that IO functions are pure. If you use the same IO function in two parts of a program, you may indeed get different return values, but that’s simply because they are parameterized on the RealWorld, which will be different every time. Referential transparency means that a function will always return the same value for the same arguments, but we will never pass the exact same argument to an IO function, so IO functions are, trivially, referentially transparent.

[Boudewijn]

ja ik weet het, maar het principe van IO is in een functionele taal niet echt handig (IO loze programma's zijn veeeel fijner ).


Monads werken prima ja, idd (ghehe is mijn jaar ST@UU toch nog ergens goed voor geweest).

Volgens mij heb ik een werkende implementatie, zal hem straks eens posten.

[Verwijderd]

RayNbow schreef op donderdag 26 juni 2008 @ 00:58:
[...]

Ten eerste, wat versta je onder een "real-world" Haskell programma?

Een programma dat geen speeltje is en met grote hoeveelheden data om moet gaan (> 10 miljoen objecten), typisch > 10KLOC is en voor productiedoeleinden bestemd is.

Ten tweede, wat valt bij jou onder niet-functionele code? (Noem voorbeelden/algoritmen?)

Niet-functionele code is code die niet geïmplementeerd kan worden zonder gebruik te maken van referenties (dus IO dan wel ST monad). Groepen datastructuren waar een directe verbinding tussen twee structuren (bijv. twee bomen) moet zijn en in constante tijd moeten kunnen worden veranderd kunnen niet functioneel worden geimplementeerd. Zippers zijn hier niet toepasbaar. Soms wil je echt iets veranderen in plaats van de hele spine aflopen.

Er zijn wel manier om dit te omzeilen, maar die zijn of geen Haskell 98 meer of erg langzaam.

Dus een probleem waarin er n links zijn naar een structuur X, maar deze structuur moet in O(1) worden aangepast naar een structuur X', waarbij na de aanpassing alle n links wijzen naar X' i.p.v. X.

[Boudewijn]

Verwijderd schreef op donderdag 26 juni 2008 @ 15:30:
[...]

Een programma dat geen speeltje is en met grote hoeveelheden data om moet gaan (> 10 miljoen objecten), typisch > 10KLOC is en voor productiedoeleinden bestemd is.

Ik kan me prima voorstellen dat je dingen als encryptie-technieken in Haskell (of andere func taal) implementeert. Dat lijkt me een prima optie, zijn dat dan geen real world programmas?

Niet-functionele code is code die niet geïmplementeerd kan worden zonder gebruik te maken van referenties (dus IO dan wel ST monad).

Klopt, alleen IO is niet echt anders te doen lijkt me . IO is per definitie niet functioneel (als in je weet nooit wat er uit komt) , maar ook een rng is dat ook niet (om nog maar een cliche te noemen).

[Soultaker]

Waarom is I/O niet "functioneel"? Je kunt je programma modelleren als een functie die invoer transformeert naar uitvoer; in sommige talen wordt I/O zo ook geïmplementeert.

Effectief doet Haskell's I/O monad dat ook. De monad scheidt alleen de implementatie van de interface.

[Verwijderd]

Boudewijn schreef op donderdag 26 juni 2008 @ 15:38:
Ik kan me prima voorstellen dat je dingen als encryptie-technieken in Haskell (of andere func taal) implementeert. Dat lijkt me een prima optie, zijn dat dan geen real world programmas?

Als ik een exacte definitie voor een real-world programma zou moeten geven, dan zou ik eeuwig bezig zijn. Een encryptieprogramma haalt geen 10KLOC of je doet iets verkeerd.

Klopt, alleen IO is niet echt anders te doen lijkt me . IO is per definitie niet functioneel (als in je weet nooit wat er uit komt) , maar ook een rng is dat ook niet (om nog maar een cliche te noemen).

Ja, maar in Haskell scheidt je je systeem in zoveel mogelijk afgeschermde stukjes, zodat het (zo is de gedachte) makkelijker te onderhouden wordt. Dus je leest bijv. een bestand in, dan doe je iets ingewikkelds (op een functionele manier (jouw encryptieprogramma is daar een voorbeeld van)) met het bestand en dan schrijf je het weer weg. Daar zit bijna geen I/O in. Met heel veel programma's is dat mogelijk, maar niet in alle (wat ik bedoelde te zeggen). Of je nu IO of ST gebruikt maakt in principe niet zoveel uit, anders dan dat ST een compiler extentie is (en nog een paar garanties geeft) en IO niet.

Soultaker schreef op donderdag 26 juni 2008 @ 15:48:
Waarom is I/O niet "functioneel"? Je kunt je programma modelleren als een functie die invoer transformeert naar uitvoer; in sommige talen wordt I/O zo ook geïmplementeert.

Effectief doet Haskell's I/O monad dat ook. De monad scheidt alleen de implementatie van de interface.

Ja, ik weet hoe monads werken en je hebt in theorie gelijk. En nee, het is niet productief om er op die manier over na te denken.

Een C programma zou dan eigenlijk ook puur functioneel moeten zijn. Het werkt alleen in de C monad. Dit zou de betekenis van "functioneel programmeren" tot nul reduceren.

[ Voor 20% gewijzigd door Verwijderd op 26-06-2008 16:08 . Reden: Soultaker kwam er tussen ]