segunda-feira, 25 de novembro de 2019

A Melhor Base II

Após verificar que a base 3 é a base mais econômica dentre as bases tradicionais, resolvi experimentar algumas representações diferentes: a base fatorádica e os numerais romanos.

O problema é encontrar o menor número de placas para representar todos os números de 0 a 999.

#!/usr/bin/perl
use Roman;
use Data::Dumper;
use strict;

my %symbols=();

for my $b (0..999) {
  my %s=();
  my $r=factoradic($b);
  print "$r\n";
  my @s=split(//,$r);
  for my $s (@s) {
    $s{$s}++;
    if ($symbols{$s}<$s{$s}) {
      $symbols{$s}=$s{$s};
    }
  }
}

for my $d (keys %symbols) {
  print "$d => $symbols{$d}\n";
}

sub factoradic {
  use integer;
  my $n=shift;
  my $f='';
  my $i=1;
  do {
    $f=($n%$i).$f;
    $n/=$i;
    $i++;
  } while($n>0);
  
  return $f;
}


Para os numerais romanos, encontrei um módulo pronto no CPAN. Não tive tanta sorte com a base fatorádica, mas é muito fácil converter.

Os numerais romanos surpreenderam: são bastante mais econômicos e necessitam apenas 15 placas (mais uma para o zero). Já a fatorádica, requer 22 placas e fica, portanto, entre as bases 5 e 6 no ranking geral.

As placas necessárias seriam: I (3), V (1), X (4), L (1), C (4), D (1), M (1). Para o zero, a melhor opção seria N (de nulla ou nihil).

quarta-feira, 13 de novembro de 2019

A Melhor Base

Suponha que queiras montar um placar eletrônico para uma quadra de basquetebol. As pontuações costumam rondar uma centena; geralmente abaixo, frequentemente acima. Então, são necessários, pelo menos, 3 dígitos decimais. Para cada dígito, são necessárias 10 placas (de 0 a 9). Ao todo são 30 placas.

O que muda se usarmos outras bases? A conta é simples:

Número n de dígitos na base b = log(1000)/log(b)
Total de placas = b*n

Para as bases até 10, os resultados são:


2       19.9315685693242
3       18.8631294686045
4       19.9315685693242
5       21.4601483711009
6       23.1317497608924
7       24.8491879115537
8       26.5754247590989
9       28.2946942029067
10      30

A base 3 é a campeã. Seriam necessárias 19 placas para exibir todas as 1000 possibilidades de 0 a 999.

O valor de 999 em base 3 é 1101000. São 7 dígitos. Como não vamos passar de 999, se tivermos 7 dígitos, o mais significativo só pode ser 1. Então, 6*3 placas garantiriam todas as possibilidades dos 6 primeiros dígitos e uma placa adicional resolveria o sétimo.

quarta-feira, 11 de setembro de 2019

Multiplicação Russa e suas Consequências

A multiplicação russa é interessante porque funciona muito bem na base 2.

A idéia é simples:
  • Crie uma coluna para cada número (maior à esquerda, menor à direita);
  • Divida o número maior por dois até chegar a 1;
  • Multiplique o número menor por dois o mesmo número de vezes;
  • Descarte as linhas em que o número da esquerda for par;
  • Some os números que restavam à direita.
Por exemplo, 3 * 18:

18   3
 9   6
 4  12
 2  24
 1  48

Resultado= 6+48=54


Ela fica mais divertida em base 2:

00010010 00000011
00001001 00000110
00000100 00001100
00000010 00011000
00000001 00110000    

Resultado = 00000110+00110000= 110110


Ou seja, basta ir fazendo shifts.

Uma otimização óbvia é pegar a maior potência de dois para dividir o problema. As multiplicações por potências de dois sempre acabam com apenas uma linha sendo considerada: a maior do lado direito (porque todos os números do lado esquerdo são pares, exceto a última).

8  3
4  6
2 12
1 24

A resposta é 24. nenhuma soma é precisa, porque 8*3=3*2*2*2


E se eu repetir esse processo de sempre pegar a maior potência? Nesse caso, vou poder descrever sucintamente o processo como: para multiplicar m por n, percorro os bits de m e, para cada bit 1, adiciono n deslocado à esquerda pela posição desse bit.

Sucintamente, em Perl (devia ser assembly!), seria algo assim:

#!/usr/bin/perl
use strict;
use warnings;
use integer;

my $n=$ARGV[0];
my $m=$ARGV[1];
my $p=0;
my $total=0;

do {
  $total+=$m<<$p if $n&1;
  $p++;
} while ($n>>=1);

print $total;


Ou seja, se quero multiplicar 46 por 5, como cinco é 101, executo 46<<2 + 46<<0 (46*4+46*1 para os binário-deficientes). A respostá é óbvia, dado que 46*5=46*(4+1).

Uma solução alternativa um pouco mais elegante é essa função recursiva:

#!/usr/bin/perl
use strict;
use warnings;
use integer;

my $n=$ARGV[0];
my $m=$ARGV[1];

sub mult {
  my ($n, $m)=@_;
  
  return $m if $n==1;
  
  my $d=0;
  
  $d=$m if $n&1;
  return $d + mult($n>>1, $m<<1);
}

print mult($n, $m);

sexta-feira, 23 de agosto de 2019

Minha Reforma Ortográfica

Muita gente ficou insatisfeita com a última reforma ortográfica. Eu tenho minhas diferenças com ela também. E com a maneira como os acentos são ensinados na escola.

O problema dos acentos no português é que eles não sabem bem o que querem ser na vida: se indicam tonicidade, ou se indicam o som, ou se indicam as duas coisas.

Eu acho que deveriam apenas indicar a tonicidade (com a exceção única da crase). Já convivemos com porco e porcos; ovo e ovos.

O alfabeto cirílico possui letras para ditongos. Isso também nos ajudaria a eliminar duas categorias de acentos: os hiatos e os paroxítonos terminados em ditongo crescente. Os dois são meio atravessados, porque o que eles querem, na verdade, é deslocar a tonicidade para nos obrigar a pronunciar o ditongo. Querem resolver um problema por segunda intenção.

Podíamos muito bem adicionar umas letras para os ditongos, mas talvez seja mais prático aproveitar o fato de que o y e o w voltaram ao alfabeto e dar-lhes utilidade.

Então, na minha nova ortografia, teríamos: "saude" e "sawdade"; "distancya" e "policya"; "pais" e "pays".

Eu moro num pais tropical com meus pays, temos saude mas a distancya de nossa terra nos traz sawdade. Nenhum acento nessa frase!

quarta-feira, 19 de junho de 2019

Medição de Poluição em Porto Alegre II

O clima em maio e junho está realmente estranho. Fez calor e houve pouca chuva. Além disso, notei que o ar tinha cheiro de São Paulo. Ou seja, tinha cheiro de combustível. Por isso resolvi religar o meu medidor de partículas.

O ar realmente piorou desde minha última medição. Entretanto, ao menos em relação às partículas, ele continua dentro do razoável.


Uma única medição de PM10 passou do 100 (indo de satisfatório para moderadamente poluído). A medição de PM2.5 nunca passou de 44, então permaneceu no reino do ar bom.

O tempo não esteve seco durante esses dias, indo a 100% de umidade relativa todas as noites.

Deduzo que a diferença se deva à falta de chuva e à falta de ventos.

quarta-feira, 8 de maio de 2019

Atenciosamente

Acho curiosa essa forma de terminar as correspondências: Att. Querem supor que é abreviação de Atenciosamente. Não é. Além de estar errado, abreviar a saudação é o oposto de ser atencioso. É pior ainda quando está na assinatura do e-mail: o sujeito não se dá sequer ao trabalho de fingir ser atencioso.

A abreviação chega a ser irrelevante. Deveria ser proibida para esta palavra. Quem quer ser atencioso, não encurta a saudação final.

Atenciosamente,

Forinti.

sexta-feira, 22 de março de 2019

Fourier em SQL (e Perl)

Dada uma nova ferramenta, resolvi experimentar no SQL. A transformada discreta de Fourier resume-se, basicamente, a um montão de multiplicações e somas. É fácil repetir em SQL. Já a FFT nem tanto. SQL simplesmente não se presta a recursões.

Outra desvantagem do SQL é a ausência de suporte a números complexos (Perl oferece o fantástico módulo Math::Complex que, inclusive, reimplementa todas as operações da linguagem). A DFT não exige muito, basta separar a conta em cos() e i*sin(). Mas se fôssemos implementar a FFT, seria preciso fazer a multiplicação por extenso. Isso só seria chato, resolver a recursão é que é o problema do SQL.

Mesmo assim, a DFT pode ser bem útil e, se vamos usá-la num banco, é porque não estamos com pressa mesmo.

Comecei por um algoritmo FFT em Perl para poder conferir os resultados do SQL. O script executa a FFT sobre a função sin(x), assim como a consulta (que escrevi para conferir os resultados do Perl).

DFT de sin(x)

Os dois deram o mesmo resultado, mas a implementação do FFT foi muito mais rápida, como esperado.

O grande porém da FFT é que precisamos ter um número de elementos que seja potência de 2. Com DFT, podemos usar qualquer quantidade. Então, resolvi experimentar numa tabela de pagamentos.

Usei dois anos de pagamentos e obtive o seguinte gráfico (que parece indicar que há um componente trimestral nos pagamentos):


Aprender a implemenar a DFT e a FFT é só o primeiro passo. Analisar os resultados e achar aplicações é o próximo passo.