#include <stdio.h>
#define MINUS_INFINITY -1 /* Any invalid (negative) degree will suffice */
#define MAX_DEGREE 100 /* We are interested in polynomials of max degree 100 */
#define POLY_SIZE 102 /* We need 102 int cells, 101 for storing the coefficients, one more for the degree */
#define DEGREE_INDEX 101 /* The degree is stored in the highest array position */
typedef int poly[POLY_SIZE]; /* Data structure poly is defined for enhanced readability */
void polyInit ( poly f )
{
f[DEGREE_INDEX] = MINUS_INFINITY;
}
void polyCompact ( poly f )
{
int d, i;
d = MINUS_INFINITY;
for (i=f[DEGREE_INDEX]; i>=0; i--) {
if (f[i] != 0) { d = i; break; }
}
f[DEGREE_INDEX] = d;
}
void polyScan ( poly f )
{
int d, i;
printf("Enter degree : ");
scanf("%d",&d); printf("%d\n",d);
if (d<0) polyInit(f);
else if (d > MAX_DEGREE) {
printf("Error: I can not handle that big polynomials\n");
return;
} else {
f[DEGREE_INDEX] = d;
for (i=d;i>=0;i--) {
printf("Enter coefficient of X^%d : ",i);
scanf("%d",&f[i]); printf("%d\n",f[i]);
}
polyCompact(f);
}
}
void polyPrint ( poly f )
{
int d, i;
polyCompact(f);
if (f[DEGREE_INDEX] == MINUS_INFINITY) {
printf("0");
return;
}
d = f[DEGREE_INDEX];
for (i=d;i>=0;i--) if (f[i] != 0) {
if (i>0) {
if (f[i]>1) printf("%s%d",(i==d)?"":"+",f[i]);
else if (f[i]==1) printf("%s",(i==d)?"":"+");
else if (f[i]==-1) printf("-");
else printf("%d",f[i]);
if (i==1) printf("X"); else printf("X^%d",i);
} else {
if (f[i]>0) printf("%s%d",(i==d)?"":"+",f[0]);
else printf("%d",f[0]);
}
}
}
int polyEval ( poly f , int n )
{
int d, i, retval;
d = f[DEGREE_INDEX];
if (f[d] == MINUS_INFINITY) return(0);
else {
retval = f[d];
for (i=d-1;i>=0;i--) retval = retval * n + f[i];
return(retval);
}
}
int polyComp ( poly f , poly g )
{
int i;
polyCompact(f);
polyCompact(g);
if (f[DEGREE_INDEX]!=g[DEGREE_INDEX]) return(1);
for (i=f[DEGREE_INDEX];i>=0;i--) if (f[i]!=g[i]) return(1);
return(0);
}
void polyCopy ( poly h , poly f )
{
int i;
polyCompact(f);
h[DEGREE_INDEX] = f[DEGREE_INDEX];
for (i=f[DEGREE_INDEX];i>=0;i--) h[i] = f[i];
}
void polyAdd ( poly h , poly f , poly g )
{
int d, d1, d2, i;
polyCompact(f);
polyCompact(g);
d1 = f[DEGREE_INDEX];
d2 = g[DEGREE_INDEX];
if (d1 == 0) { polyCopy(h,g); return; }
if (d2 == 0) { polyCopy(h,f); return; }
if (d1>=d2) {
d = d1;
for (i=d2+1;i<=d1;i++) g[i] = 0;
} else {
d = d2;
for (i=d1+1;i<=d2;i++) f[i] = 0;
}
h[DEGREE_INDEX] = d;
for (i=d;i>=0;i--) h[i] = f[i] + g[i];
polyCompact(h);
}
void polyMul ( poly h , poly f , poly g )
{
int d, d1, d2, i, j;
polyCompact(f);
polyCompact(g);
d1 = f[DEGREE_INDEX];
d2 = g[DEGREE_INDEX];
if ( (d1 == MINUS_INFINITY) || (d2 == MINUS_INFINITY) ) {
h[DEGREE_INDEX] = MINUS_INFINITY;
return;
} else {
poly hh;
d = d1 + d2;
if (d > MAX_DEGREE) {
printf("The product is too big.\n");
return;
}
hh[DEGREE_INDEX] = d;
for (i=d;i>=0;i--) hh[i] = 0;
for (i=d1;i>=0;i--) for (j=d2;j>=0;j--) hh[i+j] += f[i] * g[j];
polyCopy(h,hh);
}
}
void polyDerive ( poly h , poly f )
{
int i;
polyCompact(f);
if (f[DEGREE_INDEX] <= 0) {
h[DEGREE_INDEX] = MINUS_INFINITY;
return;
}
h[DEGREE_INDEX] = f[DEGREE_INDEX] - 1;
for (i=0;i<=h[DEGREE_INDEX];i++) h[i] = (i+1)*f[i+1];
}
int main ()
{
int i,j,val;
poly f,g,h,p,q;
f[DEGREE_INDEX] = 7;
f[0] = f[2] = f[3] = f[4] = f[5] = f[6] = 0;
f[1] = -1; f[7] = 1;
printf("Evaluating the polynomial f(X) = "); polyPrint(f); printf("\n");
for (i=1;i<=7;i++) {
val = polyEval(f,i);
printf("f(%d) = %d, f(%d) rem 7 = %d\n",i,val,i,val%7);
}
printf("\n");
f[DEGREE_INDEX] = 8;
f[0] = f[1] = f[2] = f[3] = f[5] = f[6] = f[7] = 0;
f[4] = -1; f[8] = 1;
printf("Evaluating the polynomial f(X) = "); polyPrint(f); printf("\n");
for (i=1;i<=8;i++) {
val = polyEval(f,i);
printf("f(%d) = %d, f(%d) rem 8 = %d\n",i,val,i,val%8);
}
printf("\n");
f[DEGREE_INDEX] = 0; f[0] = 1;
g[DEGREE_INDEX] = 1; g[0] = g[1] = 1;
for (i=1;i<=10;i++) {
polyCopy(p,f);
polyMul(f,f,g);
printf("(X+1)^%d = ",i); polyPrint(f); printf("\n");
polyDerive(h,f);
printf("((X+1)^%d)' = ",i); polyPrint(h); printf("\n");
for (j=0;j<=p[DEGREE_INDEX];j++) p[j] *= i;
printf("%d(X+1)^%d = ",i,i-1); polyPrint(p); printf("\n");
printf("Comparison result = %d\n\n",polyComp(p,h));
}
printf("Verification of the product formula:\n");
printf("Reading f(X):\n"); polyScan(f);
printf("Reading g(X):\n"); polyScan(g);
polyMul(h,f,g);
printf("f(X) = "); polyPrint(f); printf("\n");
printf("g(X) = "); polyPrint(g); printf("\n");
printf("f(X)g(X) = "); polyPrint(h); printf("\n");
polyDerive(h,h);
printf("(f(X)g(X))' = "); polyPrint(h); printf("\n");
polyDerive(p,f); /* p <- f' */
polyMul(p,p,g); /* p <- p * g */
polyDerive(q,g); /* q <- g' */
polyMul(q,f,q); /* q <- f * q */
polyAdd(p,p,q); /* p <- p + q */
printf("f'(X)g(X)+f(X)g'(X) = "); polyPrint(p); printf("\n");
printf("Comparison result = %d\n",polyComp(p,h));
}
[Course home] [Home]