-- 1ª definición
sumasDe2Cuadrados1 :: Integer -> [(Integer, Integer)]
sumasDe2Cuadrados1 n =
[(x,y) | x <- [n,n-1..0]
, y <- [0..x]
, x*x+y*y == n]
-- 2ª definición:
sumasDe2Cuadrados2 :: Integer -> [(Integer, Integer)]
sumasDe2Cuadrados2 n =
[(x,y) | x <- [a,a-1..0]
, y <- [0..x]
, x*x+y*y == n]
where a = (floor . sqrt . fromIntegral) n
-- 3ª definición
sumasDe2Cuadrados3 :: Integer -> [(Integer, Integer)]
sumasDe2Cuadrados3 n =
[(raizEntera x, raizEntera y)
| y <- takeWhile (<= n `div` 2) cuadrados
, let x = n - y
, esCuadrado x]
cuadrados :: [Integer]
cuadrados = map (^2) [0..]
esCuadrado :: Integer -> Bool
esCuadrado x =
x == y * y
where y = raizEntera x
raizEntera :: Integer -> Integer
raizEntera x =
(floor . sqrt . fromIntegral) x
-- 4ª definición
sumasDe2Cuadrados4 :: Integer -> [(Integer, Integer)]
sumasDe2Cuadrados4 n = aux ((floor . sqrt . fromIntegral) n) 0
where aux x y | x < y = []
| x*x + y*y < n = aux x (y+1)
| x*x + y*y == n = (x,y) : aux (x-1) (y+1)
| otherwise = aux (x-1) y
-- Comparación de eficiencia
-- λ> sumasDe2Cuadrados1 2020
-- [(42,16),(38,24)]
-- (4.29 secs, 621,601,336 bytes)
-- λ> sumasDe2Cuadrados2 2020
-- [(42,16),(38,24)]
-- (0.01 secs, 488,496 bytes)
-- λ> sumasDe2Cuadrados3 2020
-- [(42,16),(38,24)]
-- (0.02 secs, 197,256 bytes)
-- λ> sumasDe2Cuadrados4 2020
-- [(42,16),(38,24)]
-- (0.01 secs, 175,088 bytes)
--
-- λ> length (sumasDe2Cuadrados2 48612265)
-- 32
-- (51.25 secs, 7,395,035,904 bytes)
-- λ> length (sumasDe2Cuadrados3 48612265)
-- 32
-- (0.06 secs, 8,368,296 bytes)
-- λ> length (sumasDe2Cuadrados4 48612265)
-- 32
-- (0.04 secs, 3,483,168 bytes)
--
-- λ> length (sumasDe2Cuadrados3 (10^12))
-- 7
-- (7.32 secs, 1,137,167,688 bytes)
-- λ> length (sumasDe2Cuadrados4 (10^12))
-- 7
-- (3.64 secs, 480,776,736 bytes)