sexta-feira, 8 de maio de 2015

[P9] Alguns dígitos de PI

     O número PI é a relação entre o perímetro de uma circunferência e o seu diâmetro e é bastante estudada em geral. O principal interesse aqui é sobre a obtenção numérica dos dígitos de PI, buscas e aspectos interessantes de serem realizadas. O Dia de PI é 14 de Março, pois em inglês escreve-se 3/14, equivalendo aos primeiros dígitos de PI.
     Para decorar PI, em inglês, basta decorar a seguinte frase e daí contar o tamanho de cada palavra:
May I have a large container of coffee beans
3 1 4 1 5 9 2 6 5

     Como curiosidade, é possível usar a letra grega em HTML para representar PI, por exemplo, π (para maiores informações, consulte o este site).

     A tabela a seguir mostra onde foram obtidos os arquivos dos dígitos de PI:
Tamanho (em dígitos) Local (site)
100.000 http://www.geom.uiuc.edu/~huberty/math5337/groupe/digits.html
10.000.000 http://pi.karmona.com/
100.000.000 https://ia801404.us.archive.org/4/items/Pi_to_100000000_places/pi.txt
Para os cem milhoes, o seguinte foi fornecido:
QPI-Quick Pi v2.90, (c) 2000-2004 S. Pagliarulo
Freely distributable, email: s_pagliarulo@hotmail.com

Intel(R) Pentium(R) 4 CPU 2.53GHz detected
System speed measured at 2.5 GHz
Using custom training data

Computation of Pi to 100,000,000 digits
Method used : Chudnovsky
Started : Fri Dec 16 16:06:49 2005

Series size : 7051368  (100,000,015 digits)
Initialization time : 0.06
Series processing time : 1002.95
Final value time : 225.98

Total time : 1229.00 seconds (20 mins, 29.00 secs)
Total memory used : 639,608,980 (609.98 MB)
CPU utilization : 99.97%

     Mas qual a chance de encontrar números nos dígitos de PI? O site http://www.angio.net/pi/whynotpi.html tenta responder esta pergunta, conforme a seguinte tabela a seguir (as chances foram computadas para 100 milhões de dígitos):

Tamanho do número Chance de encontrar
1-5 100%
6 Quase 100%
7 99,995%
8 63%
9 9,5%
10 0,995%%
11 0,09995%

Computando PI em C


     Existem três métodos (baseado em http://www.codeproject.com/Articles/813185/Calculating-the-Number-PI-Through-Infinite-Sequenc):

1. Wallis's Series (1655) - Double Precision

2. Gregory-Leibniz's Series (1671-1674) - Double Precision

3. Nilakantha's Series (Século XV) - Double Precision


     Um outro método chamado Método de Chudnovsky computa dígitos para PI de forma rápida:

4. Chudnovsky's Method (1989)


     O problema deste método é que é necessário trabalhar com bibliotecas BigInt, ou seja, com grandes inteiros, pois acima de 27, o fatorial começa a ficar muito complicado de ser calculado (como desafio, programe este algoritmo e tente passar de 27).



1. Wallis's Series - Double Precision
// Approximation of the number pi through the Wallis's series
// Language: C
// Author: Jose Cintra (jose.cintra@html-apps.info)

#include <stdio.h>
#include <stdlib.h>

main() {

   double n, i         // Number of iterations and control variable
   double pi = 4;

   printf("Approximation of the number pi through the Wallis's series\n");
   printf("\nEnter the number of iterations: ");    
   scanf("%lf",&n);
   printf("\nPlease wait. Running...\n");

   for(i = 3; i <= (n + 2); i+=2)
      pi = pi * ((i - 1) / i) * (( i + 1) / i);

   printf("\nAproximated value of PI = %1.16lf\n", pi);  

}

2. Gregory-Leibniz's Series - Double Precision
// Approximation of the number PI through the Leibniz's series
// Language: C
// Author: Jose Cintra (jose.cintra@html-apps.info)

#include <stdio.h>
#include <stdlib.h>

main() {

   double n, i;       // Number of iterations and control variable
   double s = 1;      //Signal for the next iteration
   double pi = 0;

   printf("Approximation of the number PI through the Leibniz's series\n");
   printf("\nEnter the number of iterations: ");    
   scanf("%lf",&n);
   printf("\nPlease wait. Running...\n");      

   for(i = 1; i <= (n * 2); i += 2) {
     pi = pi + s * (4 / i);
     s = -s;
   }

   printf("\nAproximated value of PI = %1.16lf\n", pi);  

}

3. Nilakantha's Series - Double Precision
// Approximation of the number pi through the Nilakantha's series
// Language: C
// Author: Jose Cintra (jose.cintra@html-apps.info)

#include <stdio.h>
#include <stdlib.h>

main() {
   double n, i;    // Number of iterations and control variable
   double s = 1;   //Signal for the next operation
   double pi = 3;

   printf("Approximation of the number PI through the sequence of the Nilakantha's series\n");
   printf("\nEnter the number of iterations: ");
   scanf("%lf",&n);
   printf("\nPlease wait. Running...\n");

   for(i = 2; i <= n*2; i += 2) {
     pi = pi + s * (4 / (i * (i + 1) * (i + 2)));
     s = -s;
   }
   printf("\nAproximated value of PI = %1.16lf\n", pi);
}

Dados

     Existem quatro arquivos para baixar:
  1. a1-cem-mil-digitos-de-PI.txt: como o nome diz, possui cem mil dígitos de PI, em 98Kb de tamanho em disco.
  2. a2-dez-milhoes-digitos-de-PI.txt: este arquivo contém dez milhões de dígitos de PI, com aproximadamente 9,8Mb de tamanho.
  3. a3-cem-milhoes-digitos-de-PI.txt: finalmente, cem milhões de dígitos de PI, ocupando aproximadamente 98Mb.
  4. arquivos dos projetos escritos em C
     Cabe ressaltar que os arquivos com os dígitos de PI em questão possuem apenas uma linha, então tenha *muito* cuidado na hora de carregá-los para a memória!

Questões interessantes deste projeto

Observação: considere sempre que o primeiro dígito a ser usado encontra-se após o 3., ou seja, para PI=3,141592..., o quinto dígito é 9.
  1. Verificar se é verdade que qualquer número de tamanho 3 existe ou não nos 1 milhão de dígitos, ou seja, para todos os números com tamanho 3 (por exemplo, 005, 456, ou 768) entre 000 e 999, verifique sua primeira ocorrência nos dígitos de PI no arquivo de 1 milhão de dígitos
  2. E para a totalidade de números de tamanho igual a 6 (por exemplo, 567333), quantos e quais não existem?
  3. Conte o total de ocorrências deste número de tamanho 3 para todos os 1 milhão de dígitos, fazendo o mesmo para dez e cem milhões
  4. Conte quantas sequências de números idênticos de tamanho 4 e 5 existem nos dígitos de PI. Por exemplo, para o número 7777 ou 55555, quantas ocorrências existem?
  5. Mostre o dígito (caso ocorram) da primeira ocorrência bem como o total de ocorrências das seguintes sequências especiais de números: 0123456789 ou 9876543210, 112233 ou 223344 ou 998877, 000111222 ou 999444111, 0000011111 ou 8888822222, 3141592653 (estes são os primeiros 10 dígitos de PI). Pense em outras e implemente
  6. Para sequências de números pares e ímpares de tamanho igual a 10, conte o total de ocorências nos dígitos de PI (por exemplo, sequências, 0204060810 ou 0602081004)
  7. Procurar ocorrencias de strings baseadas em datas de nascimento (formato ddmmaaaa, mas procure também por mmddaaaa, aaaaddmm, aaaammdd) em todos os arquivos, contando o total de ocorrências existente
  8. Mostrar uma determinada sequência de dígitos de PI, onde é passada uma posição qualquer (por exemplo, 495959) e uma função mostrando os N dígitos anteriores e os M dígitos posteriores (inclusive a sequência)
  9. Procure o total de ocorrências de números primos (começando em I e percorrendo até J) nos primeiros K dígitos dos cem milhões de dígitos de PI. Por exemplo: para os números primos compreendidos entre 1000 e 10000, busque suas ocorrências em PI
  10. Faça uma função que salva N novos arquivos dos dígitos de PI contendo M caracteres cada (padrão de nomes: PI_i.txt)
  11. Faça um arquivo chamado PI-colunas.txt contendo N linhas e M colunas onde os primeiros K dígitos de PI são utilizados. Por exemplo, para tamanho de coluna igual a 3, linha igual a 3 e os primeiros 27 dígitos, ficaria:
    1. 141 592 653
    2. 589 793 238
    3. 462 643 383
  12. Para cada dígito de 0 a 9, conte quantas ocorrências existem nos primeiros N dígitos de PI (tente contar no arquivo com cem milhões de dígitos)
  13. Faça uma função onde é passado um total de dígitos totais N, um valor K e um valor M e esta pega os primeiros N dígitos de PI e cria um arquivo com M linhas e tamanho de coluna igual a K (esta é uma combinação de funções implementadas anteriormente)
  14. Compute as seguintes funções geométricas com o valor de PI com diferentes precisões mostrando as diferenças nas respostas (seja π o valor de PI com diferentes precisões (cuidado) e r o valor do raio)
    1. Área de um círculo: Ac = π*r2
    2. Perímetro de um círculo: Pc = 2*π*r
    3. Área de uma esfera: Ae = 4*π*r2
    4. Volume de uma esfera: Ve = 4*π*r3/3


Um comentário:

  1. a sr Ricardo,
    Grato por postar esse estudo bem minucioso;
    Tambem estou fazendo um estudo estatistico sobre o PI mas consegui
    um milhão e gostaria de obter 10 milhões porém clico no link e ele não vem...
    Seria por aqui ou o servidor não está mandando?
    Uso a Linguagem Pascal (Delphi 7) com algumas functions q eu mesmo
    desenvolvi (acumuladores associados a nomes) e gostaria de uma amostragem
    maior...
    Grato por qualquer informação,
    Laercio Santos (laercium@yahoo.com.br)

    ResponderExcluir