Potencia entera

Definir la función

   potencia :: Integer -> Integer -> Integer

1	potencia :: Integer -> Integer -> Integer

tal que potencia x n es x elevado al número natural n. Por ejemplo,

   potencia 2 3  ==  8

1	potencia 2 3 == 8

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import Data.List (foldl')
import Control.Arrow ((***))
import Test.QuickCheck

-- 1ª solución
-- ===========

potencia1 :: Integer -> Integer -> Integer
potencia1 _ 0 = 1
potencia1 m n = m * potencia1 m (n-1)

-- 2ª solución
-- ===========

potencia2 :: Integer -> Integer -> Integer
potencia2 m = aux
  where aux 0 = 1
        aux n = m * aux (n-1)

-- 3ª solución
-- ===========

potencia3 :: Integer -> Integer -> Integer
potencia3 m = aux 1
  where aux r 0 = r
        aux r n = aux (r*m) (n-1)

-- 4ª solución
-- ===========

potencia4 :: Integer -> Integer -> Integer
potencia4 m = aux 1
  where aux r 0 = r
        aux r n = (aux $! (r*m)) $! (n-1)

-- 5ª solución
-- ===========

potencia5 :: Integer -> Integer -> Integer
potencia5 m n = product [m | _ <- [1..n]]

-- 6ª solución
-- ===========

potencia6 :: Integer -> Integer -> Integer
potencia6 m n = foldl' (*) 1 [m | _ <- [1..n]]

-- 7ª solución
-- ===========

potencia7 :: Integer -> Integer -> Integer
potencia7 m n =
  fst (until (\ (_,k) -> k == n)
             (\ (r,k) -> (r*m, k+1))
             (1,0))

-- 8ª solución
-- ===========

potencia8 :: Integer -> Integer -> Integer
potencia8 m n =
  fst (until ((== n) . snd)
             ((m *) *** (1 +))
             (1,0))

-- 9ª solución
-- ===========

potencia9 :: Integer -> Integer -> Integer
potencia9 m n = m^n

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_potencia :: Integer -> NonNegative Integer -> Bool
prop_potencia m (NonNegative n) =
  all (== potencia1 m n)
      [potencia2 m n,
       potencia3 m n,
       potencia4 m n,
       potencia5 m n,
       potencia6 m n,
       potencia7 m n,
       potencia8 m n,
       potencia9 m n]

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

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> length (show (potencia1 2 (2*10^5)))
--    60206
--    (2.97 secs, 2,602,252,408 bytes)
--    λ> length (show (potencia2 2 (2*10^5)))
--    60206
--    (2.63 secs, 2,624,652,624 bytes)
--    λ> length (show (potencia3 2 (2*10^5)))
--    60206
--    (3.41 secs, 2,619,606,368 bytes)
--    λ> length (show (potencia4 2 (2*10^5)))
--    60206
--    (0.64 secs, 2,636,888,928 bytes)
--    λ> length (show (potencia5 2 (2*10^5)))
--    60206
--    (2.47 secs, 2,597,108,000 bytes)
--    λ> length (show (potencia6 2 (2*10^5)))
--    60206
--    (0.35 secs, 2,582,488,824 bytes)
--    λ> length (show (potencia7 2 (2*10^5)))
--    60206
--    (2.48 secs, 2,616,406,272 bytes)
--    λ> length (show (potencia8 2 (2*10^5)))
--    60206
--    (2.40 secs, 2,608,652,736 bytes)
--    λ> length (show (potencia9 2 (2*10^5)))
--    60206
--    (0.01 secs, 4,212,968 bytes)
--
--    λ> length (show (potencia4 2 (10^6)))
--    301030
--    (10.39 secs, 63,963,999,656 bytes)
--    λ> length (show (potencia6 2 (10^6)))
--    301030
--    (8.90 secs, 63,691,999,552 bytes)
--    λ> length (show (potencia9 2 (10^6)))
--    301030
--    (0.04 secs, 19,362,032 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

import Data.List (foldl')

import Control.Arrow ((***))

import Test.QuickCheck

-- 1ª solución

-- ===========

potencia1 :: Integer -> Integer -> Integer

potencia1 _ 0 = 1

potencia1 m n = m * potencia1 m (n-1)

-- 2ª solución

-- ===========

potencia2 :: Integer -> Integer -> Integer

potencia2 m = aux

where aux 0 = 1

aux n = m * aux (n-1)

-- 3ª solución

-- ===========

potencia3 :: Integer -> Integer -> Integer

potencia3 m = aux 1

where aux r 0 = r

aux r n = aux (r*m) (n-1)

-- 4ª solución

-- ===========

potencia4 :: Integer -> Integer -> Integer

potencia4 m = aux 1

where aux r 0 = r

aux r n = (aux $! (r*m)) $! (n-1)

-- 5ª solución

-- ===========

potencia5 :: Integer -> Integer -> Integer

potencia5 m n = product [m | _ <- [1..n]]

-- 6ª solución

-- ===========

potencia6 :: Integer -> Integer -> Integer

potencia6 m n = foldl' (*) 1 [m | _ <- [1..n]]

-- 7ª solución

-- ===========

potencia7 :: Integer -> Integer -> Integer

potencia7 m n =

fst (until (\ (_,k) -> k == n)

(\ (r,k) -> (r*m, k+1))

(1,0))

-- 8ª solución

-- ===========

potencia8 :: Integer -> Integer -> Integer

potencia8 m n =

fst (until ((== n) . snd)

((m *) *** (1 +))

(1,0))

-- 9ª solución

-- ===========

potencia9 :: Integer -> Integer -> Integer

potencia9 m n = m^n

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_potencia :: Integer -> NonNegative Integer -> Bool

prop_potencia m (NonNegative n) =

all (== potencia1 m n)

[potencia2 m n,

potencia3 m n,

potencia4 m n,

potencia5 m n,

potencia6 m n,

potencia7 m n,

potencia8 m n,

potencia9 m n]

-- La comprobación es

-- λ> quickCheck prop_potencia

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> length (show (potencia1 2 (2*10^5)))

-- 60206

-- (2.97 secs, 2,602,252,408 bytes)

-- λ> length (show (potencia2 2 (2*10^5)))

-- 60206

-- (2.63 secs, 2,624,652,624 bytes)

-- λ> length (show (potencia3 2 (2*10^5)))

-- 60206

-- (3.41 secs, 2,619,606,368 bytes)

-- λ> length (show (potencia4 2 (2*10^5)))

-- 60206

-- (0.64 secs, 2,636,888,928 bytes)

-- λ> length (show (potencia5 2 (2*10^5)))

-- 60206

-- (2.47 secs, 2,597,108,000 bytes)

-- λ> length (show (potencia6 2 (2*10^5)))

-- 60206

-- (0.35 secs, 2,582,488,824 bytes)

-- λ> length (show (potencia7 2 (2*10^5)))

-- 60206

-- (2.48 secs, 2,616,406,272 bytes)

-- λ> length (show (potencia8 2 (2*10^5)))

-- 60206

-- (2.40 secs, 2,608,652,736 bytes)

-- λ> length (show (potencia9 2 (2*10^5)))

-- 60206

-- (0.01 secs, 4,212,968 bytes)

-- λ> length (show (potencia4 2 (10^6)))

-- 301030

-- (10.39 secs, 63,963,999,656 bytes)

-- λ> length (show (potencia6 2 (10^6)))

-- 301030

-- (8.90 secs, 63,691,999,552 bytes)

-- λ> length (show (potencia9 2 (10^6)))

-- 301030

-- (0.04 secs, 19,362,032 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from functools import reduce
from operator import mul
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 potencia1(m: int, n: int) -> int:
    if n == 0:
        return 1
    return m * potencia1(m, n-1)

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

def potencia2(m: int, n: int) -> int:
    def aux(k: int) -> int:
        if k == 0:
            return 1
        return m * aux(k-1)
    return aux(n)

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

def potencia3(m: int, n: int) -> int:
    def aux(r: int, k: int) -> int:
        if k == 0:
            return r
        return aux(r*m, k-1)
    return aux(1, n)

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

# producto(xs) es el producto de los elementos de xs. Por ejemplo,
#    producto([2, 3, 5])  ==  30
def producto(xs: list[int]) -> int:
    return reduce(mul, xs, 1)

def potencia4(m: int, n: int) -> int:
    return producto([m]*n)

# 5ª solución
# ===========

def potencia5(m: int, n: int) -> int:
    r = 1
    for _ in range(0, n):
        r = r * m
    return r

# 6ª solución
# ===========

def potencia6(m: int, n: int) -> int:
    return m**n

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

# La propiedad es
@given(st.integers(),
       st.integers(min_value=0, max_value=100))
def test_potencia(m: int, n: int) -> None:
    r = potencia1(m, n)
    assert potencia2(m, n) == r
    assert potencia3(m, n) == r
    assert potencia4(m, n) == r
    assert potencia5(m, n) == r
    assert potencia6(m, n) == r

# La comprobación es
#    src> poetry run pytest -q potencia_entera.py
#    1 passed in 0.17s

# 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('potencia1(2, 2*10**4)')
#    0.01 segundos
#    >>> tiempo('potencia2(2, 2*10**4)')
#    0.01 segundos
#    >>> tiempo('potencia3(2, 2*10**4)')
#    0.02 segundos
#    >>> tiempo('potencia4(2, 2*10**4)')
#    0.01 segundos
#    >>> tiempo('potencia5(2, 2*10**4)')
#    0.01 segundos
#    >>> tiempo('potencia6(2, 2*10**4)')
#    0.00 segundos
#
#    >>> tiempo('potencia4(2, 5*10**5)')
#    2.87 segundos
#    >>> tiempo('potencia5(2, 5*10**5)')
#    3.17 segundos
#    >>> tiempo('potencia6(2, 5*10**5)')
#    0.00 segundos

100

101

102

103

104

105

106

107

108

109

110

from functools import reduce

from operator import mul

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 potencia1(m: int, n: int) -> int:

if n == 0:

return 1

return m * potencia1(m, n-1)

# 2ª solución

# ===========

def potencia2(m: int, n: int) -> int:

def aux(k: int) -> int:

if k == 0:

return 1

return m * aux(k-1)

return aux(n)

# 3ª solución

# ===========

def potencia3(m: int, n: int) -> int:

def aux(r: int, k: int) -> int:

if k == 0:

return r

return aux(r*m, k-1)

return aux(1, n)

# 4ª solución

# ===========

# producto(xs) es el producto de los elementos de xs. Por ejemplo,

# producto([2, 3, 5]) == 30

def producto(xs: list[int]) -> int:

return reduce(mul, xs, 1)

def potencia4(m: int, n: int) -> int:

return producto([m]*n)

# 5ª solución

# ===========

def potencia5(m: int, n: int) -> int:

r = 1

for _ in range(0, n):

r = r * m

return r

# 6ª solución

# ===========

def potencia6(m: int, n: int) -> int:

return m**n

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.integers(),

st.integers(min_value=0, max_value=100))

def test_potencia(m: int, n: int) -> None:

r = potencia1(m, n)

assert potencia2(m, n) == r

assert potencia3(m, n) == r

assert potencia4(m, n) == r

assert potencia5(m, n) == r

assert potencia6(m, n) == r

# La comprobación es

# src> poetry run pytest -q potencia_entera.py

# 1 passed in 0.17s

# 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('potencia1(2, 2*10**4)')

# 0.01 segundos

# >>> tiempo('potencia2(2, 2*10**4)')

# 0.01 segundos

# >>> tiempo('potencia3(2, 2*10**4)')

# 0.02 segundos

# >>> tiempo('potencia4(2, 2*10**4)')

# 0.01 segundos

# >>> tiempo('potencia5(2, 2*10**4)')

# 0.01 segundos

# >>> tiempo('potencia6(2, 2*10**4)')

# 0.00 segundos

# >>> tiempo('potencia4(2, 5*10**5)')

# 2.87 segundos

# >>> tiempo('potencia5(2, 5*10**5)')

# 3.17 segundos

# >>> tiempo('potencia6(2, 5*10**5)')

# 0.00 segundos

El código se encuentra en GitHub.

Potencia entera

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Se puede imprimir o compartir con

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico