Programming Praxis – Wheel Factorization

In today’s Programming Praxis problem we’re supposed to factor numbers both the naive way and using Wheel factorization. Let’s go.

First, let’s define a function that finds factors using trial division:

tdFactors :: Integer -> [Integer] -> [Integer]
tdFactors _ [] = []
tdFactors r (x:xs) | x * x > r    = [r]
                   | mod r x == 0 = x : tdFactors (div r x) (x:xs)
                   | otherwise    = tdFactors r xs

Using that, the function for naive factorization is trivial:

factorNaive :: Integer -> [Integer]
factorNaive n = tdFactors n [2..]

Now for the wheel factorization. First we define a function that tells us which columns of our wheel to use given the circumference.

spokes :: Integer -> [Bool]
spokes c = map ((== 1) . gcd c) [1..c]

To construct our wheel, we keep repeating this pattern and use only the numbers from the correct columns (and correct the start of the wheel).

wheel :: [Integer] -> [Integer]
wheel ps = (ps ++) . drop 1 . map snd . filter fst $
           zip (cycle . spokes $ product ps) [1..]

The function to do wheel factorization is practically identical to the naive one:

factorWheel :: Integer -> [Integer]
factorWheel n = tdFactors n $ wheel [2,3,5,7]

And of course we need to test if everything works:

main :: IO ()
main = do print $ factorNaive 600851475143
          print $ factorWheel 600851475143

And we’re done. Pretty simple.

About these ads

Tags: , , , ,

15 Responses to “Programming Praxis – Wheel Factorization”

  1. programmingpraxis Says:

    I submitted this code at http://codepad.org/xbZJhC9N and got a timeout error while factorNaive was running. Did I do something wrong?

    Phil

  2. Remco Niemeijer Says:

    Hm. I guess they’ve set their timeout limit pretty low.

    A benchmark on my machine shows about 2.7 and 0.7 seconds for factorNaive and factorWheel when running in the interpreter and 0.2 and 0.1 seconds for the compiled version. How fast does your Scheme solution run?

  3. programmingpraxis Says:

    On my two-year-old pc at work, 0 ms for both, running in the interpreter.

    On the same machine as my Haskell attempt, at http://codepad.org/HScJryvX, 0 ms for both; I don’t know what the hardware is, but the Scheme system is an old version of MzScheme, an interpreter.

    Phil

  4. Remco Niemeijer Says:

    One speedup that works, assuming you only call tdFactors with an increasing list of numbers, is to replace factor with

    factor r (x:xs) | x > r = []
    | mod r x == 0 = x : factor (div r x) (x:xs)
    | otherwise = factor r xs

    (the only change is the added first guard).
    That reduces execution time to 30 and 0 ms interpreted and 0 ms compiled.

  5. programmingpraxis Says:

    Shouldn’t you stop as soon as x*x > r? But doesn’t the takewhile already do that?

    Phil

  6. Remco Niemeijer Says:

    No, if you do that then it only gives three of the four factors of the test number. The x > r clause does obsolete the takeWhile bit though (again, assuming increasing numbers).

  7. programmingpraxis Says:

    Then something is wrong. You’re not handling the termination properly. You should be able to quit as soon as you exceed the square root of the remaining cofactor.

  8. Remco Niemeijer Says:

    Correct. It should be

    | x * x > r = [r]

    On the bright side, now I understand why you were adding n to the factors at the end in your solution :)

    I’ve updated the main post with this version.

  9. programmingpraxis Says:

    I bet your timings are faster now.

  10. Remco Niemeijer Says:

    Yeah, 0-15 and 0 ms interpreted as expected. And I realized that my original version only worked with random orderings in a very limited number of cases (it could only be in random order until the first case where x > sqrt(n), after that all xs had to be more than sqrt(n).
    Thanks for the improvement :)

  11. programmingpraxis Says:

    Please post your revised code at Programming Praxis, along with a discussion of why it is better than the original.

  12. Remco Niemeijer Says:

    One further minor optimization: I interpreted the assignment so that we were supposed to find only the unique factors (e.g 60 results in [2,3,5] instead of [2,2,3,5]). Since your solution doesn’t, we can remove the nub function and the required import. Saves another two lines.

  13. Remco Niemeijer Says:

    And with nub gone, the internal function factor becomes the entire function definition. Another line gone.

  14. programmingpraxis Says:

    If you’re removing lines, you can take out tdFactors _ [] = []. It makes the function partial, but is unneeded.

  15. Remco Niemeijer Says:

    Obviously, but I prefer my code not to throw any compilation warnings. Besides, this way it also works on non-infinite lists (not needed in this program, but still).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: