## 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.