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?

Code:
``` ClrHome Lbl IN Input ("Polynomial: ",Str1 startTmr->T While T=startTmr End T+1->T ClrHome 0:prgmZFUNCT 0->W 2->K "*+-->Str7 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       Then          If sub(Str1,Q,1)="(          Then             Q->W             Else             If sub(Str1,Q,1)=")             Then                If sub(Str7,Z,1)=sub(Str1,Q+1,1                Then                   sub(Str1,W+1,Q-W-1->Str2                   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                   sub(Str1,Y+1,X-Y-1->Str2                   2:prgmZFUNCT//translate 2nd one                   sub(Str1,Q+1,1->Str9                   If Str9=sub(Str7,Z,1//is the operation the correct one?                   Then                      "="+Str1->Str5                      8:prgmZFUNCT                      Disp "--------------------------                      K+1->K                      |LD->|LPOLY2                      If Str9="-"// is the operation subtraction?                      Then                         length(Str4->theta                         For(A,1,dim(|LPOLY2)/theta                            ~|LPOLY2(1+theta(A-1)->|LPOLY2(1+theta(A-1                         End                         "+->Str9                      End                      If Str9="+"//is it addition?                      Then                         augment(|LPOLY1,|LPOLY2->|LPOLY1                         Else                         If Str9="*"//multiplication                         Then                            3:prgmZFUNCT//multiply routine                            L6->|LPOLY1                         End                      End                      4:prgmZFUNCT//combine polynomial routine                      " ->Str3                      0->U                      If W!=1                      Then                         1->U                         Str3+sub(Str1,1,W-1->Str3                      End                      9:prgmZFUNCT//turn list back into polynomial routine                      Str3+"("+Str8+")->Str3                      If not(U) and X=length(Str1                      Then                         7:prgmZFUNCT//turn list into nicer polynomial and output                         Disp Str8                         Disp "Done!                         Pause "Sec="+toString(startTmr-T                         Stop//yer done                         Else                         If X!=length(Str1                         Then                            Str3+sub(Str1,X+1,length(Str1)-X->Str3                         End                         sub(Str3,2,length(Str3)-1->Str1                      End                      1->Q                   End                End             End          End       End    End End ```
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.

»
» 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