my dog learned polymorphism*
The moose likes Beginning Java and the fly likes Polynomials and Hashing Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of OCA/OCP Java SE 7 Programmer I & II Study Guide this week in the OCPJP forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Polynomials and Hashing" Watch "Polynomials and Hashing" New topic
Author

Polynomials and Hashing

John Lockheart
Ranch Hand

Joined: Oct 13, 2006
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

Joined: Oct 13, 2006
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

Joined: Oct 13, 2006
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

Joined: Jun 01, 2007
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

Joined: Oct 13, 2006
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

Joined: Jun 01, 2007
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

Joined: Oct 13, 2006
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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Polynomials and Hashing