Menu Close

Reconocimiento de potencias de 4

Definir la función

   esPotenciaDe4 :: Integral a => a -> Bool

tal que (esPotenciaDe4 n) se verifica si n es una potencia de 4. Por ejemplo,

   esPotenciaDe4 16                ==  True
   esPotenciaDe4 17                ==  False
   esPotenciaDe4 (4^(4*10^5))      ==  True
   esPotenciaDe4 (1 + 4^(4*10^5))  ==  False

Soluciones

-- 1ª solución
-- ===========
 
esPotenciaDe4_1 :: Integral a => a -> Bool
esPotenciaDe4_1 0 = False
esPotenciaDe4_1 1 = True
esPotenciaDe4_1 n = n `mod` 4 == 0 && esPotenciaDe4_1 (n `div` 4)
 
-- 2ª solución
-- ===========
 
esPotenciaDe4_2 :: Integral a => a -> Bool
esPotenciaDe4_2 n = n `pertenece` potenciasDe4
 
-- potenciassDe4 es la lista de las potencias de 4. Por ejemplo,
--    take 5 potenciasDe4  ==  [1,4,16,64,256]
potenciasDe4 :: Integral a => [a]
potenciasDe4 = [4^x | x <- [0..]]
 
-- (pertenece x ys) se verifica si x pertenece a la lista ordenada
-- (posiblemente infinita xs). Por ejemplo,
--    pertenece 8 [2,4..]  ==  True
--    pertenece 9 [2,4..]  ==  False
pertenece :: Integral a => a -> [a] -> Bool
pertenece x ys = x == head (dropWhile (<x) ys)
 
-- 3ª solución
-- ===========
 
esPotenciaDe4_3 :: Integral a => a -> Bool
esPotenciaDe4_3 n = n `pertenece` potenciasDe4_2
 
-- potenciassDe4 es la lista de las potencias de 4. Por ejemplo,
--    take 5 potenciasDe4  ==  [1,4,16,64,256]
potenciasDe4_2 :: Integral a => [a]
potenciasDe4_2 = iterate (*4) 1
 
-- 4ª solución
-- ===========
 
esPotenciaDe4_4 :: Integral n => n -> Bool
esPotenciaDe4_4 n =
  n == head (dropWhile (<n) (iterate (*4) 1))
 
-- 5ª solución
-- ===========
 
esPotenciaDe4_5 :: Integral n => n -> Bool
esPotenciaDe4_5 n =
  n == until (>=n) (*4) 1
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> esPotenciaDe4_1 (4^(4*10^4))
--    True
--    (0.18 secs, 233,903,248 bytes)
--    λ> esPotenciaDe4_2 (4^(4*10^4))
--    True
--    (2.01 secs, 756,125,712 bytes)
--    λ> esPotenciaDe4_3 (4^(4*10^4))
--    True
--    (0.05 secs, 212,019,464 bytes)
--    λ> esPotenciaDe4_4 (4^(4*10^4))
--    True
--    (0.05 secs, 212,019,368 bytes)
--    λ> esPotenciaDe4_5 (4^(4*10^4))
--    True
--    (0.07 secs, 209,779,888 bytes)
--
--    λ> esPotenciaDe4_3 (4^(2*10^5))
--    True
--    (0.64 secs, 5,184,667,280 bytes)
--    λ> esPotenciaDe4_4 (4^(2*10^5))
--    True
--    (0.64 secs, 5,184,667,200 bytes)
--    λ> esPotenciaDe4_5 (4^(2*10^5))
--    True
--    (0.63 secs, 5,173,467,656 bytes)
--
--    λ> esPotenciaDe4_3 (4^(4*10^5))
--    True
--    (2.27 secs, 20,681,727,464 bytes)
--    λ> esPotenciaDe4_4 (4^(4*10^5))
--    True
--    (2.30 secs, 20,681,727,320 bytes)
--    λ> esPotenciaDe4_5 (4^(4*10^5))
--    True
--    (2.28 secs, 20,659,327,352 bytes)

El código se encuentra en GitHub.

Ejercicio

2 soluciones de “Reconocimiento de potencias de 4

  1. j0sejuan
    import Data.List (genericLength)
    import Data.Maybe
     
    -- construimos sobre Maybe la búsqueda de un resto
    -- al dividir sobre cierto valor
    resto :: Integral a => a -> a -> Maybe a
    resto p n = case n `divMod` p of
                  (1, 0) -> Nothing
                  (m, 0) -> resto p m
                  (_, r) -> Just r
     
    -- entonces es potencia si no hay resto
    esPotenciaDe4 = isNothing . resto 4
     
    -- podemos entonces aumentar exponencialmente la convergencia
    -- sin analizar `n` sólo usando potencias exp + grandes
    esPotenciaDe4' n = isNothing $ resto (4^1000) n
                               >>= resto (4^100)
                               >>= resto (4^10)
                               >>= resto 4
     
    -- o podemos estimar a partir de 10^p = 4^q => q >= n log 10 / log 4
    esPotenciaDe4'' = isNothing . es
      where es n = case genericLength (show n) of
                    1 -> resto 4 n
                    q -> resto (4^q) n >>= es
     
    {-
     
    -- comparación eficiencia de ingenua con cotas fijas
     
    *Main> esPotenciaDe4 (4^(4*10^5))
    True
    (9.33 secs, 20,283,679,752 bytes)
    *Main> esPotenciaDe4' (4^(4*10^5))
    True
     
     
    -- comparación eficiencia cotas fijas con logaritmos
    *Main> esPotenciaDe4' (4^(4*10^6))
    True
    (7.20 secs, 2,006,429,520 bytes)
    *Main> esPotenciaDe4'' (4^(4*10^6))
    True
    (1.50 secs, 740,838,288 bytes)
     
    -}
  2. Adán Bonilla
    esPotenciaDe4 :: Integral n => n -> Bool
    esPotenciaDe4 n = n == until (>=n) (*4) 1

Escribe tu solución

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