/*
 * classical.c
 * File revision 0
 * Multiply two polynomials the classical way.
 * (c) 2000 Jacob Lundberg, jacob@chaos2.org
 */


#include <sys/time.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdio.h>


/* Are we in profiling mode (timer output only)? */
#define  PROFILE                0


int _mul(double *coeff, double *left, double *right, int degree);
int _out(double *coeff, int degree);
int _nxt(int val);


int main(int argc, char **argv) {
/*
 * main()
 * Slurp up the args, run the multiplication, print the result.
 */

   int counter, degree;
   double *coeff, *left, *right;
   struct timeval before, after;

   /* There must be at least a degree and two polynomials. */
   if(argc < 4) {
      printf("The minimal input is `classical 0 x y'\n");
      return(1);
   }

   /* Arg 1 is specified to be the degree of the polynomials. */
   degree = atoi(argv[1]);

   /* Make sure the degree given is consistant with the input. */
   if(2 * degree + 2 != argc - 2) {
      printf("Arguments disagree (degree != size).\n");
      return(1);
   }

   /* Allocate the memory for the arrays (and zero it). */
   left  = (double *)malloc(2 * _nxt(degree) * sizeof(double));
   right = (double *)malloc(2 * _nxt(degree) * sizeof(double));
   coeff = (double *)malloc(2 * _nxt(2 * degree) * sizeof(double));

   /* Zero the arrays. */
   for(counter = 0; counter < 2 * _nxt(degree); ++counter)
      left[counter] = 0;
   for(counter = 0; counter < 2 * _nxt(degree); ++counter)
      right[counter] = 0;
   for(counter = 0; counter < 2 * _nxt(2 * degree); ++counter)
      coeff[counter] = 0;

   /* Read the left polynomial into its input array. */
   for(counter = 0; counter <= degree; ++counter)
      left[counter] = atof(argv[1 + 1 + degree - counter]);

   /* Read the right polynomial into its input array. */
   for(counter = 0; counter <= degree; ++counter)
      right[counter] = atof(argv[1 + 2 + 2 * degree - counter]);

   /* Do the multiplication. */
   gettimeofday(&before, NULL);
   _mul(coeff, left, right, degree);
   gettimeofday(&after, NULL);

   /* Print the results. */
   if(PROFILE)
      printf("Two polynomials of degree %i multiplied in %lu microseconds.\n", degree,
            1000000 * (after.tv_sec - before.tv_sec) + after.tv_usec - before.tv_usec);
   else
      _out(coeff, 2 * degree);

   free(left);
   free(right);
   free(coeff);

   return(0);

}


int _mul(double *coeff, double *left, double *right, int degree) {
/*
 * _mul()
 * Multiply two polynomials.
 */

   int inner, outer;
   int top = 2 * degree;

   /* The classical iterative method is really really simple: */
   for(outer = 0; outer <= top; ++outer)
      for(inner = 0; inner <= outer; ++inner)
         coeff[outer] += left[inner] * right[outer - inner];

   return(0);

}


int _out(double *coeff, int degree) {
/*
 * _out()
 * Display a polynomial.
 */

   int degcnt = degree;

   for(; degcnt >= 0; --degcnt)
      if(coeff[degcnt])
         printf("%gx^%i ", coeff[degcnt], degcnt);

   printf("\n");

   return(0);

}


int _nxt(int val) {
/*
 * _nxt()
 * Find the next smallext value in 2^n : n memb of I.
 */

   int counter = 0;

   if(val <= 0)
      return(0);

   --val;
   for(; val; ++counter)
      val >>= 1;

   return(1 << counter);

}