Como calcular o piso de um logaritmo

Este capítulo é um pequeno exercício de cálculo de logaritmos (mais exatamente, 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.

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.

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⌋:

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

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

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); 
}

★ 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; 
}

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;

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;

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;

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;    
}

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:

(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. Resumindo, temos

Exercícios 2

Prove os dois invariantes da primeira versão (aquela das multiplicações sucessivas por 2) da função lg.
Quais os invariantes da segunda versão (aquela das divisões sucessivas por 2) da função lg? Use os invariantes para mostrar que essa versão está correta.
Escreva uma versão recursiva da função lg.

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; 
}

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 log₁₀ R e R? Escreva uma função recursiva que receba um número inteiro estritamente positivo N e devolva o teto de log₁₀ N.

Um programa completo

O pequeno programa C abaixo imprime uma tabela de valores do piso do logaritmo na base 2. O programa aplica a função lg que discutimos acima às potências de um número B. Mais exatamente, dados números naturais B e K, o programa calcula lg (B¹), lg (B²), … , lg (B^K).

// 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

Executar o programa com B igual a 2, como acabamos de fazer, é um bom teste da função lg porque é fácil ver se a resposta está correta.

Exercícios 3