Uma coisa que está na minha lista faz algum tempo é fazer testes de velocidade com as várias plaquinhas que eu tenho. Mais pela brincadeira, pois estes testes normalmente não representam direito o desempenho em aplicações reais. E aí me surgiu a ideia de fazer a comparação calculando os dígitos do Pi.
Chovendo no molhado, o Pi é a razão entre a circunferência de um círculo e o seu diâmetro. É um número "irracional", que não pode ser colocado na forma de fração e na forma decimal tem um número infinito de dígitos. Calcular os dígitos do Pi tem ocupado pessoas desde muito tempo atrás (a wikipedia tem uma cronologia).
A partir de 1400 sabe-se que o Pi pode ser calculado através da soma de séries infinitas. Com o advento do computador foram desenvolvidos algorítimos que facilitam e aceleram o cálculo. Na minha busca eu rapidamente achei o seguinte programa (de autoria de Dik T Winter):
int a=10000,b,c=2800,d,e,f[2801],g;main(){for(;b-c;)f[b++]=a/5;
for(;d=0,g=c*2;c-=14,printf("%.4d",e+d/a),e=d%a)for(b=c;d+=f[b]*a,
f[b]=d%--g,d/=g--,--b;d*=b);}
Você talvez encontre uma versão com pequenas diferenças, esta acima calcula os primeiros 800 dígitos do Pi. Este programa está, propositalmente, compactado e ofuscado. Para os meus testes eu fiz uma versão um pouco mais legível e adaptada para compilação na IDE do Arduino:
/*
* Calculo dos dígito de Pi
* Usando o algoritimo Spigot de Rabinowitz e Wagon
* Adaptação da versão compacta e obsfucada escrita por Dik T. Winter:
*
* int a=10000,b,c=2800,d,e,f[2801],g;main(){for(;b-c;)f[b++]=a/5;
* for(;d=0,g=c*2;c-=14,printf("%.4d",e+d/a),e=d%a)for(b=c;d+=f[b]*a,
* f[b]=d%--g,d/=g--,--b;d*=b);}
*
* Comentários nas declarações copiados de
* https://stackoverflow.com/questions/4084571/implementing-the-spigot-algorithm-for-%CF%80-pi
*
* Daniel Quadros junho/2021
*/
#define NDIGITS 10000 //max digits to compute
#define LEN (NDIGITS/4+1)*14 //nec. array length
int32_t a = 10000; //new base, 4 decimal digits
int32_t b = 0; //nominator prev. base
int32_t c = LEN; //index
int32_t d = 0; //accumulator and carry
int32_t e = 0; //save previous 4 digits
int32_t f[LEN+1]; //array of 4-digit-decimals
int32_t g = 0; //denom previous base
void setup() {
delay(1000);
Serial.begin(115200);
}
// Não usado
void loop() {
while (Serial.read() != '\n') {
delay(100);
}
Serial.println("PI = ");
long inicio = millis();
calcula();
long tempo = millis() - inicio;
Serial.println();
Serial.print ("Tempo = ");
Serial.print (tempo);
Serial.println ("ms");
}
// Cálculo dos dígitos do Pi
void calcula() {
char dig[5] = "0000"; // para fazer o print
int n = 0; // para mudar de linha a cada 100 dígitos
c = LEN;
for(b = 0; b < c; b++) {
f[b] = a/5;
}
e = 0;
for (; c > 0; c -= 14) {
d = 0;
g = c*2;
b = c;
for (;;) {
d += f[b]*a;
f[b] = d % --g;
d /= g--;
if (--b == 0) {
break;
}
d *= b;
}
uint16_t val = e+d/a;
dig[0] = (val / 1000) + '0';
dig[1] = ((val / 100) % 10) + '0';
dig[2] = ((val / 10) % 10) + '0';
dig[3] = (val % 10) + '0';
Serial.print (dig);
n += 4;
if (n == 100) {
Serial.println();
n = 0;
}
e = d % a;
}
}
Mas o que está sendo feito, e porque? Não me arrisco a dizer que entendi completamente, mas aqui vão algumas informações e referências. O algoritmo usado pertence a uma classe chamada "spigot" (torneira): os dígitos vão sendo gerados na ordem e não são usados diretamente no cálculo dos dígitos seguintes. Este algorítimo específico foi criado em 1995 por Stan Wagon and Stanley Rabinowitz.
Algumas características interessantes deste algorítimo:
- Requer somente soma, subtração, multiplicação e divisão de inteiros
- Os dígitos são gerados de 4 em 4
- A quantidade de dígitos a calcular precisa ser definida a priori
- Requer um vetor com 14 inteiros para cada conjunto de 4 dígitos
Eu rodei o programa (acertando o número de dígitos conforme a memória disponível) em algumas placas da minha coleção: Arduino Uno, Raspberry Pi Pico, ESP32, Black Pill (STM32) e Seeduino XIAO. O resultado esta aqui, no meu canal do YouTube.
Nenhum comentário:
Postar um comentário