1votos

Descomposiciones como suma de dos cuadrados en Haskell

por jalonso hace 9 meses

Tres definiciones de creciente eficiencia.

543
Descomposiciones como suma de dos cuadrados
8 soluciones Fácil

Descomponer un número como suma de dos cuadrados.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
-- 1ª definición (por comprensión elemental): 
sumasDe2Cuadrados1 :: Integer -> [(Integer, Integer)] 
sumasDe2Cuadrados1 n =  
    [(x,y) | x <- [n,n-1..0], 
             y <- [0..x], 
             x*x+y*y == n] 
 
-- 2ª definición (por comprensión con cotas refinadas): 
sumasDe2Cuadrados2 :: Integer -> [(Integer, Integer)] 
sumasDe2Cuadrados2 n =  
    [(x,y) | x <- [a,a-1..0], 
             y <- [0..x], 
             x*x+y*y == n] 
    where a = (ceiling.sqrt.fromIntegral) n 
 
-- 3ª definición (por recursión): 
sumasDe2Cuadrados3 :: Integer -> [(Integer, Integer)] 
sumasDe2Cuadrados3 n = aux a 0  
    where a = (ceiling.sqrt.fromIntegral) n 
          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 
1 comentario
0votos
543

Escrito por jalonso hace 9 meses

La 2ª es más eficiente que la 1ª:
ghci> sumasDe2Cuadrados1 (10^4)
[(100,0),(96,28),(80,60)]
(7.53 secs, 5209799396 bytes)
ghci> sumasDe2Cuadrados2 (10^4)
[(100,0),(96,28),(80,60)]
(0.01 secs, 1572932 bytes)

La 3ª es más eficiente que la 2ª:
ghci> sumasDe2Cuadrados2 25000000
[(5000,0),(4800,1400),(4680,1760),(4216,2688),(4000,3000)]
(5.86 secs, 2465983496 bytes)
ghci> sumasDe2Cuadrados3 25000000
[(5000,0),(4800,1400),(4680,1760),(4216,2688),(4000,3000)]
(0.01 secs, 1571040 bytes)

Con la 3ª se calcula las descomposiciones de 10000000009 rápidamente:
ghci> sumasDe2Cuadrados3 10000000009
[(100000,3),(97640,21597)]
(0.11 secs, 29190232 bytes)

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.