## Posts Tagged ‘wheel’

### Programming Praxis – Wheel Factorization

May 8, 2009

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.