/************************************************* 
* Evaluation of a polynomial by Horner's method  *
*  AMAT-2120 / Fall 2005 /Asst4, Q.A2		 *
*  Author: Sergey Sadov (instructor)		 *
*  Date: November 21, 2005			 *
**************************************************/  

/* This program uses C++'s `new' operator and should be 
   compiled with g++ compliler 
 */  

#include <stdio.h>
#include <stdlib.h> /* needed for `atof` conversion function */

#define _DEBUG  /* Enables debugging output */
     /* Comment out if want to disable it */

/**************************************************** 
*  Question (as posted)
*
*  Write a C program that evaluates the given polynomial 
*   p(x)=a_0+a_1 x+...+a_n x^n
*  at the given value of x.
*  The values of n (the degree), x (the argument) and the 
*  coefficients a_0,..., a_n should be provided by the user.
*  It is up to you to decide which form of communication 
*  with users your program will employ: interactive input, 
*  command line arguments or input from a file.
*  Use an array to store the coefficients a_k. 
*****************************************************/ 

/****************************************************
*  Implementation note
*
*  This program reads in the coefficients from the command
*  line and asks for the value of x interactively.
*  This way, the user doesn't need to re-type the coefficients
*  every time anew, since the previous command line can be
*  invoked by pressing Esc-K (or up-arrow on some computers).
******************************************************/

int main(int argc, char* argv[])
{
  int N; /* degree of the polynomial P */
  double * a; /* array of coefficients, to be allocated dynamically */
  double x;  /* the argument, to be read in from terminal */
  double p;  /* the accumulator and storage for result */ 
  
  int i; /* loop counter */
  double tmp; /* auxiliary variable to store intermediate results */
  
  if(argc<2) /* Printing online manual */
  { 
    printf("This program computes the value  P(x)=a0+a1*x+...+aN*x^n,\n"); 
    printf("where the coefficients a0,...aN should be provided as command line arguments\n.");
    printf("The degree N of the polynomial P is determined automatically\n");
    return(1); /* If no command line arguments are given, quit */
  }
       
  N=argc-2; /* Why -2? If argc==2, then there is one CLA
             (not counting the program name, which is always argv[0])
             That CLA must be a0.
	     The polynomial is then a constant and its degree is 0
	    */
  #ifdef _DEBUG /* Debugging output */
    printf("Degree of P is %d\n",N); 
  #endif

 /*  We don't have to check whether N>0 here: it will be so
  *  automatically if we reach this point.
  *  Neither should we check whether N isn't extra huge,
  *  since it is impossible to have a command line of unimaginable
  *  size 
  */
      
   /* Allocating storage for coefficients */
   a=new double[N+1]; 
     /* Why +1? Again, it is easy to figure out considering
        the simplest case, when degree N=0, --- in this case
        we still have one=N+1 coefficient */

  #ifdef _DEBUG /* Debugging output */
    printf("Array of size %d allocated at address %d\n",N+1, a); 
  #endif

 /*------------ DATA INPUT ---------------------------*/
  
  /*  Reading in values from the command line 
   *  There are N+1 values to be read, which correspond
   *  to the coefficeints a[0],a[1],...,a[N]  
   */ 
   
   for (i=0; i<=N; i++)
   {
     tmp=atof(argv[i+1]);  /* first numeric CLA must be argv[1],
                              because argv[0] is program name */
     
     #ifdef _DEBUG /* Debugging output */
       printf("i=%d, Current CLA=%s, value=%lf\n", 
                  i,        argv[i+1],     tmp);
     #endif
      
     a[i]=tmp;  /* putting CLA converted to num.value in array   */
                /* No index shift: first value is placed to a[0] */  
   } /* end of command line reading loop */
   
   /* Confirming the polynomial */
   
   printf("The polynomial to be evaluated:\n");
   for (i=0; i<=N; i++)
   {
     /* Polynomial is printed in the form:
       #*x^0 + #*x^1 + #*x^2 ... + #*x^N,
       where # runs over a[0]...a[N]
      */ 
      printf("%lf*x^%d", 
              a[i],  i);
      if(i<N) 
        printf(" + ");  /* plus sign between two monomials */  	      
   }
   printf("\n");
   
   /* Asking the user for a value of x */
   printf("Please enter a value for x: ");
   
   scanf("%lf", &x);  
  
   #ifdef _DEBUG
     printf("scanf received x=%lf\n",x);
   #endif   
     
 /*------------ COMPUTATION ---------------------------*/
 /*  At this stage, we have the values a[0],..a[N] in the
  *  array `a' and the value x in variable `x'.
  */ 
  
 /*------------------------------------------------ 
  *  Horner's Method:
  *   P(x)=a[0]+x*(a[1]+x*(a[2]+x*(.....+x*a[N]))....)))
  *  
  *  In terms of a recurrence relation:
  *    
  *   new_value_of_accumulator = a[current_index]
  *  			       +x * old_value_of_accumulator
  *   
  *  The recurrence begins at the innermost level;
  *  	 initial value of acumulator=0
  *  	 and index=N.
  *  	
  *  First update will be
  *  	  
  *  	  new_value= a[N]+x*0  =>  result=a[N].
  *    
  *  Next update:
  *    
  *  	  new_value=a[N-1]+x*a[N]
  *  	  
  *  Then:
  *    
  *  	 new_value=a[N-2]+x*(a[N-1]+x*a[N])
  *  	    
  *  etc.
  *  Last value of index to be processed is 0.
  *--------------------------------------------*/       
  
  p=0; /* initializing accumulator */
  for (i=N; i>=0; i--)
  {
    tmp=a[i]+x*p;
     #ifdef _DEBUG
       printf("In Horner's loop: i=%d, old_value=%lf, ",i,p);
       printf("current_coef=%lf, new_value=%lf\n", a[i],tmp);
     #endif
     
    p=tmp; /*assigning new value to accumulator */   
  }
  
 /*------------ OUTPUT ---------------------------*/
  printf(" Result: P(%lf)=%lf\n", x,p);
  return(0);
}