cuadradoCercano :: Integer -> Integer

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

import Test.Hspec (Spec, describe, hspec, it, shouldBe)
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

-- La 4ª solución es incorrecta. Por ejemplo,
--    λ> cuadradoCercano4 (10^46)
--    9999999999999998322278400000000070368744177664
--    λ> cuadradoCercano3 (10^46)
--    10000000000000000000000000000000000000000000000

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

specG :: (Integer -> Integer) -> Spec
specG cuadradoCercano = do
  it "e1" $
    cuadradoCercano 2 `shouldBe` 1
  it "e2" $
    cuadradoCercano 6 `shouldBe` 4
  it "e3" $
    cuadradoCercano 8 `shouldBe` 9

spec :: Spec
spec = do
  describe "def. 1" $ specG cuadradoCercano1
  describe "def. 2" $ specG cuadradoCercano2
  describe "def. 3" $ specG cuadradoCercano3

-- La verificación es
--    λ> verifica
--    9 examples, 0 failures

-- Equivalencia de las definiciones
-- ================================

-- La propiedad es
prop_cuadradoCercano :: Positive Integer -> Bool
prop_cuadradoCercano (Positive x) =
  all (== cuadradoCercano1 x)
      [cuadradoCercano2 x,
       cuadradoCercano3 x]

-- La comprobación es
--    λ> quickCheck prop_cuadradoCercano
--    +++ OK, passed 100 tests.

-- 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)
--
--    λ> 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)

from itertools import count, takewhile
from math import sqrt
from sys import setrecursionlimit
from timeit import Timer, default_timer

from hypothesis import given
from hypothesis import strategies as st

setrecursionlimit(10**6)

# 1ª solución
# ===========

# raizEntera(x) es el mayor entero cuyo cuadrado no es mayor que
# x. Por ejemplo,
#    raizEntera(8)   ==  2
#    raizEntera(9)   ==  3
#    raizEntera(10)  ==  3
def raizEntera1(x: int) -> int:
    return list(takewhile(lambda n: n**2 <= x, count(1)))[-1]

def cuadradoCercano1(n: int) -> int:
    a = raizEntera1(n)
    b = a**2
    c = (a+1)**2
    if n - b < c - n:
        return b
    return c

# 2ª solución
# ===========

def raizEntera2(x: int) -> int:
    def aux(a: int, b: int) -> int:
        c = (a+b) // 2
        d = c**2
        if d == x:
            return c
        if c == a:
            return c
        if x <= d:
            return aux(a,c)
        return aux(c,b)
    return aux(1,x)

def cuadradoCercano2(n: int) -> int:
    a = raizEntera2(n)
    b = a**2
    c = (a+1)**2
    if n - b < c - n:
        return b
    return c

# 3ª solución
# ===========

def raizEntera3(n: int) -> int:
    if n == 0:
        return 0
    if n == 1:
        return 1
    x = n
    while x * x > n:
        x = (x + n // x) // 2
    return x

def cuadradoCercano3(n: int) -> int:
    a = raizEntera3(n)
    b = a**2
    c = (a+1)**2
    if n - b < c - n:
        return b
    return c

# 4ª solución
# ===========

def cuadradoCercano4(n: int) -> int:
    return round(sqrt(n)) ** 2

# La 4ª solución es incorrecta. Por ejemplo,
#    >>> cuadradoCercano4(10**46)
#    9999999999999998322278400000000070368744177664
#    >>> cuadradoCercano3(10**46)
#    10000000000000000000000000000000000000000000000

# Verificación
# ============

def test_cuadradoCercano() -> None:
    for cuadradoCercano in [cuadradoCercano1, cuadradoCercano2,
                            cuadradoCercano3, cuadradoCercano4]:
        assert cuadradoCercano(2) == 1
        assert cuadradoCercano(6) == 4
        assert cuadradoCercano(8) == 9
    print("Verificado")

# La verificación es
#    >>> test_cuadradoCercano()
#    Verificado

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(st.integers(min_value=1, max_value=1000))
def test_cuadradoCercano_equiv(x: int) -> None:
    r = cuadradoCercano1(x)
    assert cuadradoCercano2(x) == r
    assert cuadradoCercano3(x) == r
    assert cuadradoCercano4(x) == r

# La comprobación es
#    >>> test_cuadradoCercano_equiv()
#    >>>

# Comparación de eficiencia
# =========================

def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

# La comparación es
#    >>> tiempo('cuadradoCercano1(10**14)')
#    2.88 segundos
#    >>> tiempo('cuadradoCercano2(10**14)')
#    0.00 segundos
#    >>> tiempo('cuadradoCercano3(10**14)')
#    0.00 segundos
#
#    >>> tiempo('cuadradoCercano2(10**6000)')
#    1.21 segundos
#    >>> tiempo('cuadradoCercano3(10**6000)')
#    2.08 segundos

(ql:quickload "fiveam" :silent t)

(defpackage :cuadrado-mas-cercano
  (:use :cl
        :fiveam))

(in-package :cuadrado-mas-cercano)

;;; 1ª solución
;;; ===========

;;; (raiz-entera1 x) es el mayor entero cuyo cuadrado no es mayor que
;;; x. Por ejemplo,
;;;    (raiz-entera1 8)   ==  2
;;;    (raiz-entera1 9)   ==  3
;;;    (raiz-entera1 10)  ==  3
(defun raiz-entera1 (x)
  (loop for n from 1
        while (<= (* n n) x)
        finally (return (- n 1))))

(defun cuadrado-cercano1 (n)
  (let* ((a (raiz-entera1 n))
         (b (* a a))
         (c (* (+ a 1) (+ a 1))))
    (if (< (- n b) (- c n))
        b
        c)))

;;; 2ª solución
;;; ===========

;;; (raiz-entera2 x) es el mayor entero cuyo cuadrado no es mayor que
;;; x. Por ejemplo,
;;;    (raiz-entera2 8)   ==  2
;;;    (raiz-entera2 9)   ==  3
;;;    (raiz-entera2 10)  ==  3
(defun raiz-entera2 (x)
  (labels ((aux (a b)
             (let* ((c (floor (+ a b) 2))
                   (d (* c c)))
               (cond ((= d x) c)
                     ((= c a) c)
                     ((<= x d) (aux a c))
                     (t (aux c b))))))
    (aux 1 x)))


(defun cuadrado-cercano2 (n)
  (let* ((a (raiz-entera2 n))
         (b (* a a))
         (c (* (+ a 1) (+ a 1))))
    (if (< (- n b) (- c n))
        b
        c)))

;;; 3ª solución
;;; ===========

(defun cuadrado-cercano3 (n)
  (expt (round (sqrt n)) 2))

;;; La 3ª solución es incorrecta. Por ejemplo,
;;;    > (cuadrado-cercano3 (expt 10 46))
;;;    9999999556392621642119762459277931153299865600
;;;    > (cuadrado-cercano2 (expt 10 46))
;;;    10000000000000000000000000000000000000000000000

;;; Verificación
;;; ============

(test cuadrado-cercano
  (mapc (lambda (cuadrado-cercano)
          (is (= (funcall cuadrado-cercano 2) 1))
          (is (= (funcall cuadrado-cercano 6) 4))
          (is (= (funcall cuadrado-cercano 8) 9)))
        '(cuadrado-cercano1
          cuadrado-cercano2
          cuadrado-cercano3
          )))

(defun verifica ()
  (run 'cuadrado-cercano))

;;; La verificación es
;;;    (verifica)
;;;
;;;    Running test CUADRADO-CERCANO ........

;;; Equivalencia de las definiciones
;;; ================================

;;; La propiedad es
(test cuadrado-cercano-equiv
  (for-all ((n (gen-integer :min 1 :max 10)))
    (is (= (cuadrado-cercano1 n)
           (cuadrado-cercano2 n)))))

(defun comprueba ()
  (run 'cuadrado-cercano-equiv))

;;; La comprobación es
;;;    > (comprueba)
;;;
;;;    Running test LISTA-CUADRADA-EQUIV ...

;;; Comparación de eficiencia
;;; =========================

;;; La comparación es
;;;    > (time (cuadrado-cercano1 (expt 10 14)))
;;;    0.082 seconds of real time
;;;    > (time (cuadrado-cercano2 (expt 10 14)))
;;;    0.000 seconds of real time
;;;    > (time (cuadrado-cercano3 (expt 10 14)))
;;;    0.000 seconds of real time