I've been working on a line of Polynomial Expanders for a while: ex. (x^3+4x)-(5x+6)*(2x+3)=x^3-23x-10x^2-18.

But the one I've spent some time on has one major problem. Speed. Several polynomials take 50-60 seconds to expand out. I can post the full code if necessary. I think the biggest bottleneck is decoding/encoding the polynomials into natural form. Any thoughts?


Lbl IN
Input ("Polynomial: ",Str1
While T=startTmr
For(Z,1,3 //goes through operations: *+-
   For(Q,1,length(Str1)-1//parses string one char at a time.
      If Q<length(Str1 //for safety
         If sub(Str1,Q,1)="(
            If sub(Str1,Q,1)=")
               If sub(Str7,Z,1)=sub(Str1,Q+1,1
                  2:prgmZFUNCT //translate polynomial
                  |LD->|LPOLY1//store temp poly storage into Poly1
                  inString(Str1,"(",Q+1->Y//get next polynomial start
                  inString(Str1,")",Q+1->X//get next polynomial finish
                  2:prgmZFUNCT//translate 2nd one
                  If Str9=sub(Str7,Z,1//is the operation the correct one?
                     Disp "--------------------------
                     If Str9="-"// is the operation subtraction?
                     If Str9="+"//is it addition?
                        If Str9="*"//multiplication
                           3:prgmZFUNCT//multiply routine
                     4:prgmZFUNCT//combine polynomial routine
                     " ->Str3
                     If W!=1
                     9:prgmZFUNCT//turn list back into polynomial routine
                     If not(U) and X=length(Str1
                        7:prgmZFUNCT//turn list into nicer polynomial and output
                        Disp Str8
                        Disp "Done!
                        Pause "Sec="+toString(startTmr-T
                        Stop//yer done
                        If X!=length(Str1
If the polynomials are of high degree, you could try Fast Fourier transform to multiply them.
I don't think FFT algorithms are effective until the numbers reach several hundred digits. I'm not sure what the bottleneck is, but it sounds reasonable that it is turning polynomials from lists to strings.

One tip: String access takes O(n) time where n is the position in your string. So if your string is really long (200+ characters) it may be faster to save the short substring that you're working with, instead of individually accessing dozens of characters near the end. I don't know if this can help.
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 UTC - 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