De volta ao pi – agora com Leibniz
Versão inicial baseado na fórmula de Leonhard Euler
Tudo começou com o post: calculando o pi em c ansi, um exercicio para cálculo do pi baseado na fórmula de Leonhard Euler, nossa primeira versão utilizava esta fórmula de forma bem simples, tudo explicado no mesmo link acima. Fizemos um teste com 10.000.000 de números primos, estamos aguardando o resultado…. 
Segunda versão com a fórmula de Euler
Depois de alguma pesquisa resolvemos implementar uma nova versão baseada na mesma fórmula, desta vez o que muda é a forma de “gerar” o número de números primos desejado pelo usuário, agora usamos um algoritmo um pouco mais sofisticado que, com certeza, nos trará mais velocidade, o algoritmo para gerar os primos é explicado aqui. Também trabalhamos com variaveis double para tentar maior precisão
Em um teste com 10.000.000 de números primos obtivemos o resultado apresentado na figura abaixo:
Abaixo o codigo da segunda versão:
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 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 | #include <math.h> #include <time.h> #include <stdio.h> #include <stdlib.h> // Variaveis globais char tics[12] = "Segundo(s)"; time_t start; // Prototipos: int eh_primo(unsigned int n); float time_waste(time_t start, time_t end); float time_waste(time_t start, time_t end); double retorna_pi(double nprimos); int main() { double n; time_t end; system("cls"); printf("Entre com numero de primos : "); scanf("%lf",&n); printf("%1.60lf\n", retorna_pi(n)); end = time(NULL); printf("\ntempo gasto: %f, %s\n ",time_waste(start,end),tics); fflush(stdin); getch() ; } // Calcula e retorna o PI double retorna_pi(double nprimos) { double soma1 = 1; unsigned int primos = 0, count = 2; start = time(NULL); while (primos < nprimos) { if (eh_primo(count) == 1) { soma1 *= (pow(count, 2) / (pow(count, 2) - 1));; primos++; } count++; } return sqrt(soma1 * 6); } int eh_primo(unsigned int n) { unsigned int i; static unsigned int primes55[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257}; // Checa divisibilidade do numero pelos primos acima for (i = 0; i < 55; i++) { if (n % primes55[i] == 0) { if (n == primes55[i]) return 1; else return 0; } } // extrai raiz do numero n unsigned int raiz_n = sqrt(n); // Se o numero par é descartado antecipadamente if (n % 2 == 0) return 0; // Verifica se tem algum divisor entre 3 e a raiz do proprio numero for (unsigned int i = 3; i < raiz_n; i += 2) { if (n % i == 0) return 0; } return 1; } // Calculo do tempo gasto (gastando mais tempo :/ ) float time_waste(time_t start, time_t end) { float tempo_gasto; tempo_gasto = (difftime(start, end)*-1); // POG tempo_gasto = (tempo_gasto < 1) ? (0.1) : tempo_gasto; if (tempo_gasto > 59) { tempo_gasto = (tempo_gasto / 60); strcpy(tics, "Minuto(s)"); } if (tempo_gasto > 59) { tempo_gasto = (tempo_gasto / 60); strcpy(tics, "Hora(s)"); } return tempo_gasto; } |
Fórmula de Leibniz
Não é a primeira vez que procurando algo relacionado à matemática ou a computação, nos deparamos com algo do genial Leibniz, é interessante como este verdadeiro genio da humanidade é tão pouco lembrado. A figura ao lado foi extraida em um texto da wikipedia e, por si só, ja explica a fórmula, para desenvolver o algoritmo passamos o 4 para o lado esquerdo da equação, criamos uma variável que funciona como uma “flag” para somar ou subtrair, é muito mais fácil apresentar diretamente o código que tentar explicar.
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 | #include <stdio.h> #include <stdlib.h> #include <time.h> // Calculo do PI baseado nas séries de Leibniz // 4/1 - 4/3 + 4/5 - 4/7 + 4/9 ... // Prototipos void tempo_gasto(time_t start, time_t final); double pi(double divisores); // Variaveis globais :/ float time_waste;char tics[10] = "Segundo(s)"; void main() { double divisores; system("cls"); printf("Entre com o numero de iteracoes: "); scanf("%lf",&divisores); printf("%1.20lf\n", pi(divisores)); printf("Tempo gasto: %.2f %s \n\n", time_waste, tics); fflush(stdin); getchar(); } // Calculo do pi double pi(double divisores) { double pi = 0.0, divisor = 1.0; int somar = 1; time_t start = time(NULL), end; do { if (somar == 1) { pi = pi + (4.0 / divisor); somar = 0; } else { pi = pi - (4.0 / divisor); somar = 1; } divisor = (divisor + 2.0); } while (divisor < divisores); end = time(NULL); tempo_gasto(start, end); return pi; } // Funcao para mostar o tempo gasto no calculo void tempo_gasto(time_t start, time_t final) { time_waste = (difftime(start, final)*-1); // POG time_waste = (time_waste < 1) ? (0.1) : time_waste; if (time_waste > 59) { time_waste = (time_waste / 60); strcpy(tics, "Minuto(s)"); } if (time_waste > 59) { time_waste = (time_waste / 60); strcpy(tics, "Hora(s)"); } } |
Também fizemos o teste com 10.000.000, o resultado:
Como o tempo foi muuito rápido, resolvemos fazer com 1.000.000.000, o resultado foi:
Como o tempo continua sendo extremamente satisfatório, resolvemos extrapolar e testar com 1.000.000.000.000 (Um trilhão) de iterações, é impressionante como este algoritmo é rápido, neste caso a aproximação ficou um pouco melhor, talvez se fizermos mais testes com um número maior de iteracoes, consigamos precisao um pouco melhor.
Very very very crazy!
Pesquisando sobre o pi na rede, encontramos um codigo neste site que retorna o seguinte resultado:
O mais “doido” é o código, veja:
1 2 3 4 5 6 7 8 9 10 11 12 13 |
Insano!