## SPOJ Pell (Mid pelling)

Pell (Mid pelling) is related to Pell’s equation. It is similar to Project Euler 66 and SPOJ EQU2. I just wrote the quick solution from mathworld but I found Chakravala method very interesting. Accepted Haskell code.

import qualified Data.ByteString.Char8 as BS import Data.List import Data.Maybe ( fromJust ) continuedFraction :: Integer -> [ Integer ] continuedFraction n = map ( \ ( a , _ , _ ) -> a ) . iterate fun $ ( d , 0 , 1 ) where d = truncate . sqrt . fromIntegral $ n fun ( a0 , p0 , q0 ) = ( a1 , p1 , q1 ) where p1 = a0 * q0 - p0 q1 = div ( n - p1 ^ 2 ) q0 a1 = div ( d + p1 ) q1 pellSolver :: Integer -> BS.ByteString pellSolver n | perfectSqr n = BS.pack. show $ ( -1 ) | otherwise = ( BS.pack . show $ p ) `BS.append` ( BS.pack " " ) `BS.append` ( BS.pack.show $ q ) where d = truncate . sqrt . fromIntegral $ n lst = takeWhile ( /= 2 * d ) . continuedFraction $ n len = length lst r@( x : y : xs ) = take ( if even len then len else 2 * len ) . continuedFraction $ n ( p0 , p1 , q0 , q1 ) = ( x , x * y + 1 , 1 , y ) ( p , _ ) = foldl' compute ( p1 , p0 ) $ xs ( q , _ ) = foldl' compute ( q1 , q0 ) $ xs compute :: ( Integer , Integer ) -> Integer -> ( Integer , Integer ) compute ( p1 , p0 ) a = ( a * p1 + p0 , p1 ) perfectSqr :: Integer -> Bool perfectSqr n = d * d == n where d = truncate . sqrt . fromIntegral $ n readI :: BS.ByteString -> Integer readI = fst . fromJust . BS.readInteger main = BS.interact $ BS.unlines . map ( pellSolver . readI ) . tail . BS.lines

Advertisements

Would you like to enter my free programming competition? http://contestcoding.wordpress.com/

Comment by lewiscornwall1 | March 23, 2013 |