23 Jun 2005 22:03:51 -0400

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) |

From: | Hans-Peter Diettrich <DrDiettrich@compuserve.de> |

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

Return to the
comp.compilers page.

Search the
comp.compilers archives again.