# Evaluating a polynomial

You are given a polynomial of degree n. The polynomial is of the form

P(x) = an · xn + an-1 · xn-1 + … + a0

where the ai‘s are the coefficients. Given an integer x, write a program that will evaluate P(x).

You are provided with a function named power( ) that takes two positive integers x and y and returns xy. If y is 0, the function returns 1.

The prototype of this function is

int power(int x, int y);


INPUT:

• Line 1 contains the integers n and x separated by whitespace.
• Line 2 contains the coefficients an, an-1, …, a0 separated by whitespace.

OUTPUT:

A single integer which is P(x).

CONSTRAINTS:

The inputs will satisfy the following properties. It is not necessary to validate the inputs.

1 <= n <= 10
1 <= x <= 10
0 <= ai <=10


My code

#include<stdio.h>

int power(int x, int y);

int main()
{

int n,x,a[11],i; unsigned long long int sum=1;
scanf("%d%d",&n,&x);
if(n<1 || n>10) return 0;
if(x<1 || x>10) return 0;

for(i=0;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]< 0 || a[i]>10) return 0;
}
for(i=0;i<n;i++)
{

sum+=power(x,n-i)*a[i];
}
printf("%llu",sum);

return 0;
}

int power(int x, int y)
{
int result = x,i;

if(y == 0) return 1;
if(x < 0 || y < 0) return 0;

for(i = 1; i < y; ++i)
result *= x;

return result;
}

• Do you know about Horner's method? Commented Mar 27, 2014 at 18:11

1. Recommend a uniform and more indented style. E.g.

for(i=0;i<n;i++)
{
sum+=power(x,n-i)*a[i];
}

2. Both a[11] and if(... n>10) rely on the same value. Also to avoid undocumented magic numbers, consider the following (also the same for x and a[]):

#define n_MAX (10)
#define n_MIN (0)
int a[n_MAX + 1];
if(n<n_MIN || n>n_MAX) return 0;

3. unsigned long long int sum serves little value in protecting against numbers larger than INT_MAX as power() is the most likely candidate to overflow. (Strictly speaking, it is not even known that LLONG_MAX is greater than INT_MAX.) So if you want a larger range, re-write power() as unsigned long long power(int x, int y), otherwise leaving sum as int is OK.

Else suggest for marginal range improvement:

sum += (unsigned long long) power(x,n-i) * a[i];

4. BTW: should not it be:

unsigned long long int sum = 0;  //( 0 not 1)

5. Note: Stated objective says "It is not necessary to validate the inputs.". Still I like the testing you have done. Possible that the final reviewer (teacher?) may object to unneeded code. Could wrap in an #if DEBUG macro...

6. Faster way to do power()

7. See no reason for x<0 test in if(x < 0 || y < 0) return 0;. Could be

if (y < 0) return 0;

8. Do power() with unsigned rather than int as " function named power( ) that takes two positive integers x and y".

9. @Constructor comment leads to an excellent suggestion. Calculate sum with a loop that does the below. No need for a power function. Running sum can be unsigned long long and code gets great range. Its faster & simple.

// sum = (((a[n]*x + a[n-1])*x + a[n-2])*x + .... )*x + a[0];

// Something like
unsigned long long sum = 0;
for (int i=n; i>=0; i--) {
sum *= x;
sum += a[i];
}

10. Lastly, even the array a is not needed:

#include<stdio.h>
int main() {
int n;
unsigned x, a;
unsigned long long sum = 0;
scanf("%d%u", &n, &x);
while (n-- >= 0) {
scanf("%u", &a);
sum *= x;
sum += a;
}
printf("%llu", sum);
return 0;
}


You can solve this problem without using a power function. However, you can optimize your POW(x,y) to O(logn) using Divide and conquer approach,

 A^n = A^(n/2) * A^(n/2) if n is even
= A^(n/2) * A^(n/2) * A if n is odd

int power(int x, unsigned int y)
{
int temp;
if( y == 0)
return 1;
temp = power(x, y/2);
if (y%2 == 0)
return temp*temp;
else
return x*temp*temp;
}


A few suggestions:

• Whitespace (formatting) makes the code more readable: be especially careful with indentation; and don't waste vertical space with too many empty lines because you want to see the whole function on your limited-size screen)
• Don't declare variables before you assign a value to them. Declaring all your variables at the top of the function was necessary in old-style C but is no longer required.
• You don't need the a[11] array.
• You don't need to write the power function because the specifications say, "You are provided with a function ..."
• You don't need to validate your input (normally you should; but the specifications which you quoted for this problem say that you needn't: and you should usually read and obey the specifications).
• The biggest possible value of xn is 1010 for which you'll need a more-than-32-bit integer:
• Is this is a trick question, or an mistake by whoever wrote the specs?
• Is the power function (which returns int) implicitly working with 64-bit integers?
• Do you need to define your own version of the power function using int64_t?
• If you want to declare an explicitly-64-bit integer it's called int64_t.

If your compiler doesn't support 64-bit arithmetic you can implement it yourself but that makes the code a bit more complicated.

The following is FYI my attempt to do this problem in minimum/cleanest lines of code:

int main()
{
// Line 1 contains the integers n and x separated by whitespace.
int n, x;
scanf("%d%d", &n, &x);

int64_t sum = 0;
for (int i = 0; i <= n; ++i) {
// Line 2 contains the coefficients an, an-1, ..., a0 separated by whitespace.
int a;
scanf("%d", &a);
sum += a * power(x, n - i);
}

// Use PRId64 defined in <inttypes.h> to print int64_t
// https://stackoverflow.com/a/9225648/49942
printf("%" PRId64, sum);
return 0;
}


You may agree that my version is more readable than yours; partly because it's shorter.

I added comments which describe the problem being solved (by copying them from the specification).