[Date Index] [Thread Index] [Author Index]

Re: Find minimum number of operations

• To: mathgroup at smc.vnet.net
• Subject: [mg112956] Re: Find minimum number of operations
• From: Bill Rowe <readnews at sbcglobal.net>
• Date: Thu, 7 Oct 2010 03:38:31 -0400 (EDT)

On 10/6/10 at 3:17 AM, xcolwell at gmail.com (brien colwell) wrote:

>I have a set of expressions composed of literals, multiplications,
>additions, and powers. For example,

>-(-3 Bx (Ax^2 + Ay^2 - 2 Ax Bx + Bx^2 - 2 Ay By + By^2)^(3/2) +
>3 Ax^2 Ay k + 3 Ay^3 k - 8 Ax Ay Bx k + 5 Ay Bx^2 k - Ax^2 By k - 9
>Ay^2 By k + 4 Ax Bx By k - 3 Bx^2 By k + 9 Ay By^2 k - 3 By^3 k + 2
>Ax Ay Cx k - 2 Ay Bx Cx k - 2 Ax By Cx k + 2 Bx By Cx k - 2 Ax^2 Cy
>k + 4 Ax Bx Cy k - 2 Bx^2 Cy k)/(3 (Ax^2 + Ay^2 - 2 Ax Bx + Bx^2 - 2
>Ay By + By^2)^( 3/2))

For polynomials with integer exponents, the most efficient
computational method would be to use HormerForm. For example,

In[26]:= p = 11 x^3 - 4 x^2 + 7 x + 2;

In[27]:= HornerForm[p]

Out[27]= x (x (11 x-4)+7)+2

In this particular case, the number of operations is the same
per your definition above. But computing powers takes more cpu
resources than doing multiplies and additions.

>I would like to find the form for each that minimizes the number of
>operations, where each operation is either a multiplication,
>addition, or power. Is this easily done in Mathematica (7)? Also,
>just curious, what criteria does FullSimplify use to evaluate the
>"simplest form"?

Both FullSimplify and Simplify consider a form simpler if the
LeafCount decreases after a given transform is tried. Note,
=46ullSimplify will not try all possible transforms and may not
actually find a form that has a smaller LeafCount.

Look up LeafCount, FullSimplify and HornerForm in the
DocumentationCenter for more details.