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 x2 – 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.