quarta-feira, 27 de maio de 2015

Conversão de base sem ifs

Já perdi a conta do número de vezes que tive que enfrentar pequenas séries durante entrevistas de emprego. E sempre tive medo de que minha solução, mesmo sendo verdadeira, não fosse considerada pelo entrevistador.
Por exemplo, se um candidato fosse apresentado a "2,3,4", 82000 seria uma resposta perfeitamente razoável para o próximo elemento da série. Essa é a série de números que podem ser escritos usando apenas os dígitos 1 e 0 na enésima base e também em todas as anteriores.
Por exemplo, 4 na base 4 é 10, na base 3 é 11, na base 2 é 100.
O número 82000 até a base 5 tem as seguintes formas:
    • Em base 2 = 10100000001010000;
    • Em base 3 = 11011111001;
    • Em base 4 = 110001100;
    • Em base 5 = 10111000;
Por essas, nunca gostei desses exercícios como prova, embora os curta como diversão.
Em Perl, escrevi uma pequena função para converter para uma base até 32:

{
  use integer;
  my @digits=split(//,'0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ');
  sub to_base {
    my $n=shift;
    my $base=shift;
    if($n<$base) {
      return $digits[$n];
    } else {
      return to_base($n/$base, $base) . $digits[$n%$base];
    }
  }
 }
Para ir além da base 32, bastaria adicionar novos símbolos. De qualquer forma, achei que seria mais interessante retirar a recursão e também o if.

{
  my @digits=split(//,'0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ');
  sub to_base {
    my $n=shift;
    my $base=shift;
    join '', 
      reverse 
        map { $digits[int(($n%($base**($_+1)))/($base**$_))] }
          0..int(log($n)/log($base));
  }
}
A solução advém do fato de que podemos calcular qualquer dígito sem olhar os demais e que podemos calcular quantas casas serão necessárias para uma determinada base (com log(n)/log(b), sendo n o número e b a base).

Então, temos dígitos até log(n)/log(b): de b0 até blog(n)/log(b). Para saber o valor de um dígito, tiramos o resto da divisão de n por b na potência da casa subsequente (eliminando assim, todos os dígitos à esquerda). Depois dividimos por b na potência da respectiva casa e eliminamos a parte fracionária (eliminando assim, os dígitos à direita).

A função log(), vale lembrar, produz o logaritmo natural.

Por exemplo, 167 em base 10, requer log(167)/log(10)+1 dígitos (2,222+1=3). O valor do dígitos em base 10, obtemos assim:
  1. 167 mod 1000 = 167 => 167/100 = 1;
  2. 167 mod 100 = 67 => 67/10 = 6;
  3. 167 mod 10 = 7 => 7/1 = 7.
E para base 8:
  1. 167 mod 512 (8*8*8) = 167 => 167/64 (8*8) = 2;
  2. 167 mod 64 = 39 => 39/8 = 4;
  3. 167 mod 8 = 7 => 7/1 = 7.
Mais um triunfo para a programação ifless.

quarta-feira, 20 de maio de 2015

30 anos do MSX Hotbit

Em novembro de 1985, foi lançado o Hotbit. Em dezembro, a Mesbla o vendia por Cr$3.900.000,00. Quase quatro milhões de cruzeiros. Como o dólar estava quotado a Cr$10 mil, seriam apenas US$400,00. Atualizados para 2015, seriam US$877,77.

Em 1985 foi lançado o Amiga 1000. Era uma máquina de 16 bits muito superior, mas o preço também era muito superior: US$1.295,00. De qualquer forma, os micros de 8 bits já estavam de saída quando o MSX foi lançado no Brasil.

Mesmo assim, eram máquinas com bastante potencial e a baixa penetração da informática no Brasil naquela época impediu que fossem usados como deveriam. O Reino Unido, nessa mesma década, colocou micros de 8 bits em todas as escolas primárias e secundárias.

Havia periféricos que permitiriam o Hotbit operar como uma máquina de negócios, leitor de disquetes sendo a expansão mais óbvia. Também havia expansão de memória, cartão para exibição de 80 colunas, e modem. Um Hotbit poderia, segundo a especificação, suportar até 512KB de RAM. Ou seja, era um computador realmente útil.

É uma pena que discutiu-se tanto a defasagem tecnológica gerada pela reserva de mercado, enquanto pouco se discutiu como usar a tecnologia disponível da forma mais produtiva possível. Ou de como baratear a tecnologia para que mais pessoas pudessem usá-la.