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

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

Return to the comp.compilers page.
Search the comp.compilers archives again.