Login [Register]
Don't have an account? Register now to chat, post, use our tools, and much more.
Pre-note: this is in regard to a Polynomial Math utility, that I am revising. The older version utilized a string-parsing algorithm that was painfully slow, in that it manually pulled out every character without prejudice and figured out the coefficients that way.

Obviously, I'd rather not have the same algorithm for this in the new version. I came up with some ideas for a faster parser that I'd like to run by whomever has the time to comment.

1. For breaking the string into terms in the polynomial...


Code:
inString (Str0, "+") --> LPLUS
inString (Str0, "-") --> LMINUS
augment (LPLUS, LMINUS) --> LSIGNS
// LSIGNS is the positions of all + or - signs
// dim (LSIGNS) + 1 == number of terms, not including terms that have a value of 0 (and are thus omitted in the typed function)
SortA (LSIGNS) --> LSIGNS
augment( {1}, LSIGNS ) --> LSIGNS
augment( LSIGNS, length (Str0) ) --> LSIGNS

** we should now have a list consisting of the first spot in the string, all +'s or -'s, and the last term. We can use that to parse the string.



2. For getting the coefficient out:

** Set X equal to 1, then do ' expr(String) ' on that part. 1 to any power evaluates to 1. 1 times the coefficient is the coefficient. Is that pretty fool-proof?

3. For getting the exponents out:

** Not exactly sure what to do, but can't I set X > 1, evaluate ax^b, then do some sort of log( on that to get the exponent?

4. The last thing I need is a way of compensating for a term that is omitted. Like if we go from x^4 straight to x^2, we need a way of putting in a 0 for the coefficient of x^3. Not sure how to do this, using the above system.
Can you share what your old algorithm/code as well so I can see why it was slow?
http://www.cemetech.net/programs/index.php?mode=file&id=818

That is the path to the latest upload. There is no source, but feel free to open the .8xp in a viewer of your choice. The string --> list parser goes from Lbl 99 to If H=1:Goto 33. The list --> string parser goes from Lbl RR to the end.
Apparently Rebol (and Red) has an amazing approach to parsing that is supposedly better than regular expressions.

This is because the "grammar" can contain code, and because the language is homoiconic (i.e. code and data are made of the same structure *at runtime*), that code can modify the parsing rules *as* they are executing.

http://www.red-lang.org/2013/11/041-introducing-parse.html
Can't you find the coefficients of a degree-N polynomial by just evaluating it at N+1 points and doing Lagrange interpolation? I forgot exactly how to do this, but there's a fairly simple method that involves DeltaList(.
ACagliano wrote:
Pre-note: this is in regard to a Polynomial Math utility, that I am revising. The older version utilized a string-parsing algorithm that was painfully slow, in that it manually pulled out every character without prejudice and figured out the coefficients that way.

Obviously, I'd rather not have the same algorithm for this in the new version. I came up with some ideas for a faster parser that I'd like to run by whomever has the time to comment.

1. For breaking the string into terms in the polynomial...


Code:
inString (Str0, "+") --> LPLUS
inString (Str0, "-") --> LMINUS
augment (LPLUS, LMINUS) --> LSIGNS
// LSIGNS is the positions of all + or - signs
// dim (LSIGNS) + 1 == number of terms, not including terms that have a value of 0 (and are thus omitted in the typed function)
SortA (LSIGNS) --> LSIGNS
augment( {1}, LSIGNS ) --> LSIGNS
augment( LSIGNS, length (Str0) ) --> LSIGNS

** we should now have a list consisting of the first spot in the string, all +'s or -'s, and the last term. We can use that to parse the string.



2. For getting the coefficient out:

** Set X equal to 1, then do ' expr(String) ' on that part. 1 to any power evaluates to 1. 1 times the coefficient is the coefficient. Is that pretty fool-proof?

3. For getting the exponents out:

** Not exactly sure what to do, but can't I set X > 1, evaluate ax^b, then do some sort of log( on that to get the exponent?

4. The last thing I need is a way of compensating for a term that is omitted. Like if we go from x^4 straight to x^2, we need a way of putting in a 0 for the coefficient of x^3. Not sure how to do this, using the above system.

I actually ended up recreating a thing like this that can utilize a buncha stuff (multivariate polynomial multiplication, subtraction, and adding, anyone?)

But use two approaches for storing the polynomials. Not to be advertising or anything for my own utility programs or anything...
First I pull out the different variables it contains, then parse it term by term in the form {coefficient for term, var 1, var 2... var n} where n is the number of different variables. I concatenate the different terms of each list. I then use my list of strings program to store the toString of each list in a list entry, to make it easier to pull out each polynomial.

My list of strings program is here: https://www.cemetech.net/programs/index.php?mode=file&path=/84pce/basic/programs/StringtoList.zip

Anyway if you want me to give you the commented source of that I can. I actually wanted to thank you for giving me the idea for this in the first place and good luck with your algorithm!
  
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
Page 1 of 1
» All times are GMT - 5 Hours
 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

 

Advertisement