Raíces enteras
Definir la función
raizEnt :: Integer -> Integer -> Integer
tal que raizEnt x n es la raíz entera n-ésima de x; es decir, el mayor número entero y tal que \(y^n \leq x\). Por ejemplo,
raizEnt 8 3 == 2 raizEnt 9 3 == 2 raizEnt 26 3 == 2 raizEnt 27 3 == 3 raizEnt (10^50) 2 == 10000000000000000000000000
Comprobar con QuickCheck que para todo número natural n,
raizEnt (10^(2*n)) 2 == 10^n
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
Soluciones en Haskell
module Raices_enteras where import Test.Hspec (Spec, hspec, it, shouldBe) import Test.QuickCheck (quickCheck) -- 1ª solución -- =========== raizEnt1 :: Integer -> Integer -> Integer raizEnt1 x n = last (takeWhile (\y -> y^n <= x) [0..]) -- 2ª solución -- =========== raizEnt2 :: Integer -> Integer -> Integer raizEnt2 x n = floor ((fromIntegral x)**(1 / fromIntegral n)) -- Nota. La solución anterior falla para números grandes. Por ejemplo, -- λ> raizEnt2 (10^50) 2 == 10^25 -- False -- 3ª solución -- =========== raizEnt3 :: Integer -> Integer -> Integer raizEnt3 x n = aux (1,x) where aux (a,b) | d == x = c | c == a = c | d < x = aux (c,b) | otherwise = aux (a,c) where c = (a+b) `div` 2 d = c^n -- Comparación de eficiencia -- ========================= -- λ> raizEnt1 (10^14) 2 -- 10000000 -- (6.15 secs, 6,539,367,976 bytes) -- λ> raizEnt2 (10^14) 2 -- 10000000 -- (0.00 secs, 0 bytes) -- λ> raizEnt3 (10^14) 2 -- 10000000 -- (0.00 secs, 25,871,944 bytes) -- -- λ> raizEnt2 (10^50) 2 -- 9999999999999998758486016 -- (0.00 secs, 0 bytes) -- λ> raizEnt3 (10^50) 2 -- 10000000000000000000000000 -- (0.00 secs, 0 bytes) -- Comprobación de la propiedad -- ============================ -- La propiedad es prop_raizEnt :: Integer -> Bool prop_raizEnt n = raizEnt3 (10^(2*m)) 2 == 10^m where m = abs n -- La comprobación es -- λ> quickCheck prop_raizEnt -- +++ OK, passed 100 tests. -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ raizEnt1 8 3 `shouldBe` 2 it "e2" $ raizEnt1 9 3 `shouldBe` 2 it "e3" $ raizEnt1 26 3 `shouldBe` 2 it "e4" $ raizEnt1 27 3 `shouldBe` 3 it "e5" $ raizEnt2 8 3 `shouldBe` 2 it "e6" $ raizEnt2 9 3 `shouldBe` 2 it "e7" $ raizEnt2 26 3 `shouldBe` 2 it "e8" $ raizEnt2 27 3 `shouldBe` 3 it "e9" $ raizEnt3 8 3 `shouldBe` 2 it "e10" $ raizEnt3 9 3 `shouldBe` 2 it "e11" $ raizEnt3 26 3 `shouldBe` 2 it "e12" $ raizEnt3 27 3 `shouldBe` 3 -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- e4 -- e5 -- e6 -- e7 -- e8 -- e9 -- e10 -- e11 -- e12 -- -- Finished in 0.0007 seconds -- 12 examples, 0 failures
Soluciones en Python
from itertools import count, takewhile from math import floor 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 # =========== def raizEnt(x: int, n: int) -> int: return list(takewhile(lambda y : y ** n <= x, count(0)))[-1] # 2ª solución # =========== def raizEnt2(x: int, n: int) -> int: return floor(x ** (1 / n)) # Nota. La solución anterior falla para números grandes. Por ejemplo, # >>> raizEnt2(10**50, 2) == 10 **25 # False # 3ª solución # =========== def raizEnt3(x: int, n: int) -> int: def aux(a: int, b: int) -> int: c = (a + b) // 2 d = c ** n if d == x: return c if c == a: return c if d < x: return aux(c, b) return aux(a, c) return aux(1, x) # 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('raizEnt(10**14, 2)') # 2.71 segundos # >>> tiempo('raizEnt2(10**14, 2)') # 0.00 segundos # >>> tiempo('raizEnt3(10**14, 2)') # 0.00 segundos # # >>> raizEnt2(10**50, 2) # 10000000000000000905969664 # >>> raizEnt3(10**50, 2) # 10000000000000000000000000 # Comprobación de la propiedad # ============================ # La propiedad es @given(st.integers(min_value=0, max_value=1000)) def test_raizEntP(n: int) -> None: assert raizEnt3(10**(2*n), 2) == 10**n # La comprobación es # >>> test_raizEnt)() # >>> # Verificación # ============ def test_raizEnt() -> None: assert raizEnt(8, 3) == 2 assert raizEnt(9, 3) == 2 assert raizEnt(26, 3) == 2 assert raizEnt(27, 3) == 3 assert raizEnt2(8, 3) == 2 assert raizEnt2(9, 3) == 2 assert raizEnt2(26, 3) == 2 assert raizEnt2(27, 3) == 3 assert raizEnt3(8, 3) == 2 assert raizEnt3(9, 3) == 2 assert raizEnt3(26, 3) == 2 assert raizEnt3(27, 3) == 3 print("Verificado") # La comprobación es # >>> test_raizEnt() # Verificado