Today’s Programming Praxis problem brings us yet another factorization problem, this time using Fermat’s method. Originally I tried using the algorithm from the assignment, but that resulted in pretty much a direct translation of his Scheme solution, since I couldn’t find a way to express it that was both more elegant and not slower. Since that would be boring, we’re going to use a slightly different approach to Fermat’s method that is slightly shorter and faster.

First we need a way to take the square root of integers:

isqrt :: Integer -> Integer isqrt = ceiling . sqrt . fromIntegral

What this algorithm does is check whether x^{2} – n is square for any xs between sqrt(n) and n. If so, we return the factors of n (which are further factorized if needed).

factor :: Integer -> [Integer] -> [Integer] factor _ [] = [] factor n (x:xs) | y*y /= x*x - n = factor n xs | x - y == 1 = [x + y] | otherwise = concatMap factors [x - y, x + y] where y = isqrt (x*x - n)

Like the Scheme solution, we divide by 2 until we have an odd number to work with, since Fermat’s method only works on odd numbers.

factors :: Integer -> [Integer] factors n | even n = 2 : factors (div n 2) | otherwise = factor n [isqrt n..n]

And, as usual, we test our code:

main :: IO () main = print $ factors 600851475143

Nine lines of code. Not bad.