Suma con redondeos
Definir las funciones
1 2 |
sumaRedondeos :: Integer -> [Integer] limiteSumaRedondeos :: Integer -> Integer |
tales que
- (sumaRedondeos n) es la sucesión cuyo k-ésimo término es
1 |
redondeo (n/2) + redondeo (n/4) + ... + redondeo (n/2^k) |
Por ejemplo,
1 |
take 5 (sumaRedondeos 1000) == [500,750,875,937,968] |
- (limiteSumaRedondeos n) es la suma de la serie
1 |
redondeo (n/2) + redondeo (n/4) + redondeo (n/8) + ... |
Por ejemplo,
1 2 3 |
limiteSumaRedondeos 2000 == 1999 limiteSumaRedondeos 2016 == 2016 limiteSumaRedondeos (10^308) `mod` (10^10) == 123839487 |
Soluciones
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
-- 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') |
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
.