/****************************************************************************
                                lgstar.cpp
 ****************************************************************************
File Name : $Source$
Project   : 605.421 
Revision  : $Revision$
State     : $State$
Programmer: John E. Boon, Jr Copyright (c) 2003 John E. Boon, Jr  
                          (Work in Progress)
Program Description: 
Program Unit Notebook :  There is no separate documentation for this program. 
Program Goals         :  This program implements the iterated logarithm 
   function. The program is a command-line DOS program.  It prompts the student
   for a non-negative number, then computes the log*n for that number.
References:
   1. Thomas H. Cormen, Lieserson,Charles E., and Rivest, Ronald L., 
   Introduction to Algorithms. Cambridge, MA: The MIT Press, 1990. (page 36). 
Reusability Keywords  : algorithmic growth iterated log
Software Metrics (computed by RSM version 6.01):
  Function: main
  Complexity   Param 0       Return 1      Cyclo Vg 1       Total        2
  LOC 10       eLOC 9        lLOC 8        Comment 2        Lines       11

  Function: lg
  Complexity   Param 1       Return 1      Cyclo Vg 1       Total        3
  LOC 7        eLOC 6        lLOC 5        Comment 16       Lines       11

  Function: iterated_log
  Complexity   Param 1       Return 1      Cyclo Vg 2       Total        4
  LOC 13       eLOC 11       lLOC 9        Comment 13       Lines       13
Runtime Environment
Runtime Environment:
  Platform            : Intel PentiumPro/Windows 2000 (Service Pack 2)
  Compiler Used       : gcc version 3.3 (djgpp)
  Compilation Switches: 
  Memory Required     : 
  Math co-processor   : PentiumPro 
Input Files Needed    : none
Temporary Files Needed: none
Output Files Needed   : none
Exception Handlers    : 
  Condition Checked   : input value <= 0
  Handling Process    : none - program terminates (uses an assertion)
Updates Log           : $Log$
Header Version        : BOON-05-26-2003-GNU-CVS
 ***************************************************************************
                                lgstar.cpp
 **************************************************************************/

#include <iostream>
#include <cmath>
#include <cassert>
using namespace std;

int iterated_log(long int);
// note that the gpp_libc.202 has function log2 in math.h
double lg(double x);

/************************* MAIN PROGRAM BODY ******************************/
/**************************************************************************/
int main (void) {
   int lg_star_value;
   long int n;

   cout << "Enter the non-negative number for which to compute lg* (n > 1):\t";
   cin  >> n;
   assert(n > 0);
   lg_star_value = iterated_log(n);
   cout << "lg* of " << n << " is " << lg_star_value << endl;
   return 0;
}
/**************************************************************************/
/************************* MAIN PROGRAM BODY ******************************/

/**************************** lg ******************************************
 lg: Compute the base 2 logarithm of a double type input.
 Method Signature: function: {real} -> {real}
    domain function ::={x member of real | x > 0}
 Method Plans : Using the change of base formula and the standard header
    functions for base 10 logs, compute the base 2 log of a number.
 Precondition Axioms    :  x > 0
 Postcontdition Axioms  :  2^lg(x) = x
 Parameters: double x value for which the base 2 logarithm is needed
 Returns   : double base 2 logarithm of the input number
 Exception Handlers     : 
  Condition Checked     :
  Handling Process      :
 **************************************************************************/
double lg (double x){
  double lg_value;
  // apply the change of base formula
  // log base b(a) = log base c(a)/log base c(b) 
  assert(x > 0);
  // the intermediate solution could be computed and an assertion made
  // that the intermediate solution was a valid value for the lg
  lg_value = log(x)/log(2.0);
  assert( (x - pow(2.0,lg_value)) < 0.0001);
  return (lg_value);
}
/**************************** lg ******************************************/

/**************************** iterated_log *********************************
 iterated_log: Compute the iterated logarithm of an integer type input.
 Method Signature: function: {int} -> {int}
    domain function ::={x member of int | x > 0}
 Method Plans : Count the number of times the base 2 log of the input number
    can be taken.  Stop when i = 0, the base case or the base 2 log of the 
    current value is undefined.
 Precondition Axioms    :  n > 1
 Postcontdition Axioms  :  lg*n > 0
 Parameters: long int n input number
 Returns   : int iterated log, lg*n, of the input number
 Exception Handlers     : 
  Condition Checked     :
  Handling Process      :
 **************************************************************************/
int iterated_log(long int n) {
  int i;
  double lg_star;
  assert(n > 1);
  i = 0;
  lg_star =(double) n;
  while (lg_star > 0) {
      i++;
      lg_star = lg(lg_star);
  }
  assert (i-1 > 0);
  return (i-1);
}
/**************************** iterated_log   ******************************/

/**************************************************************************
                              lgstar.cpp      
 **************************************************************************/