CS13002 PDS Lab, Spring 2003, Section 1/A

Solution of Assignment 1



  1. One can simply evaluate the polynomial at the given points. The third root can be obtained by exploiting the fact that the sum of the three roots is -1 (the negative of the coefficient of X2) or the fact that the product of the roots is 2697 (the negative of the constant term). The first fact implies that the third root will also be an integer. On typical computers addition and subtraction are faster than multiplication or division. So one should better use the fact involving the sum of the roots. 
    #include <stdio.h>

int main ()
{
   int a;

   a = -29;
   if (a*a*a+a*a-905*a-2697==0)
      printf("%d is a root of the given polynomial.\n",a);
   a = 31;
   if (a*a*a+a*a-905*a-2697==0)
      printf("%d is a root of the given polynomial.\n",a);
   printf("The third root of the given polynomial is %d.\n", -1 - (-29 + 31));
}


  2. A straightforward evaluation of the polynomial at -2931 will lead to overflow during the computation of X3 and may therefore lead to an erroneous result. The idea here is that one may take a factor of X out from the first three terms and evaluate a quadratic polynomial at -2931. This will not lead to an overflow. 
    #include <stdio.h>

int main ()
{
   int a = -2931;

   if (a*(a*a+2871*a-174961)+2634969==0)
      printf("%d is a root of the given polynomial.\n",a);
}


  3. Since the product of the roots is the negative of the constant term, it is sufficient to evaluate the polynomial at all the divisors (positive as well as negative) of the constant term. 
    #include <stdio.h>

int main ()
{
   int r, nroot = 0;

   for (r=1; nroot<3; r++) {
      if (5294016 % r == 0) {
         if (r*r*r+r*r-74034*r+5294016==0) {
            printf("Root found : %d\n",r);
            nroot++;
         }
         if (-r*r*r+r*r+74034*r+5294016==0) {
            printf("Root found : %d\n",-r);
            nroot++;
         }
      }
   }
}
    The output of this program is 
    Root found : 78
Root found : 224
Root found : -303


  4. If a polynomial has got multiple roots, the naïve program of Exercise 4 will be unable to find all the roots. In that case we have to evaluate the first and second derivatives of the polynomial at the root. More precisely, if f(X) is a nonconstant polynomial having a root r, then the multiplicity of r in f(X) is the positive integer k such that 
    f(r)=0, f'(r)=0, ..., f(k-1)(r)=0, f(k)(r)!=0.
    For a cubic polynomial a root can have a maximum multiplicity of 3. So it is sufficient to consider upto the second derivative. 
    #include <stdio.h>

int main ()
{
   int r, nroot = 0;

   for (r=1; nroot<3; r++) {
      if (1815937 % r == 0) {   /* The root must divide the constant term */
         if (r*r*r+r*r-28033*r-1815937==0) {   /* Evaluate f(r) */
            printf("Root found : %d\n",r);
            nroot++;
            if (3*r*r+2*r-28033==0) {          /* Evaluate f'(r) */
               printf("Root found : %d\n",r);
               nroot++;
               if (6*r+2==0) {                 /* Evaluate f''(r) */
                  printf("Root found : %d\n",r);
                  nroot++;
               }
            }
         }
         if (-r*r*r+r*r+28033*r-1815937==0) {  /* Evaluate f(-r) */
            printf("Root found : %d\n",-r);
            nroot++;
            if (3*r*r-2*r-28033==0) {          /* Evaluate f'(-r) */
               printf("Root found : %d\n",-r);
               nroot++;
               if (-6*r+2==0) {                /* Evaluate f''(-r) */
                  printf("Root found : %d\n",-r);
                  nroot++;
               }
            }
         }
      }
   }
}
    The output of this program is: 
    Root found : -97
Root found : -97
Root found : 193


  5. This program is straightforward: 
    #include <stdio.h>

int main ()
{
   double t=0,      /* Time initialized to 0 */
       dist=0,      /* Distance traversed by the ant */
       slen=10;     /* Length of the string */

   while (dist < slen) {
      dist+=1;        /* Ant's move in 1 second */
      t+=1;           /* Time increases by 1 second */
      slen+=10;       /* The string stretches */
      dist*=(t+1)/t;  /* Stretching helps the ant too! */
      /* printf("After %d seconds: string length = %d cm, ant covered %f cm\n",
         (int)t, (int)slen, dist); */
   }

   printf("Ant reached the right end in %d seconds!!!\n", (int)t);
}
    The answer is 12367 seconds.

[Course home] [Home]