Menu Close

Reconocimiento de potencias de 4

José A. Alonso,

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.

Posted in Ejercicio
Tagged , , , ,

2 Comments

  1. j0sejuan
    Responder 
    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
    Responder 
    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.