7
\$\begingroup\$

Please review my implementation of Fermat's Factorization.

fermat :: Int -> Maybe (Int, Int)
fermat n = odd' n >> (go $ ceiling $ sqrt (fromIntegral n)) 
   where go a = case (try n a) of j @ (Just _) -> j
                                  Nothing      -> go (a + 1) 

odd' :: Int -> Maybe Int
odd' x = if (odd x) then Just x else Nothing

try :: Int -> Int -> Maybe (Int, Int)
try n a = fmap (\b -> ((a + b), (a - b))) result
  where result = get_perfect_sq (a^2 - n)

get_perfect_sq :: Int -> Maybe Int
get_perfect_sq x = if (sq * sq == x) then Just sq else Nothing
  where sq = floor $ sqrt (fromIntegral x :: Float)

examples

ghci> fermat 5995
Just (109,55)

-- prime per http://www.bigprimes.net/cruncher/1300633/
ghci> fermat 1300633
Just (1300633,1)
\$\endgroup\$
6
\$\begingroup\$

odd' seems like a useless function, you never use its result, only its monadic context. Use a guard on fermat instead.

fermat n | odd n     = Just $ -- ...
         | otherwise = Nothing

Don't use snake_case in Haskell (get_perfect_sq). We're a camelCase language.

Instead of writing your recursive functions explicitly, try to use higher order functions out of Prelude. They more clearly express intent to readers of your code by highlighting common patterns. In this case, having read Wikipedia's page on Fermat's factorization method, the pseudo-code given in the Basic Method section shows that the primary operation of the function iterates on changing values of \$a\$ and \$b2\$. In Haskell we can use iterate to produce an infinite lazy stream of values, and find to grab the first that meets a condition.

-- given odd n
let a  = ceiling . sqrt $ fromIntegral n
    b2 = a * a - n
in find squareb2 $ iterate step (a, b2)

I'd also be sure to strap a comment to the top with the pseudo-code or algorithm you're trying to implement. It aids understanding and error recognition far easier.

{-
From https://en.wikipedia.org/wiki/Fermat%27s_factorization_method

FermatFactor(N): // N should be odd
  a ← ceil(sqrt(N))
  b2 ← a*a - N
  while b2 isn't a square:
    a ← a + 1 // equivalently: b2 ← b2 + 2*a + 1
    b2 ← a*a - N // a ← a + 1
  endwhile
  return a - sqrt(b2) // or a + sqrt(b2)
-}
fermat :: Integer -> Maybe (Integer, Integer)
fermat n | odd n     = Just . solutions $ find squareb2 (iterate step (a_0, b2_0))
         | otherwise = Nothing
  where
    a_0  = ceiling . sqrt $ fromIntegral n
    b2_0 = a_0 * a_0 - n

    step (a, b2) = (a + 1, b2 + 2 * a + 1)

    squareb2 = isSquare . snd

    solutions (a, b2) = let b = floor . sqrt $ fromIntegral b2 in (a - b, a + b)
\$\endgroup\$
  • \$\begingroup\$ Thanks for this detailed answer! Could you please tell me where find comes from? I didn't see it: Prelude> :t find | <interactive>:1:1: Not in scope: find \$\endgroup\$ – Kevin Meredith May 7 '15 at 14:28
  • \$\begingroup\$ Also, as a follow-up, do you typically prefer to use inner functions, i.e. a_0, step, etc.? I personally (not an experienced Haskel'er) like to see the types, i.e. I like outer functions. I'm curious of when you choose one over the other. \$\endgroup\$ – Kevin Meredith May 7 '15 at 14:32
  • \$\begingroup\$ find is from Data.List. You can include type signatures in local definitions (let or where clauses) like you would for the top-level. It's somewhat less common unless your inner types are complex, but there's no real reason not to. Defining things locally or globally is a real gut instinct for me, usually it comes down to whether I would ever need to test or reference a function independently, and in the case of mathematical functions I don't think I would. Not a great difference though as long as they're all written in close proximity. \$\endgroup\$ – bisserlis May 7 '15 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.