[Date Index]
[Thread Index]
[Author Index]
Minimize number of mulitplications
*To*: mathgroup at smc.vnet.net
*Subject*: [mg23818] Minimize number of mulitplications
*From*: Jihad Haddad <jihad at imada.sdu.dk>
*Date*: Sat, 10 Jun 2000 03:00:26 -0400 (EDT)
*Organization*: UNI-C
*Sender*: owner-wri-mathgroup at wolfram.com
I am sitting in the middle of my thesis and bumped into the following
problem which I hope Mathematica has a solution for. Or maybe there
exists a package I can download that can solve it.
I can illustrate it with a simple problem, even though my problem is of
a much larger magnitude.
Multiplying two first degree polynomials (ax+b) and (cx+d) yields the
following 2nd degree polynomial: (ac)x^2 + (ad+bc)x + bd.
So to compute the second degree polynomial given the two first degree
polynomials we have to compute the three expressions (ac), (ad+bc) and
(bd). Intuitively that will take four multiplications to perform, namely
(a*c), (a*d), (b*c) and (b*d). My aim is to minimize the number of
multiplications, and in the case above, it is possible to compute the
three expressions in three multiplications. We
can find (a*c), (b*d) and (a+b)*(c+d). That is three multiplications.
But we still need the expression (ad+bc). But that is equal to
(a+b)*(c+d)-(a*c)-(b*d) which we already have computed. Note that I do
not care how many additions and subtractions I perform. That is because
multiplications are a lot more time consuming than additions or
subtractions.
Now the question is: Is there a Mathematica function that can find the
minimal number of multiplications to compute a certain number of
expressions, given the expressions?
I will be very glad to get an answer. I am in desperate need for such an
optimizing function.
Thank you in advance
Jihad Haddad (Denmark)
Prev by Date:
**Industrial Optimization**
Next by Date:
**Re: ReadList question**
Previous by thread:
**Industrial Optimization**
Next by thread:
**Re: Minimize number of mulitplications**
| |