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
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
Thank you in advance
Jihad Haddad (Denmark)
Prev by Date:
Next by Date:
Re: ReadList question
Previous by thread:
Next by thread:
Re: Minimize number of mulitplications