Solution of Assignment 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 X
^{2}) 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)); }

- A straightforward evaluation of the polynomial at -2931
will lead to overflow during the computation of X
^{3}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); }

- 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 isRoot found : 78 Root found : 224 Root found : -303

- 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

For a cubic polynomial a root can have a maximum multiplicity of 3. So it is sufficient to consider upto the second derivative.^{(k-1)}(r)=0, f^{(k)}(r)!=0.#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

- 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]