Menos velocidade, mais rapidez

Acho muito curiosos os argumentos de que o limite de velocidade nas avenidas de Porto Alegre é baixo, porque minhas viagens para casa no fim do dia dificilmente alcançam 10km/h. Considerando a quantidade de carros nas ruas, aumentar a velocidade não iria resolver nada, portanto.

Parece-me que há, por outro lado, bons argumentos para diminuir a velocidade máxima em toda a cidade para 40km/h.

É comum reencontrarmos os apressadinhos nas sinaleiras. Eles correm para utrapassar e ganhar a corrida até o próximo sinal vermelho. O que me leva a creer que os tempos dos deslocamentos urbanos são muito mais regidos pelos tempos de parada ou lentidão que pelos tempos de velocidade.

Porto Alegre não é uma cidade muito grande. Pode-se ir da zona sul à zona norte em menos de 20km. E, supondo que não houvesse qualquer obstáculo no caminho, essa distância seria percorrida em 20 minutos a 60km/h ou em 30 minutos a 40km/h.

Quem tenta entrar numa avenida sabe que a velocidade na via mais rápida dificulta o acesso. Nas ruas de 40km/h, os rapidinhos que excedem o limite também roubam dos outros motoristas a possibilidade de fazer uma conversão em menos tempo. E ainda há o tempo de luz amarela nos semáforos, que deve ser maior para dar segurança aos cruzamentos das avenidas.

Além disso tudo, há o fato de que os atropelamentos a 60km/h (90% são fatais) são muito mais perigosos que os atropelamentos a 40km/h (50% são fatais). Havendo menos velocidade, a cidade tornar-se-ia mais segura para os ciclistas e mais gente poderia sentir-se motivada a adotar esse meio de locomoção.

Em resumo, acho que há mais vantagens de termos uma velocidade máxima menor do que perdemos por poder andar rápido por alguns segundos de vez em quando. Mesmo assim, não guardo muita esperança de que o motorista portoalegrense médio queira adotar uma medida racional e civilizada para melhorar o trânsito.

Até tu, Ubuntu?

Minha máquina Ubuntu tem dois monitores. Eu queria desabilitar um deles temporariamente, porque não estava funcionando. Assim como o Windows, o Ubuntu retorna à configuração anterior se uma mudança na configuração de video não for confirmada em poucos segundos (para salvar o usuário, caso a alteração tenha desligado o sinal).

Pois bem, o Ubuntu, deduzo eu, estava tentando pedir a confirmação justamente no monitor que eu estava tentando desabilitar, porque, alguns segundos depois da alteração, tudo piscava e o monitor desligado constava novamente como habilitado.

Foi um momento muito triste na história dos sistemas operacionais.

Fatorial revisitado III

Minhas tentativas anteriores de otimizar o cálculo dos fatoriais a partir de potências de números primos tinha evoluído até eu conseguir calcular o total dos expoentes de cada primo p entre potências consecutivas. Agora, consegui encontrar uma maneira de calcular todos os expoentes até uma potência qualquer.

Para um primo p, a soma dos expoentes de sua participação em cada múltiplo anterior ou igual a pⁿ é

n+[(pⁿ-p*n+n-1)/(p-1)]
= pⁿ-1/p-1

Por exemplo, entre 2 e 8, temos os seguintes múltiplos de 2: 2, 4, 6, e 8. Anteriormente, teríamos que calcular os expoentes entre 2 e 4 e somá-los aos expoentes entre 4 e 8 e ainda somar os expoentes das potências (2, 4, e 8).

Agora, chegamos rapidamente ao resultado:

3+[(2³-2*3+3-1)/(2-1)] = 3+[(8-6+3-1)/1] = 3+4 = 7
= 8-1/2-1
= 7

Conferindo os múltiplos de 2, confirmamos que

• 2 = 2¹
• 4 = 2²
• 6 = 2¹*3
• 8 = 2³

E assim, percebemos que a soma dos expoentes é, de fato, 7.

Alterei um pouco o código para exibir as respectivas fatorações.

import java.math.BigInteger;

public class Factorial {

  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];
    double logn=Math.log(n);
    for(int i=2; i<=m/2; i++) {
      if(p[i]!=-1) {
        //Marcar todos os múltiplos
        for(int j=i+i; j<m; j+=i) {
          p[j]=-1;
        }
        //Calcular soma de expoentes até a maior potência anterior a n
        int power=(int)(logn/Math.log(i));
        int k=(int)Math.pow(i, power);
        p[i]=(k-1)/(i-1);
        //Calcular os expoentes para os múltiplos que seguem a última potência
        for(int l=k+i; l<m; l+=i) {
          p[i]+=in(i, l);
        }
      }
    }
    BigInteger f=BigInteger.ONE;
    for(int k=2; k<m; k++) {
      int pk=p[k];
      if(pk>=0) {
        if(k>2) {
          System.out.print("*");
        }
        if(pk<2) {
          System.out.print(k);
          f=f.multiply(BigInteger.valueOf(k));
        } else {
          System.out.print(k+"^"+pk);
          f=f.multiply(BigInteger.valueOf(k).pow(pk));
        }
      }
    }
    return f;
  }
    
  public static void main(String... args) {
    for(int i=2; i<20; i++) {
      System.out.printf("%d! = ", i);
      BigInteger f1=f(i);
      System.out.printf(" = %d\n", f1);
    }
  }
 }

E isso produz o seguinte:

2! = 2 = 2
3! = 2*3 = 6
4! = 2^3*3 = 24
5! = 2^3*3*5 = 120
6! = 2^4*3^2*5 = 720
7! = 2^4*3^2*5*7 = 5040
8! = 2^7*3^2*5*7 = 40320
9! = 2^7*3^4*5*7 = 362880
10! = 2^8*3^4*5^2*7 = 3628800
11! = 2^8*3^4*5^2*7*11 = 39916800
12! = 2^10*3^5*5^2*7*11 = 479001600
13! = 2^10*3^5*5^2*7*11*13 = 6227020800
14! = 2^11*3^5*5^2*7^2*11*13 = 87178291200
15! = 2^11*3^6*5^3*7^2*11*13 = 1307674368000
16! = 2^15*3^6*5^3*7^2*11*13 = 20922789888000
17! = 2^15*3^6*5^3*7^2*11*13*17 = 355687428096000
18! = 2^16*3^8*5^3*7^2*11*13*17 = 6402373705728000
19! = 2^16*3^8*5^3*7^2*11*13*17*19 = 121645100408832000

É muito mais interessante que um fatorial recursivo simples, com if ou sem.

Fatorial revisitado II

Uma propriedade interessante dos números surgiu nas minhas investigações do fatorial. O número de vezes que um número divide seus múltiplos entre duas potências suas consecutivas é igual à primeira potência menos um mais o expoente dessa primeira potência. Bastante intuitivo, eu penso.

Entre 2ⁿ e 2ⁿ⁺¹, por exemplo, temos os múltiplos 2ⁿ+2, 2ⁿ+4, 2ⁿ+6, e assim por diante. Cada um desses números pode ser dividido por uma potência de 2. E a soma dos expoentes é 2ⁿ-(1+n).

Tomemos outro exemplo com 5. Entre 5¹ e 5² temos os seguintes múltiplos de 5: 10 (2*5); 15 (3*5); e 20 (2*2*5). A soma dos expoentes de 5 é 3, que é igual a 5-2, ou, 5ⁿ-(1+n)=5¹-(1+1)=3.

Essa propriedade podemos usar para acelerar o cáculo do fatorial. Infelizmente, ainda precisamos manter o método anterior para calcular os expoentes de cada primo em cada múltiplo posterior à última potência anterior a n (quando estivermos calculando n!).

Então, o algoritmo ficou divido em 3 partes:

1. Para cada primo, marcar seus múltiplos menores que n+1;
2. Para cada potência de cada primo p, calcular p^m-(1+m);
3. Para os múltiplos de p superiores à última potência inferior a n, calcular os expoentes de p.

Em Java, montei o seguinte:

  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) {
        //Marcar todos os múltiplos
        for(int j=i+i; j<m; j+=i) {
          p[j]=-1;
        }
        //Calcular os expoentes entre potências consecutivas
        int k=i;
        int power=1;
        for(; k*i<=m; k*=i) {
          p[i]+=k-power-1;
          p[i]+=power;
          power++;
        }
        //Calcular os expoentes para os múltiplos que seguem a última potência
        if(k<m) {
          p[i]+=power;
          for(int l=k+i; l<m; l+=i) {
            p[i]+=in(i, l);
          }
        }
      }
    }
    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;
  }

O mais surpreendente é que funciona.

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.