Cálculo de dígitos de pi y su distribución
Se pueden generar los dígitos de Pi, como se explica en el artículo Unbounded spigot algorithms for the digits of pi c0on la función digitosPi definida por
|
1 2 3 4 5 6 |
digitosPi :: [Integer] digitosPi = g(1,0,1,1,3,3) where g (q,r,t,k,n,l) = if 4*q+r-t < n*t then n : g (10*q, 10*(r-n*t), t, k, div (10*(3*q+r)) t - 10*n, l) else g (q*k, (2*q+r)*l, t*l, k+1, div (q*(7*k+2)+r*l) (t*l), l+2) |
Por ejemplo,
|
1 2 |
λ> take 25 digitosPi [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4,3] |
La distribución de los primeros 25 dígitos de pi es [0,2,3,5,3,3,3,1,2,3] ya que el 0 no aparece, el 1 ocurre 2 veces, el 3 ocurre 3 veces, el 4 ocurre 5 veces, …
Usando digitosPi, definir las siguientes funciones
|
1 2 |
distribucionDigitosPi :: Int -> [Int] frecuenciaDigitosPi :: Int -> [Double] |
tales que
- (distribucionDigitosPi n) es la distribución de los n primeros dígitos de pi. Por ejemplo,
|
1 2 3 4 5 6 7 8 |
λ> distribucionDigitosPi 10 [0,2,1,2,1,2,1,0,0,1] λ> distribucionDigitosPi 100 [8,8,12,12,10,8,9,8,12,13] λ> distribucionDigitosPi 1000 [93,116,103,103,93,97,94,95,101,105] λ> distribucionDigitosPi 5000 [466,531,496,460,508,525,513,488,492,521] |
- (frecuenciaDigitosPi n) es la frecuencia de los n primeros dígitos de pi. Por ejemplo,
|
1 2 3 4 5 6 7 8 |
λ> frecuenciaDigitosPi 10 [0.0,20.0,10.0,20.0,10.0,20.0,10.0,0.0,0.0,10.0] λ> frecuenciaDigitosPi 100 [8.0,8.0,12.0,12.0,10.0,8.0,9.0,8.0,12.0,13.0] λ> frecuenciaDigitosPi 1000 [9.3,11.6,10.3,10.3,9.3,9.7,9.4,9.5,10.1,10.5] λ> frecuenciaDigitosPi 5000 [9.32,10.62,9.92,9.2,10.16,10.5,10.26,9.76,9.84,10.42] |
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 |
import Data.Array import Data.List (group, sort) digitosPi :: [Integer] digitosPi = g(1,0,1,1,3,3) where g (q,r,t,k,n,l) = if 4*q+r-t < n*t then n : g (10*q, 10*(r-n*t), t, k, div (10*(3*q+r)) t - 10*n, l) else g (q*k, (2*q+r)*l, t*l, k+1, div (q*(7*k+2)+r*l) (t*l), l+2) -- 1ª definición -- ============= distribucionDigitosPi :: Int -> [Int] distribucionDigitosPi n = elems (accumArray (+) 0 (0,9) [ (i,1) | i <- take n digitosPi]) frecuenciaDigitosPi :: Int -> [Double] frecuenciaDigitosPi n = [100 * (fromIntegral x / m) | x <- distribucionDigitosPi n] where m = fromIntegral n -- 2ª definición -- ============= distribucionDigitosPi2 :: Int -> [Int] distribucionDigitosPi2 n = [length xs - 1 | xs <- group (sort (take n digitosPi ++ [0..9]))] frecuenciaDigitosPi2 :: Int -> [Double] frecuenciaDigitosPi2 n = [100 * (fromIntegral x / m) | x <- distribucionDigitosPi2 n] where m = fromIntegral n -- Comparación de eficiencia -- ========================= -- λ> last (take 5000 digitosPi) -- 2 -- (4.47 secs, 3,927,848,448 bytes) -- λ> frecuenciaDigitosPi 5000 -- [9.32,10.62,9.92,9.2,10.16,10.5,10.26,9.76,9.84,10.42] -- (0.01 secs, 0 bytes) -- λ> frecuenciaDigitosPi2 5000 -- [9.32,10.62,9.92,9.2,10.16,10.5,10.26,9.76,9.84,10.42] -- (0.02 secs, 0 bytes) |
Otras soluciones
- Se pueden escribir otras soluciones en los comentarios.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>