# Integer factorization

13 messages
Open this post in threaded view
|

## Integer factorization

 Hello, I am solving a problem of finding the largest prime factor of 600851475143 (Project Euler is great for learning new language!), and came with the following solution (it uses the most ineffective approach to finding prime numbers, however is able to factor the above number in fraction of second): factors :: Integer -> [Integer] factors n = doFactors n (eratosthenesFilter [1..n]) doFactors n primes     | null newPrimes = []     | otherwise      =         let topPrime = head newPrimes in         if topPrime == n             then [topPrime]             else topPrime : (doFactors (n `quot` topPrime) primes)     where         newPrimes = snd \$ break (\x -> (n `rem` x) == 0) primes eratosthenesFilter :: [Integer] -> [Integer] eratosthenesFilter [] = [] eratosthenesFilter (num : nums)     | num == 1  = eratosthenesFilter nums     | otherwise = num : (eratosthenesFilter \$ doFilter num nums)     where         doFilter num nums = filter (\x -> x > num && (x `rem` num) /= 0) nums What would you do different (including stylistic changes)? What are the general comments about efficiency (not of the algorithm, but of the implementation: for example, is it fine to use break at every invocation of doFactors?) and elegance of the solution? Thanks and regards, Sergey
Open this post in threaded view
|

## Re: Integer factorization

 On http://www.haskell.org/haskellwiki/Prime_numbers"primeFactors" should do what you want (although I don't like the the pattern matching on "1") Cheers Christian Sergey V. Mikhanov wrote: >    Hello, > > I am solving a problem of finding the largest prime factor of > 600851475143 (Project Euler is great for learning new language!), and > came with the following solution (it uses the most ineffective > approach to finding prime numbers, however is able to factor the above > number in fraction of second): > > factors :: Integer -> [Integer] > > factors n = doFactors n (eratosthenesFilter [1..n]) > > doFactors n primes >     | null newPrimes = [] >     | otherwise      = >         let topPrime = head newPrimes in >         if topPrime == n >             then [topPrime] >             else topPrime : (doFactors (n `quot` topPrime) primes) >     where >         newPrimes = snd \$ break (\x -> (n `rem` x) == 0) primes > > eratosthenesFilter :: [Integer] -> [Integer] > > eratosthenesFilter [] = [] > eratosthenesFilter (num : nums) >     | num == 1  = eratosthenesFilter nums >     | otherwise = num : (eratosthenesFilter \$ doFilter num nums) >     where >         doFilter num nums = filter (\x -> x > num && (x `rem` num) /= 0) nums > > What would you do different (including stylistic changes)? What are > the general comments about efficiency (not of the algorithm, but of > the implementation: for example, is it fine to use break at every > invocation of doFactors?) and elegance of the solution? > > Thanks and regards, > Sergey
Open this post in threaded view
|

## Re: Integer factorization

 In reply to this post by Sergey V. Mikhanov Sergey V. Mikhanov wrote: > > factors :: Integer -> [Integer] > factors n = doFactors n (eratosthenesFilter [1..n]) > > doFactors n primes >     | null newPrimes = [] >     | otherwise      = >         let topPrime = head newPrimes in >         if topPrime == n >             then [topPrime] >             else topPrime : (doFactors (n `quot` topPrime) primes) >     where >         newPrimes = snd \$ break (\x -> (n `rem` x) == 0) primes > > eratosthenesFilter :: [Integer] -> [Integer] > eratosthenesFilter [] = [] > eratosthenesFilter (num : nums) >     | num == 1  = eratosthenesFilter nums >     | otherwise = num : (eratosthenesFilter \$ doFilter num nums) >     where >         doFilter num nums = filter (\x -> x > num && (x `rem` num) /= 0) nums > > What would you do different (including stylistic changes)? What are > the general comments about efficiency (not of the algorithm, but of > the implementation: for example, is it fine to use break at every > invocation of doFactors?) and elegance of the solution? Stylistically, one usually uses shorter variable names in Haskell. Also, the guards in  doFactors  are better expressed as pattern matching and the if can be turned into guards.     factors :: Integer -> [Integer]     factors n = go n \$ eratosthenes [2..n]         where         go n []              = []         go n (p:ps)            | n `mod` p == 0  = p : go (n `div` p) ps            | otherwise       = go n ps     eratosthenes :: [Integer] -> [Integer]     eratosthenes []     = []     eratosthenes (p:ps) = p : erathostenes ps'        where        ps' = filter (\x -> x > p && (x `mod` p) /= 0) ps Other than that, efficiency is best understood as algorithmic efficiency; there are not straightforward "tweaks" that give you the warm fuzzy feeling of "writing efficient code". Regards, apfelmus -- http://apfelmus.nfshost.com
Open this post in threaded view
|

## Re: Integer factorization

Open this post in threaded view
|

## Re: Integer factorization

 >>>>> "Francesco" == Francesco Bochicchio <[hidden email]> writes:     Francesco> Nevertheless readability tends to be a big issue in     Francesco> languages used in IT industry, and my feeling is that     Francesco> haskell tends to err on the laconic side of the     Francesco> balance. Strongly seconded. -- Colin Adams Preston Lancashire
Open this post in threaded view
|

## Integer factorization

 In reply to this post by Sergey V. Mikhanov On 3/10/2009, "Sergey V. Mikhanov" <[hidden email]> wrote: >   Hello, > >I am solving a problem of finding the largest prime factor of >600851475143 (Project Euler is great for learning new language!), and >came with the following solution (it uses the most ineffective >approach to finding prime numbers, however is able to factor the above >number in fraction of second): > >factors :: Integer -> [Integer] > >factors n = doFactors n (eratosthenesFilter [1..n]) > >doFactors n primes >    | null newPrimes = [] >    | otherwise      = >        let topPrime = head newPrimes in >        if topPrime == n >            then [topPrime] >            else topPrime : (doFactors (n `quot` topPrime) primes) >    where >        newPrimes = snd \$ break (\x -> (n `rem` x) == 0) primes > >eratosthenesFilter :: [Integer] -> [Integer] > >eratosthenesFilter [] = [] >eratosthenesFilter (num : nums) >    | num == 1  = eratosthenesFilter nums >    | otherwise = num : (eratosthenesFilter \$ doFilter num nums) >    where >        doFilter num nums = filter (\x -> x > num && (x `rem` num) /= 0) nums > >What would you do different (including stylistic changes)? What are >the general comments about efficiency (not of the algorithm, but of >the implementation: for example, is it fine to use break at every >invocation of doFactors?) and elegance of the solution? > >Thanks and regards, >Sergey This is my solution to the same problem.  I'm just a beginner with Haskell as well, so just consider this as an alternate solution, not an ideal solution. The bottom 2 functions were pulled out of support code that I use for all my Project Euler solutions, so that's why they seem unnecessarily generic. I think the only real advantages of my solution over yours is that I take advantage of the fact that primes are always odd (except for the number 2) and that the largest prime factor of a number will always be <= half its value. main = putStrLn output output = show result result = largestPrimeFactor 600851475143 largestPrimeFactor n = last \$ primeFactors n {-  - Gets the prime factors of an integer.  -} primeFactors :: (Integral a) => a -> [a] primeFactors n = primeFactorsUsingPrimesList (2:[3, 5 .. n `div` 2]) n {-  - Gets the prime factors of a number.  The primes list passed as the first  - argument is not required to be a list of primes.  It is simply required to be  - a list of values to try to divide the input from.  If this list contains  - non-prime values, they should be ordered.  If the list does not contain all  - of the primes that are divisors of the input value, then the result will be  - incorrect.  -} primeFactorsUsingPrimesList :: (Integral a) => [a] -> a -> [a] primeFactorsUsingPrimesList _      1 = [] primeFactorsUsingPrimesList (x:xs) n = if n `rem` x == 0      then x : primeFactorsUsingPrimesList (x:xs) (n `div` x)      else primeFactorsUsingPrimesList xs n primeFactorsUsingPrimesList []     n = [n]
Open this post in threaded view
|

## Re: Integer factorization

Open this post in threaded view
|

## Re: Integer factorization

 Greetings! > A second, and my main reason for short names, or rather against long > names, is that names should be to the point. None of the names > >   newPrimes >   topPrime >   doFactors >   doFilter > > accurately describe the object they represent. The primes are not "new", > the prime is not "on top". The "do" is a prefix does not carry a meaning > either, it just conveys that  doFactors  has something to do with > factors . This is best expressed by making  doFactors  a local > definition in the where-block of  factors. > Those remarks are fine with me! I asked about the stylistic changes because I came from the, hm, Java world and would like to avoid "writing familiar things in unfamiliar language". In Java, factors() and doFactors() would be a perfectly named methods: factors() is public, auxiliary doFactors() is private and essentially _does_ the factoring. > > Out of curiosity, there is any reason why you called the auxiliary > function > > 'go' ? > > Convention. Often, an auxiliary function that does basically the same > thing as the main function  factors  but with an extra parameter will be > named  factors' . The apostrophe has the drawback that it's easy to > forget, so some people now name such auxiliary functions  go  instead. > I think having a local function 'go' in 'factors' is aboslutely plausible: it is local, there's no ambiguity. Regards, Sergey -------------- next part -------------- An HTML attachment was scrubbed... URL: http://www.haskell.org/pipermail/beginners/attachments/20090313/74eea645/attachment.htm
Open this post in threaded view
|

## Re: Integer factorization

 In reply to this post by Heinrich Apfelmus >>>>> "Heinrich" == Heinrich Apfelmus <[hidden email]> writes:     Heinrich> Abstraction is the one driving force for very short     Heinrich> names. For example, take the definition of foldr     Heinrich>    foldr f z [] = z foldr f z (x:xs) = f x (foldr f z     Heinrich> xs)     Heinrich> Since this function is polymorphic, so f , z and the xs     Heinrich> can be anything, using more "descriptive" variable names     Heinrich> is simply not possible; the key point of fold is its     Heinrich> generality. Wouldn't unit be a better descriptive name than z? -- Colin Adams Preston Lancashire
Open this post in threaded view
|

## Re: Integer factorization

 Colin Paul Adams wrote: >>>>>> "Heinrich" == Heinrich Apfelmus <[hidden email]> writes: > >     Heinrich> Abstraction is the one driving force for very short >     Heinrich> names. For example, take the definition of foldr > >     Heinrich>    foldr f z [] = z foldr f z (x:xs) = f x (foldr f z >     Heinrich> xs) > >     Heinrich> Since this function is polymorphic, so f , z and the xs >     Heinrich> can be anything, using more "descriptive" variable names >     Heinrich> is simply not possible; the key point of fold is its >     Heinrich> generality. > > Wouldn't unit be a better descriptive name than z? I have never heard of a unit in relation to  fold , I'm afraid. Monoids and groups have units, as do physicists and a few other mathematical structures. While  z  is indeed quite often the unit of a monoid, for instance in     sum     = foldr (+) 0     product = foldr (*) 1     concat  = foldr (++) [] it doesn't have to be the unit of a monoid. Regards, apfelmus -- http://apfelmus.nfshost.com
Open this post in threaded view
|