Fatorial revisitado

Eu estava tendo dificuldades para criar um executável com um banco de dados embutido (com Tcl, SQLite e Freewrap), quando resolvi brincar um pouco com o Tcl. Escrevi uma pequena função para calcular fatoriais. Tcl permite gerar números bem grandes (como 1000!) com facilidade. Para tornar a coisa mais interessante, resolvi escrever uma versão sem if (abaixo).

proc fac {n} {
  set e 1;
  for {set x 2} {$x<=$n} {incr x} {
    append e "*$x"
  }
  puts $e
  return [expr $e]
}

A função simplesmente gera uma expressão (por exemplo, ela gera "2*3*4*5" para 5!) e depois calcula o resultado. Talvez inspirado pela recente releitura o livro Metamat! (de Gregory Chaitin), achei que seria interessante encontrar uma maneira de encolher essa expressão e assim tornar o programa mais curto e eficiente.

A solução mais próxima seria gerar um produto de primos, assim a multiplicação teria o menor número possível de multiplicandos. Não demorou muito para sair um algoritmo parecido com o Crivo de Eratóstenes. Se eu quiser calcular n!, faço o seguinte:

1. Enumero todos os inteiros até n;
2. Começando em 2, marco todos os múltiplos dos primos e anoto qual potência de cada primo divide cada múltiplo (e vou somando as potências);
3. Ao fim, terei uma potência para cada primo e a multiplicação de cada um elevado à sua potência produzirá o fatorial.

Por exemplo, para 6!, os passos são:

1. Começando em 2, descubro que 2=2^1, 4=2^2 e 6=2^1*3;
2. Com 3, tenho 3=3^1 e 6=3^1*2;
3. Quatro posso ignorar, porque já o visitei e anotei como inteiro composto;
4. 5 não tem múltiplos menores ou iguais a 6, então anoto 5^1;
5. Finalmente, 6 já sei que não é primo.

O resultado é 2^4*3^2*5 e isso produz 720, conforme esperado. Abaixo apresento uma solução em Java:

  private static int in(int p, int i) {
    int n=0;
    while(i%p==0) {
      n++;
      i=i/p;
    }
    return n;
  }

  public static BigInteger f(int n) {
    int m=n+1;
    int[] p=new int[m];
    for(int i=2; i<=m/2; i++) {
      if(p[i]!=-1) {
        p[i]=1;
        for(int j=i+i; j<m; j+=i) {
          if(j%i==0) {
            int v=in(i,j);
            p[i]+=v;
            p[j]=-1;
          }
        }
      }
    }
    BigInteger f=BigInteger.ONE;
    for(int k=2; k<m; k++) {
      int pk=p[k];
      if(pk>=0) {
        if(pk==0) {
          f=f.multiply(BigInteger.valueOf(k));
        } else {
          f=f.multiply(BigInteger.valueOf(k).pow(pk));
        }
      }
    }
    return f;
  }

Esse código tem uma pequena otimização. Ele percorre os primos apenas até n/2. Todos os primos acima disso só vão aparecer uma única vez no produto final (em 10!, por exemplo, 7 só aparece como 7^1). O array p começa com zeros. As posições ocupadas por primos vão recebendo as respectivas potências e as demais recebem -1. Ao fim, as posições de primos acima de n/2 vão continuar com 0 (porque não as visitamos), então a segunda parte da função (que faz as multiplicações para calcular o resultado final) ignora os valores menores que zero, troca os zeros por uns e usa os demais valores como os encontrar.

Comparando com uma função simples que multiplica instâncias de BigInteger de 2 até n, para valores pequenos, a diferença de tempo é insignificante. Em algum ponto entre 1000! e 2000!, a nova função passa a tomar um pouco mais que a metade do tempo. Ela é mais econômica em memória também.

O método f() retorna um BigInteger, mas imagino que em algumas situações possa ser mais útil guardar o produto de primos ou simplesmente imprimir a expressão.

Tcl e Freewrap

Recebi a incumbência de escrever um pequeno programa para corrigir alguns arquivos de configuração. Os requisitos eram estes:

1. Rodar em Windows;
2. Ser um executável sem dependências externas (principalmente, não depender de uma VM);
3. Alterar o valor da coluna 114 para 4 em todas as linhas;
4. Gravar uma cópia do arquivo original.

Pareceu-me uma boa oportunidade de usar o Tcl. Desta vez, sem o Tk. Com o Freewrap, posso rapidamente criar um executável.

O script abaixo mostra como é simples a tarefa com Tcl, mas é o Freewrap que torna a aplicação da linguagem interessante no Windows.

if {$argc<1} {
  puts "Uso: setcol arquivo";
  exit
}

set filename [lindex $argv 0]

proc replace {filename} {
  set in  [open $filename]
  set out [open "$filename.temp" w]

  while {[gets $in line] >= 0} {
    puts $out [string replace $line 113 113 4]
  }
  
  close $in
  close $out
  file delete "$filename.bak"
  file rename $filename "$filename.bak"
  file rename "$filename.temp" $filename
}

if [catch {replace $filename} result] {
  puts stderr "Cuidado: $result"
  exit
}

A força do Freewrap para este tipo de problema (uma solução para uma máquina remota com poucos recursos de software) é que ele permite agregar binários adicionais ao pacote. Então, posso enviar um script e vários binários acessórios sem nenhum esforço. Posso também criar uma interface gráfica com Tk para facilitar o uso de algum binário por um operador leigo. E o resultado vai rodar em qualquer versão do Windows (talvez não no Windows 3.11, mas, sem testar, não é possível excluir a possibilidade).

Este cenário é dos mais simples e gerar o executável é uma questão apenas de digitar o seguinte comando:

freewrapTCLSH setcol.tcl

Isso produz um arquivo chamado setcol.exe com aproximadamente 2,3MB. Essa versão do freewrap não inclui o Tk. Com ele, o executável teria mais de 4MB.

Velhas ferramentas

Algumas velhas ferramentas continuam úteis mesmo depois da aparição de modernidades muito mais sofisticadas. A linguagem Tcl/Tk surgiu um 1988 e tive o primeiro contato com ela por volta de 1996.

Ela é uma linguagem muito simples, projetada para facilitar a vida de quem quer montar uma interface gráfica para um programa ou oferecer uma linguagem de programação simples para um sistema.

Existem alternativas muito mais sofisticadas, como Perl ou Python, mas o Tcl/Tk tem uma grande vantagem: além de ser portável, é muito simples gerar um executável para Windows. Ela está sempre presente em todas as plataformas *nix. Eu já vi um Unix sem um compilador C, mas nunca vi um sem Tcl/Tk.

Em Tcl/Tk, tudo é um comando seguido de parâmetros separados por espaços.

comando parm1 parm2 parm3...

Até mesmo as estruturas de controle são comandos. O if é um comando cujo primeiro parâmetro é uma condição, o segundo uma ação a executar se a condição for verdadeira, etc. É fácil escrever um comando em C e adicioná-lo ao ambiente.

Pois, há pouco precisei de um find com expressão regular no Windows, como no Linux. Eu podia ter procurado o find do GNU, mas resolvi brincar um pouco com o Tcl.

O resultado foi muito mais simples do que eu esperava:

if {$argc<2} {
  puts "Usage: find dir regexp";
  exit
}

set dir [lindex $argv 0]
set re [lindex $argv 1]

proc find {filename re} {
  set total 0
  if {[regexp $re $filename]>0} {
    puts $filename
    incr total
  }
  if {[file isdirectory $filename]>0} {
    set files [glob "$filename/*"]
    foreach f $files {
      catch { incr total [find $f $re] }
    }
  }
  return $total
}
puts "[find $dir $re] files"

Esse pequeno programa recebe dois parâmetros: um diretório e uma expressão regular. Ele percorre os diretórios recursivamente (a partir do indicado) e vai imprimindo na tela os nomes dos arquivos que são reconhecidos pela expressão regular. No fim, ele ainda diz quantos arquivos foram encontrados. Por exemplo:

find C:\Windows\ .*dll

Testei-o no Linux e ele funcionou sem nenhuma modificação, coisa que seria difícil, mesmo para o Java. O executável tem cerca de 1,5MB. É um pouco grande, mas a maior parte se deve ao interpretador, que é empacotado junto com o programa. Portanto, programas maiores não devem crescer muito de tamanho. De qualquer forma, é muito mais prático que forçar o usuário a instalar o Java Runtime (uns 15MB) ou o Perl (uns 5MB).