Login [Register]
Don't have an account? Register now to chat, post, use our tools, and much more.
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.

» 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