Algorithms Design   |   C language   |   Index

Logarithms

This chapter is a small exercise in the calculation of logarithms (more precisely, truncated logarithms). The exercise is relevant because the analysis of the time consumption of many algorithms involves the logarithmic function. 

This chapter serves as an excuse to introduce the concept of floor of a real number and of the invariants of an iterative algorithm.  We shall also take this opportunity to show a well-organized C program, with good layout and good documentation.

Floor of base 2 logarithms

The logarithm in base 2 of a number N is the exponent to which 2 must be raised in order to produce N.  The base 2 logarithm of N will be denoted by log N.  Of course, log N is defined only if N is strictly positive.

Problem: Given a strictly positive integer N, compute the floor of log N.

The floor of log N, usually denoted by  ⌊log N⌋, is approximately equal to the number of bits in the binary representation of N.  The following table shows some values of log N (to three decimal places) as well as the corresponding values of ⌊log N⌋:

Here is a function that solves our problem:

// The function lg receives an integer N > 0 
// and returns the floor of log N, that is,
// the only integer i such that
// 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;    
}

Instead of repeated multiplications, we can use repeated divisions:

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

Since the expression  n/2  involves only objects of type int, the division operation is integer. Hence, the value of the expression is  ⌊n / 2⌋.

Exercises 1

Analysis of the lg function

Consider the iterative process of the first version of the function lg (the one based on successive multiplications). Let's say that the starting point of each iteration lies immediately before the test n <= N/2.  Then, at the beginning of each iteration, the following relations hold between the variables n, i, and N:

n = 2ⁱ   and   n ≤ N .

(Check it!)  In other words, these relations are invariant.  The relations hold, in particular, at the beginning of the last iteration, when  n > N/2. At this time,  N/2  <  n  ≤  N,

• whence  n  ≤  N  <  2n,
• whence  2ⁱ  ≤  N  <  2ⁱ⁺¹,
• whence  i  ≤  log N  <  i+1,

and therefore  i = ⌊log N⌋.  So, by returning i, the function lg fulfills what it promised to do. We have thus shown that

lg (N)  =  ⌊log N⌋

for any positive integer N. Hence, the algorithm is correct.

Exercises 2

A complete C program

The little C program below prints a table of values of the floor of base 2 logarithms. The program applies the function  lg  discussed above to the powers of a number B. More precisely, given natural numbers B and K, the program computes  lg (B¹),  lg (B²), … , lg (B^K).

This exercise serves as an excuse to show a complete program with good layout, documentation, and organization, and it illustrates the use of function libraries and command line data input.

// Program: floorlog
// Author: PF
// Date: 2018-08-22
//
// This program prints a table of the values of the
// floor of log N for N = B^1, B^2, ..., B^K. As
// usual, log is the base 2 logarithm. To run the
// program with B = 10 and K = 6, for example, type
// 
//     ./floorlog 10 6
//
// We assume that B and K are integers, with B >= 2
// and K >= 1.
///////////////////////////////////////////////////


// Prototypes of functions.
// The program uses the functions printf (from the
// stdio library) and strtol (from the stdlib
// library).

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

// Communication with the user. 
// The two arguments on the command line, B and K,
// must be smaller than INT_MAX (see the limits.h
// interface).

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

// The function lg receives an integer N > 0 and
// returns the floor of log N.

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


// An output example for B = 10 and K = 6:
//
// $ ./floorlog 10 6
//
//           N  lg(N)
//
//          10     3
//         100     6
//        1000     9
//       10000    13
//      100000    16
//     1000000    19
// $ 

If you compile the program and then type   ./floorlog 2 30   on the terminal, the output will be

          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

Running the program for B equal to 2, as we just did, is a good test of the lg function because you can immediately see whether the output is correct or not.

Exercises 3