Posts Tagged ‘fermat’s’

Programming Praxis – Fermat’s Method

May 19, 2009

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.