Logaritmos

Este capítulo é um pequeno exercício de cálculo de logaritmos (mais precisamente, logaritmos truncados). O exercício é relevante porque a análise do consumo de tempo de muitos algoritmos envolve a função logarítmica.  O cálculo de logaritmos serve de pretexto para exercitar o conceito de piso de um número real e o conceito de invariantes de um algoritmo iterativo.

Aproveitaremos também a ocasião para exibir um programa completo em C, com bom leiaute, boa documentação, e boa organização.

Piso do logaritmo na base 2

O logaritmo na base 2 de um número N é o expoente a que 2 deve ser elevado para produzir N.  O logaritmo na base 2 de N é denotado por log N.  É claro que log N só está definido se N é estritamente positivo.

Problema: dado um inteiro estritamente positivo N, calcular o piso de log N.

O piso de log N, usualmente denotado por  ⌊log N, é aproximadamente igual ao número de bits na representação binária de N.  A seguinte tabela mostra alguns valores de log N (aproximados até a terceira casa decimal) bem como os correspondentes valores de ⌊log N:

N    log N   ⌊log N
10 3.322 3
100 6.644 6
1000 9.966 9

Eis uma função que resolve nosso problema:

// A função lg recebe um inteiro N > 0 
// e devolve o piso de log N, ou seja,
// o único inteiro i tal que
// 2^i <= N < 2^(i+1).

int lg (int N)
{  
   int i, n;
   i = 0;
   n = 1;
   while (n <= N/2) {
      n = 2 * n;
      i += 1;
   }
   return i;    
}

O código poderia também ser escrito com divisões sucessivas no lugar das multiplicações sucessivas:

int lg (int N)
{  
   int i = 0;
   int n = N;
   while (n > 1) {
      n = n / 2;
      i += 1;
   }
   return i;    
}

Como a expressão  n / 2  só envolve objetos do tipo int, a operação de divisão é inteira. Assim, o valor da expressão é  n / 2⌋.

Exercícios 1

  1. Critique a seguinte versão da função lg.  Ela usa as funções log10 e floor da biblioteca math:
    #include <math.h>
    int lg (int N) {  
       double x;
       x = log10 (N) / log10 (2);
       return floor (x); 
    }
    
  2. ★ Mostre que código abaixo corre o risco de produzir resultados errados em virtude de overflow aritmético.
    int lg (int N) {  
       int i = 0, n = 1;
       while (n <= N) {
          n = 2 * n;
          i += 1; 
       }
       return i-1; 
    }
    
  3. Verifique que a seguinte versão alternativa da função lg está correta:
       int i = 0;
       for (int n = 2; n <= N; n = 2*n) 
          i += 1;
       return i; 
    
  4. Critique a seguinte versão alternativa da função lg:
       int achou = 0, i = 0, n = 1;
       while (!achou) {
          n *= 2;
          i += 1;
          if (n > N) achou = 1;
       }
       return i - 1;
    
  5. Critique a seguinte versão alternativa da função lg:
       if (N == 1) return 0;
       if (N == 2) return 1;
       int i = 2; 
       int n = 4;
       while (n <= N) {
          n = 2 * n;
          i += 1; 
       }
       return i - 1;    
    
  6. Eficiência.  Critique a seguinte versão alternativa da função lg. Ela calcula, explicitamente, a maior potência de 2 que não passa de N.
    int potencia (int i) { 
       int p = 1;
       for (int j = 1; j <= i; ++j) p = 2 * p;
       return p;
    }
    int lg (int N) {
       for (int i = 0; potencia (i) <= N; ++i) {}
       return i - 1;    
    }
    
  7. Logaritmos na base 10.  Escreva uma função que calcule o piso do logaritmo na base 10 de um número.

Análise da função lg

Considere o processo iterativo da primeira versão da função lg (aquela das multiplicações sucessivas por 2). Digamos que o início de cada iteração fica imediatamente antes do teste n <= N/2.  Então as seguintes relações entre as variáveis n, i e N valem no início de cada iteração:

n = 2i   e   nN.

(Verifique!)  Essas relações são, portanto, invariantes.  A validade das invariantes no início da última iteração garante que o algoritmo está correto. De fato, quando  n > N/2

e portanto  i = ⌊log N.  Assim, ao devolver i, a função lg cumpre o que prometeu.

Exercícios 2

  1. Prove os dois invariantes da primeira versão da função lg.
  2. Quais os invariantes da segunda versão da função lg (aquela das divisões sucessivas por 2)? Use os invariantes para mostrar que essa versão está correta.
  3. Escreva uma versão recursiva da função lg.
  4. O que faz a função abaixo? Escreva o invariante que explica a função.
    int tlg (int N) {  
       int i = 0, n = 1;
       while (n < N) {
          n *= 2;
          i += 1;
       }
       return i; 
    }
    
  5. O que é o teto de um número real r?  Se R é um número estritamente positivo, qual a relação entre o teto de  log10 R  e  R?  Escreva uma função recursiva que receba um número inteiro estritamente positivo N e devolva o teto de log10 N.

Um programa completo

A função lg que discutimos acima pode ser usada para imprimir uma tabela do piso do logaritmo na base 2.  Segue um pequeno programa C que imprime uma tal tabela. Dados quaisquer números naturais BK, o programa imprime o valor de lg (Bi) para i variando de 1K.

Este exercício é um pretexto para exibir um programa completo com bom leiaute, boa documentação e organização, bem como para ilustrar o uso de bibliotecas de funções e a entrada de dados pela linha de comando.

// Programa: pisolog
// Autor: PF
// Data: 2017-06-29
//
// Este programa imprime uma tabela dos valores do
// piso de log N para N = B^1, B^2, ..., B^K.
// Como de hábito, log é o logaritmo na base 2.
// Os valores de B e K são especificados na linha 
// de comando: para executar o programa com B = 10 
// e K = 6, por exemplo, diga 
// 
//     ./pisolog 10 6
//
// Vamos supor que B e K são inteiros, com B >= 2
// e K >= 1.
//////////////////////////////////////////////////


// Protótipos de funções.
// O programa usa as funções externas printf (da
// biblioteca stdio) e strtol (da biblioteca 
// stdlib).

#include <stdio.h>
#include <stdlib.h>
int lg (int);

// Comunicação com o usuário. 
// Os dois argumentos na linha de comando, B e K,
// devem ser menores que INT_MAX (veja a interface
// limits.h).

int main (int numargs, char *arg[])
{ 
   int B = strtol (arg[1], NULL, 10);
   int K = strtol (arg[2], NULL, 10);
   int N = 1; 
   printf ("\n          N  lg(N)\n\n");
   for (int i = 1; i <= K; ++i) {
      N = B * N;
      printf ("%11d %5d\n", N, lg (N));
   }
   return EXIT_SUCCESS;
}
 

// A função lg recebe um inteiro N > 0
// e devolve o piso de log N.

int lg (int N)
{  
   int i = 0, n = N;
   while (n > 1) {
      i += 1;
      n /= 2;
   }
   return i;    
}


// Exemplo com B = 10 e K = 6:
// $ ./pisolog 10 6
//
//           N  lg(N)
//
//          10     3
//         100     6
//        1000     9
//       10000    13
//      100000    16
//     1000000    19
// $ 

Se você compilar o programa e depois digitar   ./pisolog 2 30   no terminal, receberá como resposta a tabela

          N  lg(N)

          2     1
          4     2
          8     3
         16     4
         32     5
         64     6
        128     7
        256     8
        512     9
       1024    10
       2048    11
       4096    12
       8192    13
      16384    14
      32768    15
      65536    16
     131072    17
     262144    18
     524288    19
    1048576    20
    2097152    21
    4194304    22
    8388608    23
   16777216    24
   33554432    25
   67108864    26
  134217728    27
  268435456    28
  536870912    29
 1073741824    30

(Executar o programa com B igual a 2 é um bom teste porque é fácil ver se a resposta está correta.)

Exercícios 3

  1. ★ Como se sabe, log Bi = i log B para quaisquer Bi.  Poderíamos pensar em reescrever o programa pisolog da seguinte maneira: calcule b = lg(B) e depois imprima b, 2*b, … , K*b.  Isso produziria uma tabela correta?
  2. ★ Ao calcular as potências de B em main, o programa corre o risco de produzir resultados errados em virtude de um overflow aritmético. (Isso acontece, por exemplo, se B vale 2 e K vale 31.) Modifique o código de main de modo que a execução seja interrompida antes que ocorra um overflow.
  3. Se R é um número estritamente positivo, qual a relação entre o piso de log10 RR?   Escreva uma função recursiva que receba um número inteiro estritamente positivo m e devolva o piso de log10 m.