|polynomial evaluation in GF(2) and common subexpression elimination firstname.lastname@example.org (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 email@example.com (drizzle) (2005-06-23)|
|Re: polynomial evaluation in GF(2) and common subexpression eliminatio firstname.lastname@example.org (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)|
|From:||Hans-Peter Diettrich <DrDiettrich@compuserve.de>|
|Date:||23 Jun 2005 22:03:51 -0400|
|Posted-Date:||23 Jun 2005 22:03:51 EDT|
> 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.
Return to the
Search the comp.compilers archives again.