Menu Close

Suma con redondeos

Definir las funciones

   sumaRedondeos       :: Integer -> [Integer]
   limiteSumaRedondeos :: Integer -> Integer

tales que

  • (sumaRedondeos n) es la sucesión cuyo k-ésimo término es
     redondeo (n/2) + redondeo (n/4) + ... + redondeo (n/2^k)

Por ejemplo,

     take 5 (sumaRedondeos 1000)  ==  [500,750,875,937,968]
  • (limiteSumaRedondeos n) es la suma de la serie
     redondeo (n/2) + redondeo (n/4) + redondeo (n/8) + ...

Por ejemplo,

     limiteSumaRedondeos 2000                    ==  1999
     limiteSumaRedondeos 2016                    ==  2016
     limiteSumaRedondeos (10^308) `mod` (10^10)  ==  123839487

Soluciones

-- 1ª definición
-- =============
 
sumaRedondeos1 :: Integer -> [Integer]
sumaRedondeos1 n =
    [sum [round (n'/(fromIntegral (2^k))) | k <- [1..m]] | m <- [1..]]
    where n' = fromIntegral n
 
limiteSumaRedondeos1 :: Integer -> Integer
limiteSumaRedondeos1 = limite . sumaRedondeos1
 
limite :: [Integer] -> Integer
limite xs = head [x | (x,y) <- zip xs (tail xs), x == y]
 
-- 2ª definición
sumaRedondeos2 :: Integer -> [Integer]
sumaRedondeos2 n =
    scanl1 (+) [round (n'/(fromIntegral (2^k))) | k <- [1..]]
    where n' = fromIntegral n
 
limiteSumaRedondeos2 :: Integer -> Integer
limiteSumaRedondeos2 = limite . sumaRedondeos2
 
-- 3ª definición
sumaRedondeos3 :: Integer -> [Integer]
sumaRedondeos3 n = map fst (iterate f (round (n'/2),4))
    where f (s,d) = (s + round (n'/(fromIntegral d)), 2*d)
          n'      = fromIntegral n
 
limiteSumaRedondeos3 :: Integer -> Integer
limiteSumaRedondeos3 = limite . sumaRedondeos3
 
-- 4ª definición
sumaRedondeos4 :: Integer -> [Integer]
sumaRedondeos4 n = xs ++ repeat x
    where n' = fromIntegral n
          m  = round (logBase 2 n')
          xs = scanl1 (+) [round (n'/(fromIntegral (2^k))) | k <- [1..m]]
          x  = last xs
 
limiteSumaRedondeos4 :: Integer -> Integer
limiteSumaRedondeos4 = limite . sumaRedondeos4
 
-- Comparación de eficiencia
--    λ> (sumaRedondeos1 4) !! 20000
--    3
--    (0.92 secs, 197,782,232 bytes)
--    λ> (sumaRedondeos1 4) !! 30000
--    3
--    (2.20 secs, 351,084,816 bytes)
--    λ> (sumaRedondeos3 4) !! 20000
--    3
--    (0.30 secs, 53,472,392 bytes)
--    λ> (sumaRedondeos4 4) !! 20000
--    3
--    (0.01 secs, 0 bytes)
 
-- En lo que sigue, usaremos la 3ª definición
sumaRedondeos :: Integer -> [Integer]
sumaRedondeos = sumaRedondeos3
 
-- 5ª definición
-- =============
 
limiteSumaRedondeos5 :: Integer -> Integer
limiteSumaRedondeos5 n = 
    sum [round (n'/(fromIntegral (2^k))) | k <- [1..m]]
    where n' = fromIntegral n
          m  = round (logBase 2 n')

3 soluciones de “Suma con redondeos

  1. carruirui3
    sumaRedondeos :: Integer -> [Integer]
    sumaRedondeos n = map (sum . sumandos n) [1..]
     
    -- sumandos n k devuelve los k primeros elementos de la sucesión 
    -- x_k = round(n/2^k) 
    sumandos :: Integer -> Integer -> [Integer]
    sumandos n k = map (sumando n) [1..k]
     
    sumando :: Integer -> Integer -> Integer
    sumando n = round . (fromIntegral n/) . (2^^)
     
    limiteSumaRedondeos :: Integer -> Integer
    limiteSumaRedondeos n = 
        fst . head . dropWhile ((_,k) -> sumando n k > 0) $
        zip (sumaRedondeos n) [1..]
    • josejuan

      En mi opinión, no es correcto realizar el redondeo convirtiendo a Double el resultado de la división ya que se produce pérdida de datos (dando el resultado esperado que yo creo es incorrecto).

      Por otro lado, redondear un valor decimal puede realizarse de varias formas, ya que (por ejemplo) la fracción 3/2 está a la misma distancia de 1 que de 2, luego aquí habría ambigüedad.

      En todo caso, la identidad 10^k == 2 * sumando (10^k) 1 debe cumplirse para todo k>0 (y no se cumple con la solución indicada).

      Aporto la función solicitada para cualquier función de redondeo e indicando dos funciones de redondeo diferentes, una usando truncamiento de bits y otra usando Data.Real.Constructibles.

      import Data.Real.Constructible
      import Data.Bits
       
      -- ROUND (3 / 2) = 3
      redondear1 :: ℤ → Int → ℤ
      redondear1 n k = (n + (1 `shiftL` (k - 1))) `shiftR` k
       
      -- ROUND (3 / 2) = 2
      redondear2 :: ℤ → Int → ℤ
      redondear2 n k = round (fromIntegral n / 2:: Construct)
       
      terminos :: (ℤ → Int → ℤ) → ℤ → []
      terminos redondear n = takeWhile (0) (redondear n ↥ [1])
       
      sumaRedondeos :: (ℤ → Int → ℤ) → ℤ → []
      sumaRedondeos redondear = scanl1 (+)(repeat 0) ∘ terminos redondear
       
      limiteSumaRedondeos :: (ℤ → Int → ℤ) → ℤ → ℤ
      limiteSumaRedondeos redondear = ∑ ∘ terminos redondear
  2. fracruzam
    sumaRedondeos :: Integer -> [Integer]
    sumaRedondeos n = scanl1 (+) [round (fromIntegral n /(2^k)) | k <- [1..]]
     
    -- Usando el hecho de que, a partir de un cierto k, n / (2^k) <= 0.5, lo que
    -- implica que el redondeo de dicha expresión es 0 para todos los
    -- términos a partir de dicho k, obteniendo la función sumaRedondeos un
    -- valor constante.
     
    limiteSumaRedondeos :: Integer -> Integer
    limiteSumaRedondeos n = aux (sumaRedondeos n)
      where aux :: [Integer] -> Integer
            aux (x:y:xs) | x == y    = x
                         | otherwise = aux xs

Escribe tu solución

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