{"id":2946,"date":"2017-02-16T06:00:10","date_gmt":"2017-02-16T04:00:10","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=2946"},"modified":"2021-04-25T16:14:33","modified_gmt":"2021-04-25T14:14:33","slug":"distribucion-de-digitos-de-pi-2017","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/distribucion-de-digitos-de-pi-2017\/","title":{"rendered":"Distribuci\u00f3n de d\u00edgitos de pi"},"content":{"rendered":"<p>Se pueden generar los d\u00edgitos de Pi, como se explica en el art\u00edculo <a href=\"http:\/\/bit.ly\/2kn0Kh2\">Unbounded spigot algorithms for the digits of pi<\/a>, con la funci\u00f3n digitosPi definida por<\/p>\n<pre lang=\"text\">\n   digitosPi :: [Integer]\n   digitosPi = g(1,0,1,1,3,3) where\n     g (q,r,t,k,n,l) = \n       if 4*q+r-t < n*t\n       then n : g (10*q, 10*(r-n*t), t, k, div (10*(3*q+r)) t - 10*n, l)\n       else g (q*k, (2*q+r)*l, t*l, k+1, div (q*(7*k+2)+r*l) (t*l), l+2)\n<\/pre>\n<p>Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> take 25 digitosPi\n   [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]\n<\/pre>\n<p>La distribuci\u00f3n de los primeros 25 d\u00edgitos 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, ...<\/p>\n<p>Usando digitosPi, definir las siguientes funciones<\/p>\n<pre lang=\"text\">\n   distribucionDigitosPi :: Int -> [Int]\n   frecuenciaDigitosPi   :: Int -> [Double]\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(distribucionDigitosPi n) es la distribuci\u00f3n de los n primeros d\u00edgitos de pi. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> distribucionDigitosPi 10\n     [0,2,1,2,1,2,1,0,0,1]\n     \u03bb> distribucionDigitosPi 100\n     [8,8,12,12,10,8,9,8,12,13]\n     \u03bb> distribucionDigitosPi 1000\n     [93,116,103,103,93,97,94,95,101,105]\n     \u03bb> distribucionDigitosPi 5000\n     [466,531,496,460,508,525,513,488,492,521]\n<\/pre>\n<ul>\n<li>(frecuenciaDigitosPi n) es la frecuencia de los n primeros d\u00edgitos de pi. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n   \u03bb> frecuenciaDigitosPi 10\n   [0.0,20.0,10.0,20.0,10.0,20.0,10.0,0.0,0.0,10.0]\n   \u03bb> frecuenciaDigitosPi 100\n   [8.0,8.0,12.0,12.0,10.0,8.0,9.0,8.0,12.0,13.0]\n   \u03bb> frecuenciaDigitosPi 1000\n   [9.3,11.6,10.3,10.3,9.3,9.7,9.4,9.5,10.1,10.5]\n   \u03bb> frecuenciaDigitosPi 5000\n   [9.32,10.62,9.92,9.2,10.16,10.5,10.26,9.76,9.84,10.42]\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Array\nimport Data.List (group, sort)\n\ndigitosPi :: [Integer]\ndigitosPi = g(1,0,1,1,3,3) where\n  g (q,r,t,k,n,l) = \n    if 4*q+r-t < n*t\n    then n : g (10*q, 10*(r-n*t), t, k, div (10*(3*q+r)) t - 10*n, l)\n    else g (q*k, (2*q+r)*l, t*l, k+1, div (q*(7*k+2)+r*l) (t*l), l+2)\n\n-- 1\u00aa definici\u00f3n\n-- =============\n\ndistribucionDigitosPi :: Int -> [Int]\ndistribucionDigitosPi n =\n    elems (accumArray (+) 0 (0,9) [(i,1)\n                                  | i <- take n digitosPi]) \n\nfrecuenciaDigitosPi :: Int -> [Double]\nfrecuenciaDigitosPi n =\n  [100 * (fromIntegral x \/ m) | x <- distribucionDigitosPi n]\n  where m = fromIntegral n\n\n-- 2\u00aa definici\u00f3n\n-- =============\n\ndistribucionDigitosPi2 :: Int -> [Int]\ndistribucionDigitosPi2 n =\n  [length xs - 1 | xs <- group (sort (take n digitosPi ++ [0..9]))]\n\nfrecuenciaDigitosPi2 :: Int -> [Double]\nfrecuenciaDigitosPi2 n =\n  [100 * (fromIntegral x \/ m) | x <- distribucionDigitosPi2 n]\n  where m = fromIntegral n\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> last (take 5000 digitosPi)\n--    2\n--    (4.47 secs, 3,927,848,448 bytes)\n--    \u03bb> frecuenciaDigitosPi 5000\n--    [9.32,10.62,9.92,9.2,10.16,10.5,10.26,9.76,9.84,10.42]\n--    (0.01 secs, 0 bytes)\n--    \u03bb> frecuenciaDigitosPi2 5000\n--    [9.32,10.62,9.92,9.2,10.16,10.5,10.26,9.76,9.84,10.42]\n--    (0.02 secs, 0 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Se pueden generar los d\u00edgitos de Pi, como se explica en el art\u00edculo Unbounded spigot algorithms for the digits of pi, con la funci\u00f3n digitosPi definida por 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)...\n<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[4],"tags":[249,8,245,368,183,13,28,42,184,14,47],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2946"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=2946"}],"version-history":[{"count":8,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2946\/revisions"}],"predecessor-version":[{"id":3007,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2946\/revisions\/3007"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=2946"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=2946"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=2946"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}