# Re: polynomial evaluation in GF(2) and common subexpression elimination

## Hans-Peter Diettrich <DrDiettrich@compuserve.de>23 Jun 2005 22:03:51 -0400

From comp.compilers

Related articles
polynomial evaluation in GF(2) and common subexpression elimination panneton@hotmail.com (rng) (2005-06-21)
Re: polynomial evaluation in GF(2) and common subexpression eliminatio DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2005-06-23)
Re: polynomial evaluation in GF(2) and common subexpression eliminatio drizzle76@gmail.com (drizzle) (2005-06-23)
Re: polynomial evaluation in GF(2) and common subexpression eliminatio emailamit@gmail.com (Amit Gupta) (2005-06-24)
Re: polynomial evaluation in GF(2) and common subexpression eliminatio cfc@shell01.TheWorld.com (Chris F Clark) (2005-06-26)
| List of all articles for this month |

 From: Hans-Peter Diettrich Newsgroups: comp.compilers Date: 23 Jun 2005 22:03:51 -0400 Organization: Compilers Central References: 05-06-101 Keywords: theory, optimize Posted-Date: 23 Jun 2005 22:03:51 EDT

rng wrote:

> I have a polynomial f(z) with coefficients in GF(2) that I want to
> evaluate at a point z, (an example is f(z) = z^256 + z^255 + z^2 + z
> +1). Typically, the polynomial has hundreds of non-zero coefficients.
>
> What I am looking for is a general algorithm that will reduce the
> number of additions (i.e. xors). For exemple, for f(z) = z^256 +z^255
> +z^2+z +1, I
> can write
> g(z) = z + 1
> f(z) = z^255 h(z) + z^2 + h(z).
> which is done with 3 additions instead of 4.

Here you introduce an arbitrary function, that is used to transform
the original formula. The compiler then can determine the occurence of
a (your specific) common subexpression, in the transformed formula. So
what you really want is an algorithm for finding suitable substitution
functions, e.g. by linear optimization techniques. Such an
optimization should also take into account the amount of memory,
required to hold the value of the subexpression.

> Do you have a good reference for "common subexpression elimination"
> (applied to polynomial evaluation preferably)?

IMO, with regards to compilers, a common subexpression must more or less
obviously exist in an expression, so that the compiler can determine the
(literal) occurence of such an subexpression.

An expression of (a+b)*(a+b) obviously contains the common
subexpression (a+b), that will be found by every optimizing
compiler. A transformation of a^2-b^2 into (a+b)*(a-b) instead is most
probably out of the optimization capabilities of an compiler.

DoDi

Post a followup to this message