You are here:

# C++/pseudocode for evaluating polynomials

Question
I have this homework on evaluating a polyomial in its general form. For example, if you are given x^2 + 2x + 1, with x=1, the output should be 4. We were asked to do a pseudocode and a c++ program on it. I am having problems with the pseudocode. I do not know how to modify this pseudocode I have created; it seems like it does not give its correct value.

1   procedure PolyEval (An, An-1, ..., Ao, x)
2    if n=0 then
3       return (Ao)
4     end if
5    return (PolyEval (An * Xn) + PolyEval (An-1 * Xn-1) )
6     end PolyEval

this is just a pseudocode. I am still thinking what to modify, especially in line 5. I used recursive algorithm. Can you help me? thank you very much.

Strictly speaking this is not a C++ question. However I can see the sort of things you are doing wrong, so here are some hints. Note that I will _not_ fix you pseudo code for you - that is your job!

First, where does n come from? It is not passed in and it is not defined locally nor shown to be defined globally (a bad idea anyway).

On the other hand assuming n to be passed in and to represent the current number of coefficients then the recursion termination clause seems good, although it will possibly not be the value you expect a fixed version.

Where you are going wrong is the case where we have not terminated. First Xn, Xn-1 : what are these you have only one thing with x in its name: the x parameter passed in.

This is then obviously wrong. So what are you trying to achieve from x?

Well, x, x^2, x^3, x^4 (I am using ^ to mean "to the power"). What do these actually mean?

Well:

x   is equivalent to x
x^2 is equivalent to x * x
x^3 is equivalent to x * x * x
x^4 is equivalent to x * x * x * x

etc.

Now these terms are also multiplied by their coefficients so the full terms are:

A0       is equivalent to A0
A1 * x   is equivalent to A1 * x
A2 * x^2 is equivalent to A2 * x * x
A3 * x^3 is equivalent to A3 * x * x * x
A4 * x^4 is equivalent to A4 * x * x * x * x

Etc.

Now a thing to note about the above expansions is that all the multiplications to produce the higher powers of x (squared or greater) do not have to happen at the same time. You can do one multiplication per recursive call.

However you do have to calculate the multiplication for each of the (remaining) terms except term 0 during each recursive call, which implies a loop of some kind.

You will also need to store and pass these intermediate results between calls. Hint: you are passing the coefficients already (A0, A1 etc.).

Now what to return?

Well how about looking at it this way:

Return the result for coefficient 0 plus everything else.

The "everything else" would be the next recursive call to PolyEval.

So this gives the non-terminating case as:

- update partial term results
- return term 0 plus evaluation of remaining terms

Now I think that should give you enough to be going on with.

By the way you might like to consider a non-recursive implementation, unless using recursion is a specific requirement for your assignment. It may well be faster and possibly easier to implement.

C++

Volunteer

#### Ralph McArdell

##### Expertise

I am a software developer with more than 15 years C++ experience and over 25 years experience developing a wide variety of applications for Windows NT/2000/XP, UNIX, Linux and other platforms. I can help with basic to advanced C++, C (although I do not write just-C much if at all these days so maybe ask in the C section about purely C matters), software development and many platform specific and system development problems.

##### Experience

My career started in the mid 1980s working as a batch process operator for the now defunct Inner London Education Authority, working on Prime mini computers. I then moved into the role of Programmer / Analyst, also on the Primes, then into technical support and finally into the micro computing section, using a variety of 16 and 8 bit machines. Following the demise of the ILEA I worked for a small company, now gone, called Hodos. I worked on a part task train simulator using C and the Intel DVI (Digital Video Interactive) - the hardware based predecessor to Indeo. Other projects included a CGI based train simulator (different goals to the first), and various other projects in C and Visual Basic (er, version 1 that is). When Hodos went into receivership I went freelance and finally managed to start working in C++. I initially had contracts working on train simulators (surprise) and multimedia - I worked on many of the Dorling Kindersley CD-ROM titles and wrote the screensaver games for the Wallace and Gromit Cracking Animator CD. My more recent contracts have been more traditionally IT based, working predominately in C++ on MS Windows NT, 2000. XP, Linux and UN*X. These projects have had wide ranging additional skill sets including system analysis and design, databases and SQL in various guises, C#, client server and remoting, cross porting applications between platforms and various client development processes. I have an interest in the development of the C++ core language and libraries and try to keep up with at least some of the papers on the ISO C++ Standard Committee site at http://www.open-std.org/jtc1/sc22/wg21/.

Education/Credentials