Win a copy of Functional Reactive Programming this week in the Other Languages forum!

# Polynomials and Hashing

John Lockheart
Ranch Hand
Posts: 115
In my class polynomial I want to take a string, rearrange the characters in order, then use those ascii values to describe a polynomial. Ex) "John" would become hJno => 104, 74, 110, 111..and turns into the polynomial 104x^3 + 74x^2 + 110x + 111. Not even sure where to begin...I got this so far.

John Lockheart
Ranch Hand
Posts: 115
p.s. I have to use Horner's method of evaluating polynomials...

Copied from the book i'm teaching myself out of:

Horner's rule is a method for evaluating a polynomial efficiently. Suppose the polynomial is:

p(x) = x4 - 2x3 + 3x2 - 4x + 5

It should be evaluated in the following way:
p(x) = ((((1)x - 2)x + 3)x - 4)x + 5

John Lockheart
Ranch Hand
Posts: 115
This is what I got so far, sometimes I get the right answer and sometimes I don't...it can be off by +1, -1, or with larger strings sometimes more...

Bill Cruise
Ranch Hand
Posts: 148
Since you're using the variable counter to index into the char array, shouldn't it (counter) be initialized to 0 instead of 1 as you have it?

If this isn't the problem, can you post a few more inputs that I can test with? Ideally you should post a few Strings that work and a few that don't work, along with your expected output for each. (So those of us trying to help don't have to go through and calculate them by hand. )

John Lockheart
Ranch Hand
Posts: 115
No it shouldn't be the problem. Making counter start at 1, makes certain that when result = (int)charArray[0] <= first entry; and I add ((int)charArray[counter]) <= will always be an entry after first (counter++), I'm always adding the next value and not the same value charArray[0] to itself.

Following tests with evalPoly(1):

John => hJno => 104 + 74 + 110 + 111 = 399(correct & program output)
abc => 97 + 98 + 99 = 294(correct) => 295(program output)
abcd => 97 + 98 + 99 + 100 = 1466(correct) => 1459(program output)

Bill Cruise
Ranch Hand
Posts: 148
Here's code that mostly works.

It's not going to work with the input "John" as you've described though. The problem is the way you're sorting the char array. "John" sorts to "Jhon". In ASCII, capital letters come before lower case letters.

The problem in your original code was that you were raising the input x to the power of the term. Horner's rule doesn't do that.

John Lockheart
Ranch Hand
Posts: 115
Thanks, I didn't realize that the sorting issue for upper and lower case letters. I don't think that should matter much, i need to expand the class and all words are going to be converted to lower case anyway, so words like John and john aren't hashed differently. I guess now that i look more closely at the material I was reading about using Horner's method I was going about it the wrong way. I was trying to translate a polynomial expression into a statement as opposed to writing an statement that evaluates a polynomial.