Menu Close

Cuadrado más cercano

José A. Alonso,

Definir la función

   cuadradoCercano :: Integer -> Integer

tal que (cuadradoCercano n) es el número cuadrado más cercano a n, donde n es un entero positivo. Por ejemplo,

   cuadradoCercano 2       == 1
   cuadradoCercano 6       == 4
   cuadradoCercano 8       == 9
   cuadradoCercano (10^46) == 10000000000000000000000000000000000000000000000

Soluciones

import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
cuadradoCercano1 :: Integer -> Integer
cuadradoCercano1 n
  | n - b < c - n = b
  | otherwise     = c
  where a = raizEntera1 n
        b = a^2
        c = (a+1)^2
 
-- (raizEntera x) es el mayor entero cuyo cuadrado no es mayor que
-- x. Por ejemplo,
--    raizEntera 8   ==  2
--    raizEntera 9   ==  3
--    raizEntera 10  ==  3
raizEntera1 :: Integer -> Integer
raizEntera1 x =
  last (takeWhile (\n -> n^2 <= x) [1..])
 
-- 2ª solución
-- ===========
 
cuadradoCercano2 :: Integer -> Integer
cuadradoCercano2 n
  | n - b < c - n = b
  | otherwise     = c
  where a = raizEntera2 n
        b = a^2
        c = (a+1)^2
 
raizEntera2 :: Integer -> Integer
raizEntera2 x = aux (1,x)
    where aux (a,b) | d == x    = c
                    | c == a    = c
                    | x <= d    = aux (a,c)
                    | otherwise = aux (c,b)
            where c = (a+b) `div` 2
                  d = c^2
 
-- 3ª solución
-- ===========
 
cuadradoCercano3 :: Integer -> Integer
cuadradoCercano3 n
  | n - b < c - n = b
  | otherwise     = c
  where a = raizEntera3 n
        b = a^2
        c = (a+1)^2
 
raizEntera3 :: Integer -> Integer
raizEntera3 0 = 0
raizEntera3 1 = 1
raizEntera3 n = until aceptable mejora n
  where mejora x    = (x + n `div` x) `div` 2
        aceptable x = x^2 <= n
 
-- 4ª solución
-- ===========
 
cuadradoCercano4 :: Integer -> Integer
cuadradoCercano4 = (^ 2) . round . sqrt . fromIntegral
 
-- Equivalencia de las definiciones
-- ================================
 
-- La propiedad es
prop_cuadradoCercano :: Positive Integer -> Bool
prop_cuadradoCercano (Positive x) =
  all (== cuadradoCercano1 x)
      [cuadradoCercano2 x,
       cuadradoCercano3 x,
       cuadradoCercano4 x]
 
-- La comprobación es
--    λ> quickCheck prop_cuadradoCercano
--    +++ OK, passed 100 tests.
 
-- Aunque ha pasado los 100 tests, las definiciones no son
-- equivalentes. Por ejemplo,
--    λ> cuadradoCercano3 (10^46) == cuadradoCercano (10^46)
--    False
--    λ> cuadradoCercano3 (10^46)
--    9999999999999998322278400000000070368744177664
--    λ> cuadradoCercano (10^46)
--    10000000000000000000000000000000000000000000000
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> cuadradoCercano1 (10^14)
--    100000000000000
--    (4.59 secs, 5,920,475,784 bytes)
--    λ> cuadradoCercano2 (10^14)
--    100000000000000
--    (0.01 secs, 512,472 bytes)
--    λ> cuadradoCercano3 (10^14)
--    100000000000000
--    (0.01 secs, 494,248 bytes)
--    λ> cuadradoCercano4 (10^14)
--    100000000000000
--    (0.01 secs, 475,152 bytes)
--
--    λ> length (show (cuadradoCercano2 (10^20000)))
--    20001
--    (3.94 secs, 1,446,675,504 bytes)
--    λ> length (show (cuadradoCercano3 (10^20000)))
--    20001
--    (4.50 secs, 926,647,904 bytes)

El código se encuentra en GitHub

La elaboración de las soluciones se muestra en el siguiente vídeo:

,

6 soluciones de “Cuadrado más cercano”

  1. Responder
    Carlos 
    isqrt :: Integer -> Integer
isqrt 0 = 0
isqrt 1 = 1
isqrt n = head $ dropWhile stop $ iterate step (div n 2)
  where step x = div (x + div n x) 2
        stop x = x^2 > n
 
cuadradoCercano :: Integer -> Integer
cuadradoCercano n = f (i^2,(i+1)^2)
  where f (a,b) = if n - a < b - n then a else b
        i = isqrt n
  2. Responder
    Juan Díaz 
    cuadradoCercano :: Integer -> Integer
cuadradoCercano n = (round (sqrt (fromIntegral n)))^2
    • Responder
      Pedro Pérez

      La definición de Juan Díaz se puede escribir como composición funcional:

      cuadradoCercano :: Integer -> Integer
cuadradoCercano = (^ 2) . round . sqrt . fromIntegral
    • Responder
      María Ruiz

      La definición de Juan se puede escribir en Python:

      def cuadradoCercano(n):
    return round(n ** 0.5) ** 2
      • Responder
        Luis Galán

        Las definiciones de Juan, Pedro y María fallan en el cuarto ejemplo. Su evaluación es

        λ> sqrt (10^46)
9.999999999999999e22

        y debería de dar 10^46.

        El motivo del fallo es el uso de la aritmética de punto flotante en la función sqrt

        λ> sqrt (10^46)
9.999999999999999e22

        debería de dar 10^23.

  3. Responder
    j0sejuan

    Algo más rápida.

    cuadradoCercano :: Integer -> Integer
cuadradoCercano x = f 0 x' 0 (x'^2)
  where x' = x `div` 2 + 1
        f a b a2 b2 = let c  = (a + b) `div` 2
                          c2 = c^2
                      in  if b - a < 2
                            then if x - a2 < b2 - x then a2 else b2
                            else case c2 `compare` x of
                                  LT -> f c b c2 b2
                                  EQ -> c2
                                  GT -> f a c a2 c2

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.