flat assembler
Message board for the users of flat assembler.

Index > Heap > Algorithm for algebraic expansion

Author
Thread Post new topic Reply to topic
TmX



Joined: 02 Mar 2006
Posts: 821
Location: Jakarta, Indonesia
TmX
Expanding forms like this by hand:
(2 - x)(3.1 + x)(4.2 - x)(12 + x)(9 - x)

can be very cumbersome.

Is there any efficient algorithm to do that, so I can easily know the n-th term and its coefficient?
Post 11 Aug 2009, 02:40
View user's profile Send private message Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6038
Location: Poland
MHajduk
TmX wrote:
Expanding forms like this by hand:
(2 - x)(3.1 + x)(4.2 - x)(12 + x)(9 - x)

can be very cumbersome.

Is there any efficient algorithm to do that, so I can easily know the n-th term and its coefficient?
Well... probably most efficient in your case (I guess you want to write some program to perform such task?) will be simply to fix maximal number n, expand such product of n binomials to the proper polynomial of order n and calculate needed coefficients accordingly to the previously obtained formulas.

For example, we can see how it would look in the case of n = 4 (I wrote all formulas in LaTeX because of better readability):Image
Coefficients for x^k are sums of

Image

products made of all different combinations of k coefficients a_{i} and n-k coefficients b_{j} (0 <= i, j < n).
Post 11 Aug 2009, 11:30
View user's profile Send private message Visit poster's website Reply with quote
Borsuc



Joined: 29 Dec 2005
Posts: 2466
Location: Bucharest, Romania
Borsuc
Do you mean, to do this yourself, or do you want to program one that does it for you?

If you only want to expand it, not make a program that does it, you can use this:

http://maxima.sourceforge.net/

for many other tasks Smile

_________________
Previously known as The_Grey_Beast
Post 11 Aug 2009, 19:11
View user's profile Send private message Reply with quote
TmX



Joined: 02 Mar 2006
Posts: 821
Location: Jakarta, Indonesia
TmX
Thanks MHajduc for the hint Smile

Borsuc wrote:
Do you mean, to do this yourself, or do you want to program one that does it for you?

If you only want to expand it, not make a program that does it, you can use this:

http://maxima.sourceforge.net/

for many other tasks Smile


i mean to make such program myself Smile
btw, maxima is a nice thing
maybe i should re-install it again

(and scilab for numerical things....)
Post 12 Aug 2009, 04:46
View user's profile Send private message Reply with quote
r22



Joined: 27 Dec 2004
Posts: 805
r22
@TmX algebraic expansion can be done (I believe) very simply

First we need a format to hold our initial values.
We'll use a DWORD integer for the power of X and a DWORD single fp for the scalar.

(2 - x) using this format would be...
Code:
Term1: //binomial ?
dd 2.0
dd 0; x^0 = 1, 2.0 * 1 = 2.0
dd -1.0
dd 1 ; x^1 = x, -1.0 * x = -x
    


Once we have all our terms formatted like the above we have to start expanding them.

Here's a pseudo algorithm for the expansion.
Code:
//i.e. arr1 = {2.0, 0, -1.0, 1} // (2.0 - x)

FUNCTION EXPAND arr1, arr2 RETURN new Array
retarr = new Array
FOR x = 0; x<arr1.length; x=x+2
 FOR y = 0; y<arr2.length; y=y+2
  retarr.push( arr1[x] * arr2[y] )
  retarr.push( arr1[x+1] + arr2[y+1] )
 NEXT y
NEXT x
return retarr
END FUNCTION
//you take the resulting array and use it and the next Term/[binomial?] as the arguments for the next call to EXPAND
    


After all your expansion you'll be left with an array/stack of all the expanded terms. Many will be like-terms so you'll have to loop through the array and combine them, but I'll leave you with this task.

*Disclaimer* the above algorithm popped into my head while I was reading this thread and may be completely wrong, it's not tested.
Post 12 Aug 2009, 13:07
View user's profile Send private message AIM Address Yahoo Messenger Reply with quote
r22



Joined: 27 Dec 2004
Posts: 805
r22
I'm kind of curious if TmX was able to implement algebraic expansion in FASM...
Post 17 Aug 2009, 13:41
View user's profile Send private message AIM Address Yahoo Messenger Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
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
You can attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on YouTube, Twitter.

Website powered by rwasa.