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.

Desenhando para Entender

A DFT (Transformada Discreta de Fourier) é relativamente simples de entender, mas é um algoritmo de complexidade o(n²). A FFT (Transformada Rápida de Fourier) tem complexidade o(nlogn), mas é mais complicada, naturalmente.

Para ajudar minha compreensão, resolvi desenhar os valores para enxergar as zonas comuns que ajudam o FFT a acelerar as contas.

Com ajuda do GD, excrevi um programa em Perl para gerar uma imagem com os valores das funções-base para diferentes resoluções (potências de dois).

A imagem abaixo vai de 2⁰ a 2¹⁰. Cada valor tem 100 linhas de altura e 2ⁿ divisões. Isto é, a imagem começa com 1 valor, depois 2, depois 4, etc. Deixei linhas pretas para demarcar os valores (cada um ocupa um retângulo de altura 100 e largua 1024/2ⁿ.

O valor de cada célula é e^-i2pik/N. O componente vermelho é abs(re)*255, ou seja, a parte inteira. O componente verde é a parte imaginária e o azul é zero.

Já dá para enxergar por onde otimizar o DFT.

Se adiciono um componente azul para valores negativos da parte real, terminho com isto:

Se faço o mesmo para a parte imaginária, tenho isto:

Já que não tenho 4 componentes de cor, vario a intensidade do azul conforme as partes real e imaginária são postivas ou negativas.

Juntando essas ideias, dá para imaginar como atacar o problema.

Internet com Horário Comercial

Uma aplicação sensível precisa estar disponível na Internet. O administrador, preocupado sempre com a segurança, decide que o melhor é limitar o acesso ao horário comercial. Entretanto, supõe que quem estiver dentro do prédio fora do horário comercial seja de confiança.

A solução é usar o mod_rewrite e aprender a usar o [OR].

  #Disponível externamente somente das 8h às 18h, de segunda a sexta.
  RewriteCond %{TIME_HOUR} ^(00|01|02|03|04|05|06|07|18|19|20|21|22|23)$ [OR]
  RewriteCond %{TIME_WDAY} ^(0|7)$
  RewriteCond %{REMOTE_ADDR} !^192\.168.*$
  RewriteRule ^.*$ - [F,L]

Entre 8h e 18h e aos sábados e aos domingos, o acesso é bloqueado, exceto se o IP iniciar com 192.168.

Por omissão, as regras são analisadas com AND. O que não está claro é como agrupar quando há ORs também.

O código indica que o OR tem precedência. Então, a solução acima interpreta-se como (A OR B) AND C.