Mostrando postagens com marcador Conversão entre bases numéricas. Mostrar todas as postagens
Mostrando postagens com marcador Conversão entre bases numéricas. Mostrar todas as postagens

quarta-feira, 20 de junho de 2012

De quantos bits eu preciso?

Neste post, vamos criar um algoritmo que nos diz o número de bits que são necessários para representar um dado valor inteiro. Por exemplo, na linguagem C++ o tipo de dado long int permite armazenar valores com até 31 bits além do bit de sinal. Ou seja a declaração abaixo nos permite armazenar inteiros que vão de −2147483648 a 2147483647.

long int a = 2174483647;

O algoritmo que vamos criar é semelhante a função sizeof(var) que retorna o tamanho de uma variável em bytes, no entanto nosso código retornará o tamanho mínimo em bits que é necessário para representar um valor.

A abordagem é mais uma vez "indutiva". O esquema que criaremos é semelhante ao apresentado no post que discutimos a conversão de um valor decimal para binário.

Projeto indutivo:

  • Caso base: Se o valor que será convertido for igual a 0 ou 1, então o problema está automaticamente resolvido, ou seja, precisamos de apenas 1 bit.
  • Hipótese de indução: Nós podemos assumir que já sabemos quantos são os n - 1 bits que são necessários para a nossa representação binária. Essa é a etapa mais interessante e criativa no processo indutivo =D.
  • Caso geral: Agora basta estender a solução adicionando 1 a resposta que a hipótese de indução nos deu. E assim obteremos a quantidade total de bits que são necessários para representar o valor desejado.

Agora é só escrever o código, a linguagem de programação que será utilizada é o que menos interessa. No entanto, saber "o que" deve ser feito é um pré-requisito básico para irmos a etapa seguinte, ou seja, a etapa do "como fazer". A linguagem Haskell é ótima para esse tipo de demostração, pois é puramente funcional/indutiva, e aproxima o "o que fazer" do "como fazer".

  • Implementação em Haskell
numberBits :: Int -> Int
numberBits 0 = 1
numberBits 1 = 1
numberBits n = 1 + numberBits(n `div` 2)

terça-feira, 19 de junho de 2012

Conversão de decimal para binário usando Indução

Novamente a abordagem é indutiva. O algoritmo implementará o método clássico e simples de conversão.
Idéa indutiva:
  • Caso base: Se o valor que será convertido for igual a 0 ou 1, então o problema está automaticamente resolvido.
  • Hipótese de indução: Nós podemos assumir que já temos os n - 1 bits que compõem a representação binária. Pode até parecer uma suposição absurda, mas é dessa forma que a indução trabalha =D.
  • Caso geral: Agora basta estender a solução adicionando o último bit ao final da resposta que a hipótese de indução nos deu. E assim como acontece na prova de um teorema, a utilização da hipótese de indução no passo indutivo é obrigatória.
A seguir, apresentamos algumas implementações que seguem "exatamente" a idéia mostrada acima. Notem a presença do caso base e da hipótese de indução "dec2bin(n / 2)" em todas elas.
  • Implementação em Haskell 
dec2bin :: Int -> String
dec2bin 0 = "0"
dec2bin 1 = "1"
dec2bin n = dec2bin(n `div` 2) ++ show(n `mod` 2)
  • Implementação em Python
def dec2bin(n):
  if n < 2:
    print (n),
  else:
    dec2bin(n / 2)
    print (n % 2),
  • Implementação em Java
public static void dec2bin(int n) {
    if (n < 2) {
        System.out.println(n);
    } else {
        dec2bin(n / 2);
        System.out.println(n % 2);
    }
}
  • Implementação em JavaScript
function dec2bin(a)
{
   if(a < 2)
     return a;
   else
     return dec2bin(Math.floor(a / 2)) + “” + (a % 2);
}
  • Implementação em C++
void dec2bin(int n){
   if(n < 2)
      cout << n;
   else {
      dec2bin(n / 2);
      cout << (n % 2);
   }
}
O tempo de execução do algoritmo apresentado aqui é expresso pela relação de recorrência T(n) = T(n/2) + 1.
Fazendo n = $2^k$, temos

$T(n) = T(2^{k-1}) + 1$
$T(n) = T(2^{k-2}) + 1 + 1$
$T(n) = T(2^{k-3}) + 1 + 1 + 1$
$T(n) = T(2^{k-4}) + 1 + 1 + 1 + 1$
....
$T(n) = T(2^0) + 1 + 1 + 1 + 1 + 1 + 1 +  ...  + 1 + 1$
$T(n) = k$

Como $n = 2^k$, temos que $log  n = log  2^k$ e $log  n = k$, então a complexidade do método é limitada assintoticamente pela função logarítmica. Ou seja, $T(n) = O(log  n)$.