Menu Close

Mes: octubre 2022

Número a partir de sus dígitos

José A. Alonso, ,

Definir la función

   listaNumero :: [Integer] -> Integer

tal que listaNumero xs es el número formado por los dígitos xs. Por ejemplo,

   listaNumero [5]        == 5
   listaNumero [1,3,4,7]  == 1347
   listaNumero [0,0,1]    == 1

Soluciones

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


Soluciones en Haskell

import Data.List (foldl')
import Data.Digits (unDigits)
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
listaNumero1 :: [Integer] -> Integer
listaNumero1 = aux . reverse
  where
    aux :: [Integer] -> Integer
    aux []     = 0
    aux (x:xs) = x + 10 * aux xs
 
-- 2ª solución
-- ===========
 
listaNumero2 :: [Integer] -> Integer
listaNumero2 = aux 0
  where
    aux :: Integer -> [Integer] -> Integer
    aux r []     = r
    aux r (x:xs) = aux (x+10*r) xs
 
-- 3ª solución
-- ===========
 
listaNumero3 :: [Integer] -> Integer
listaNumero3 = aux 0
  where
    aux :: Integer -> [Integer] -> Integer
    aux = foldl (\ r x -> x + 10 * r)
 
-- 4ª solución
-- ===========
 
listaNumero4 :: [Integer] -> Integer
listaNumero4 = foldl' (\ r x -> x + 10 * r) 0
 
-- 5ª solución
-- ===========
 
listaNumero5 :: [Integer] -> Integer
listaNumero5 xs = sum [y*10^n | (y,n) <- zip (reverse xs) [0..]]
 
-- 6ª solución
-- ===========
 
listaNumero6 :: [Integer] -> Integer
listaNumero6 xs = sum (zipWith (\ y n -> y*10^n) (reverse xs) [0..])
 
-- 7ª solución
-- ===========
 
listaNumero7 :: [Integer] -> Integer
listaNumero7 = unDigits 10
 
-- 7ª solución
-- ===========
 
listaNumero8 :: [Integer] -> Integer
listaNumero8 = read . concatMap show
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_listaNumero :: NonEmptyList Integer -> Bool
prop_listaNumero (NonEmpty xs) =
  all (== listaNumero1 ys)
      [listaNumero2 ys,
       listaNumero3 ys,
       listaNumero4 ys,
       listaNumero5 ys,
       listaNumero6 ys,
       listaNumero7 ys,
       listaNumero8 ys]
  where ys = map (`mod` 10) xs
 
-- La comprobación es
--    λ> quickCheck prop_listaNumero
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> length (show (listaNumero1 (replicate (10^5) 9)))
--    100000
--    (4.01 secs, 4,309,740,064 bytes)
--    λ> length (show (listaNumero2 (replicate (10^5) 9)))
--    100000
--    (4.04 secs, 4,307,268,856 bytes)
--    λ> length (show (listaNumero3 (replicate (10^5) 9)))
--    100000
--    (4.08 secs, 4,300,868,816 bytes)
--    λ> length (show (listaNumero4 (replicate (10^5) 9)))
--    100000
--    (0.42 secs, 4,288,480,208 bytes)
--    λ> length (show (listaNumero4 (replicate (10^5) 9)))
--    100000
--    (0.41 secs, 4,288,480,208 bytes)
--    λ> length (show (listaNumero5 (replicate (10^5) 9)))
--    100000
--    (43.35 secs, 10,702,827,328 bytes)
--    λ> length (show (listaNumero6 (replicate (10^5) 9)))
--    100000
--    (46.89 secs, 10,693,227,280 bytes)
--    λ> length (show (listaNumero7 (replicate (10^5) 9)))
--    100000
--    (4.33 secs, 4,297,499,344 bytes)
--    λ> length (show (listaNumero8 (replicate (10^5) 9)))
--    100000
--    (0.03 secs, 60,760,360 bytes)

El código se encuentra en GitHub.


Soluciones en Python

from functools import reduce
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 listaNumero1(xs: list[int]) -> int:
    def aux(ys: list[int]) -> int:
        if ys:
            return ys[0] + 10 * aux(ys[1:])
        return 0
    return aux(list(reversed(xs)))
 
# 2ª solución
# ===========
 
def listaNumero2(xs: list[int]) -> int:
    def aux(r: int, ys: list[int]) -> int:
        if ys:
            return aux(ys[0] + 10 * r, ys[1:])
        return r
    return aux(0, xs)
 
# 3ª solución
# ===========
 
def listaNumero3(xs: list[int]) -> int:
    return reduce((lambda r, x: x + 10 * r), xs)
 
# 4ª solución
# ===========
 
def listaNumero4(xs: list[int]) -> int:
    r = 0
    for x in xs:
        r = x + 10 * r
    return r
 
# 5ª solución
# ===========
 
def listaNumero5(xs: list[int]) -> int:
    return sum((y * 10**n
                for (y, n) in zip(list(reversed(xs)), range(0, len(xs)))))
 
# 6ª solución
# ===========
 
def listaNumero6(xs: list[int]) -> int:
    return int("".join(list(map(str, xs))))
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(st.lists(st.integers(min_value=0, max_value=9), min_size=1))
def test_listaNumero(xs: list[int]) -> None:
    r = listaNumero1(xs)
    assert listaNumero2(xs) == r
    assert listaNumero3(xs) == r
    assert listaNumero4(xs) == r
    assert listaNumero5(xs) == r
    assert listaNumero6(xs) == r
 
# La comprobación es
#    src> poetry run pytest -q numero_a_partir_de_sus_digitos.py
#    1 passed in 0.27s
 
# 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('listaNumero1([9]*(10**4))')
#    0.28 segundos
#    >>> tiempo('listaNumero2([9]*(10**4))')
#    0.16 segundos
#    >>> tiempo('listaNumero3([9]*(10**4))')
#    0.01 segundos
#    >>> tiempo('listaNumero4([9]*(10**4))')
#    0.01 segundos
#    >>> tiempo('listaNumero5([9]*(10**4))')
#    0.41 segundos
#    >>> tiempo('listaNumero6([9]*(10**4))')
#    0.00 segundos
#
#    >>> tiempo('listaNumero3([9]*(2*10**5))')
#    3.45 segundos
#    >>> tiempo('listaNumero4([9]*(2*10**5))')
#    3.29 segundos
#    >>> tiempo('listaNumero6([9]*(2*10**5))')
#    0.19 segundos

El código se encuentra en GitHub.

Leer más →

Suma de los dígitos de un número

José A. Alonso, ,

Definir la función

   sumaDigitos :: Integer -> Integer

tal que sumaDigitos n es la suma de los dígitos de n. Por ejemplo,

   sumaDigitos 3     ==  3
   sumaDigitos 2454  == 15
   sumaDigitos 20045 == 11

Soluciones

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


Soluciones en Haskell

import Data.List (foldl')
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
sumaDigitos1 :: Integer -> Integer
sumaDigitos1 n = sum (digitos n)
 
-- (digitos n) es la lista de los dígitos del número n. Por ejemplo,
--    digitos 320274  ==  [3,2,0,2,7,4]
digitos :: Integer -> [Integer]
digitos n = [read [x] | x <- show n]
 
-- Nota. En lugar de la definición anterior de digitos se puede usar
-- cualquiera del ejercicio "Dígitos de un número" https://bit.ly/3Tkhc2T
 
-- 2ª solución
-- ===========
 
sumaDigitos2 :: Integer -> Integer
sumaDigitos2 n = foldl' (+) 0 (digitos n)
 
-- 3ª solución
-- ===========
 
sumaDigitos3 :: Integer -> Integer
sumaDigitos3 n
  | n < 10    = n
  | otherwise = n `rem` 10 + sumaDigitos3 (n `div` 10)
 
-- 4ª solución
-- ===========
 
sumaDigitos4 :: Integer -> Integer
sumaDigitos4 = aux 0
  where aux r n
          | n < 10    = r + n
          | otherwise = aux (r + n `rem` 10) (n `div` 10)
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_sumaDigitos :: NonNegative Integer -> Bool
prop_sumaDigitos (NonNegative n) =
  all (== sumaDigitos1 n)
      [sumaDigitos2 n,
       sumaDigitos3 n,
       sumaDigitos4 n]
 
-- La comprobación es
--    λ> quickCheck prop_sumaDigitos
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> sumaDigitos1 (product [1..2*10^4])
--    325494
--    (0.64 secs, 665,965,832 bytes)
--    λ> sumaDigitos2 (product [1..2*10^4])
--    325494
--    (0.41 secs, 660,579,064 bytes)
--    λ> sumaDigitos3 (product [1..2*10^4])
--    325494
--    (1.58 secs, 1,647,082,224 bytes)
--    λ> sumaDigitos4 (product [1..2*10^4])
--    325494
--    (1.72 secs, 1,662,177,792 bytes)
--
--    λ> sumaDigitos1 (product [1..5*10^4])
--    903555
--    (2.51 secs, 3,411,722,136 bytes)
--    λ> sumaDigitos2 (product [1..5*10^4])
--    903555
--    (2.30 secs, 3,396,802,856 bytes)

El código se encuentra en GitHub.


Soluciones en Python

from functools import reduce
from math import factorial
from operator import add
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
# ===========
 
# digitos(n) es la lista de los dígitos del número n. Por ejemplo,
#    digitos(320274)  ==  [3, 2, 0, 2, 7, 4]
def digitos(n: int) -> list[int]:
    return list(map(int, list(str(n))))
 
def sumaDigitos1(n: int) -> int:
    return sum(digitos(n))
 
# Nota. En lugar de la definición anterior de digitos se puede usar
# cualquiera del ejercicio "Dígitos de un número" https://bit.ly/3Tkhc2T
 
# 2ª solución
# ===========
 
def sumaDigitos2(n: int) -> int:
    return reduce(add, digitos(n))
 
# 3ª solución
# ===========
 
def sumaDigitos3(n: int) -> int:
    if n < 10:
        return n
    return n % 10 + sumaDigitos3(n // 10)
 
# 4ª solución
# ===========
 
def sumaDigitos4(n: int) -> int:
    def aux(r: int, m: int) -> int:
        if m < 10:
            return r + m
        return aux(r + m % 10, m // 10)
    return aux(0, n)
 
# 5ª solución
# ===========
 
def sumaDigitos5(n: int) -> int:
    r = 0
    for x in digitos(n):
        r = r + x
    return r
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(st.integers(min_value=0, max_value=1000))
def test_sumaDigitos(n: int) -> None:
    r = sumaDigitos1(n)
    assert sumaDigitos2(n) == r
    assert sumaDigitos3(n) == r
    assert sumaDigitos4(n) == r
    assert sumaDigitos5(n) == r
 
# La comprobación es
#    src> poetry run pytest -q suma_de_los_digitos_de_un_numero.py
#    1 passed in 0.35s
 
# 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('sumaDigitos1(factorial(6*10**3))')
#    0.01 segundos
#    >>> tiempo('sumaDigitos2(factorial(6*10**3))')
#    0.01 segundos
#    >>> tiempo('sumaDigitos3(factorial(6*10**3))')
#    0.13 segundos
#    >>> tiempo('sumaDigitos4(factorial(6*10**3))')
#    0.13 segundos
#    >>> tiempo('sumaDigitos5(factorial(6*10**3))')
#    0.01 segundos
#
#    >>> tiempo('sumaDigitos1(factorial(10**5))')
#    2.20 segundos
#    >>> tiempo('sumaDigitos2(factorial(10**5))')
#    2.22 segundos
#    >>> tiempo('sumaDigitos5(factorial(10**5))')
#    2.19 segundos

El código se encuentra en GitHub

Leer más →

Dígitos de un número

José A. Alonso, ,

Definir la función

   digitos :: Integer -> [Int]

tal que digitos n es la lista de los dígitos del número n. Por ejemplo,

   digitos 320274  ==  [3,2,0,2,7,4]

Soluciones

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


Soluciones en Haskell

import Data.Char (digitToInt)
import qualified Data.Digits as D (digits)
import qualified Data.FastDigits as FD (digits)
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
digitos1 :: Integer -> [Int]
digitos1 n = map fromInteger (aux n)
  where aux :: Integer -> [Integer]
        aux m
          | m < 10    = [m]
          | otherwise = aux (m `div` 10) ++ [m `rem` 10]
 
-- 2ª solución
-- ===========
 
digitos2 :: Integer -> [Int]
digitos2 n = map fromInteger (reverse (aux n))
  where aux :: Integer -> [Integer]
        aux m
          | m < 10    = [m]
          | otherwise = (m `rem` 10) : aux (m `div` 10)
 
-- 3ª solución
-- ===========
 
digitos3 :: Integer -> [Int]
digitos3 n = map fromInteger (aux [] n)
  where aux :: [Integer] -> Integer -> [Integer]
        aux ds m
          | m < 10    = m : ds
          | otherwise = aux (m `rem` 10 : ds) (m `div` 10)
 
-- 4ª solución
-- ===========
 
digitos4 :: Integer -> [Int]
digitos4 n = [read [x] | x <- show n]
 
-- 5ª solución
-- ===========
 
digitos5 :: Integer -> [Int]
digitos5 n = map (\ x -> read [x]) (show n)
 
-- 6ª solución
-- ===========
 
digitos6 :: Integer -> [Int]
digitos6 = map (read . return) . show
 
-- 7ª solución
-- ===========
 
digitos7 :: Integer -> [Int]
digitos7 n = map digitToInt (show n)
 
-- 8ª solución
-- ===========
 
digitos8 :: Integer -> [Int]
digitos8 = map digitToInt . show
 
-- 9ª solución
-- ===========
 
digitos9 :: Integer -> [Int]
digitos9 0 = [0]
digitos9 n = map fromInteger (D.digits 10 n)
 
-- 10ª solución
-- ===========
 
digitos10 :: Integer -> [Int]
digitos10 0 = [0]
digitos10 n = reverse (FD.digits 10 n)
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_digitos :: NonNegative Integer -> Bool
prop_digitos (NonNegative n) =
  all (== digitos1 n)
      [digitos2 n,
       digitos3 n,
       digitos4 n,
       digitos5 n,
       digitos6 n,
       digitos7 n,
       digitos8 n,
       digitos9 n,
       digitos10 n]
 
-- La comprobación es
--    λ> quickCheck prop_digitos
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> n = product [1..5000]
--    λ> length (digitos1 n)
--    16326
--    (3.00 secs, 11,701,450,912 bytes)
--    λ> length (digitos2 n)
--    16326
--    (0.13 secs, 83,393,816 bytes)
--    λ> length (digitos3 n)
--    16326
--    (0.11 secs, 83,132,552 bytes)
--    λ> length (digitos4 n)
--    16326
--    (0.01 secs, 23,054,920 bytes)
--    λ> length (digitos5 n)
--    16326
--    (0.01 secs, 22,663,088 bytes)
--    λ> length (digitos6 n)
--    16326
--    (0.06 secs, 22,663,224 bytes)
--    λ> length (digitos7 n)
--    16326
--    (0.01 secs, 22,663,064 bytes)
--    λ> length (digitos8 n)
--    16326
--    (0.03 secs, 22,663,192 bytes)
--    λ> length (digitos9 n)
--    16326
--    (0.05 secs, 82,609,944 bytes)
--    λ> length (digitos10 n)
--    16326
--    (0.01 secs, 26,295,416 bytes)
--
--    λ> n = product [1..5*10^4]
--    λ> length (digitos2 n)
--    213237
--    (10.17 secs, 12,143,633,056 bytes)
--    λ> length (digitos3 n)
--    213237
--    (10.54 secs, 12,140,221,216 bytes)
--    λ> length (digitos4 n)
--    213237
--    (1.29 secs, 2,638,199,328 bytes)
--    λ> length (digitos5 n)
--    213237
--    (2.48 secs, 2,633,081,632 bytes)
--    λ> length (digitos6 n)
--    213237
--    (2.59 secs, 2,633,081,600 bytes)
--    λ> length (digitos7 n)
--    213237
--    (2.55 secs, 2,633,081,608 bytes)
--    λ> length (digitos8 n)
--    213237
--    (2.49 secs, 2,633,081,600 bytes)
--    λ> length (digitos9 n)
--    213237
--    (7.07 secs, 12,133,397,456 bytes)
--    λ> length (digitos10 n)
--    213237
--    (2.47 secs, 2,725,182,064 bytes)

El código se encuentra en GitHub.


Soluciones en Python

from math import factorial
from sys import setrecursionlimit
from timeit import Timer, default_timer
 
from hypothesis import given
from hypothesis import strategies as st
from sympy.ntheory.digits import digits
 
setrecursionlimit(10**6)
 
# 1ª solución
# ===========
 
def digitos1(n: int) -> list[int]:
    if n < 10:
        return [n]
    return digitos1(n // 10) + [n % 10]
 
# 2ª solución
# ===========
 
def digitos2(n: int) -> list[int]:
    return [int(x) for x in str(n)]
 
# 3ª solución
# ===========
 
def digitos3(n: int) -> list[int]:
    r: list[int] = []
    for x in str(n):
        r.append(int(x))
    return r
 
# 4ª solución
# ===========
 
def digitos4(n: int) -> list[int]:
    return list(map(int, list(str(n))))
 
# 5ª solución
# ===========
 
def digitos5(n: int) -> list[int]:
    r: list[int] = []
    while n > 0:
        r = [n % 10] + r
        n = n // 10
    return r
 
# 6ª solución
# ===========
 
def digitos6(n: int) -> list[int]:
    r: list[int] = []
    while n > 0:
        r.append(n % 10)
        n = n // 10
    return list(reversed(r))
 
# 7ª solución
# ===========
 
def digitos7(n: int) -> list[int]:
    return digits(n)[1:]
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(st.integers(min_value=1))
def test_digitos(n: int) -> None:
    r = digitos1(n)
    assert digitos2(n) == r
    assert digitos3(n) == r
    assert digitos4(n) == r
    assert digitos5(n) == r
    assert digitos6(n) == r
    assert digitos7(n) == r
 
# La comprobación es
#    src> poetry run pytest -q digitos_de_un_numero.py
#    1 passed in 0.49s
 
# Comparación de eficiencia
# =========================
 
def tiempo(ex: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(ex, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")
 
# La comparación es
#    >>> tiempo('digitos1(factorial(6000))')
#    0.58 segundos
#    >>> tiempo('digitos2(factorial(6000))')
#    0.01 segundos
#    >>> tiempo('digitos3(factorial(6000))')
#    0.01 segundos
#    >>> tiempo('digitos4(factorial(6000))')
#    0.01 segundos
#    >>> tiempo('digitos5(factorial(6000))')
#    0.60 segundos
#    >>> tiempo('digitos6(factorial(6000))')
#    0.17 segundos
#    >>> tiempo('digitos7(factorial(6000))')
#    0.10 segundos
#
#    >>> tiempo('digitos2(factorial(2*10**4))')
#    0.10 segundos
#    >>> tiempo('digitos3(factorial(2*10**4))')
#    0.10 segundos
#    >>> tiempo('digitos4(factorial(2*10**4))')
#    0.09 segundos
#    >>> tiempo('digitos6(factorial(2*10**4))')
#    2.33 segundos
#    >>> tiempo('digitos7(factorial(2*10**4))')
#    1.18 segundos
#
#    >>> tiempo('digitos2(factorial(10**5))')
#    3.53 segundos
#    >>> tiempo('digitos3(factorial(10**5))')
#    3.22 segundos
#    >>> tiempo('digitos4(factorial(10**5))')
#    3.02 segundos

El código se encuentra en GitHub.

Leer más →

Algoritmo de Euclides del mcd

José A. Alonso, ,

Dados dos números naturales, a y b, es posible calcular su máximo común divisor mediante el Algoritmo de Euclides. Este algoritmo se puede resumir en la siguiente fórmula:

   mcd(a,b) = a,                   si b = 0
            = mcd (b, a módulo b), si b > 0

Definir la función

   mcd :: Integer -> Integer -> Integer

tal que mcd a b es el máximo común divisor de a y b calculado mediante el algoritmo de Euclides. Por ejemplo,

   mcd 30 45  ==  15
   mcd 45 30  ==  15

Comprobar con QuickCheck que el máximo común divisor de dos números a y b (ambos mayores que 0) es siempre mayor o igual que 1 y además es menor o igual que el menor de los números a y b.

Soluciones

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


Soluciones en Haskell

import Test.QuickCheck
 
mcd :: Integer -> Integer -> Integer
mcd a 0 = a
mcd a b = mcd b (a `mod` b)
 
-- La propiedad es
prop_mcd :: Positive Integer -> Positive Integer -> Bool
prop_mcd (Positive a) (Positive b) =
  m >= 1 && m <= min a b
  where m = mcd a b
 
-- La comprobación es
--    λ> quickCheck prop_mcd
--    OK, passed 100 tests.

El código se encuentra en GitHub.


Soluciones en Python

from hypothesis import given
from hypothesis import strategies as st
 
def mcd(a: int, b: int) -> int:
    if b == 0:
        return a
    return mcd(b, a % b)
 
# -- La propiedad es
@given(st.integers(min_value=1, max_value=1000),
       st.integers(min_value=1, max_value=1000))
def test_mcd(a: int, b: int) -> None:
    assert 1 <= mcd(a, b) <= min(a, b)
 
# La comprobación es
#    src> poetry run pytest -q algoritmo_de_Euclides_del_mcd.py
#    1 passed in 0.22s

El código se encuentra en GitHub.

Leer más →

Potencia entera

José A. Alonso, ,

Definir la función

   potencia :: Integer -> Integer -> Integer

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

   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)

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

El código se encuentra en GitHub.

Leer más →