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: factorization, kata, praxis, programming, wheel