21 Jun 2005 13:57:10 -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: | "rng" <panneton@hotmail.com> |

Newsgroups: | comp.compilers |

Date: | 21 Jun 2005 13:57:10 -0400 |

Organization: | http://groups.google.com |

Keywords: | arithmetic, optimize, question |

Hi,

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.

In my problem, the z is in fact a linear operator "A" that is applied

to a bit vector and that returns a bit vector of the same size. So,

A^n correspond to applying the operator n times. I want to compute

f(A)v, where v is a bit vector. The linear operator is very cheap to

compute, but the additions (i.e. xors) are very expensive since the bit

vectors are typically of size 20000 bits.

I have read that I can do this with a method called "common

subexpression elimination", but I cannot find a reference that clearly

explains it.

Do you have a good reference for "common subexpression elimination"

(applied to polynomial evaluation preferably)?

Do you have any advice?

Thank you.

Francois.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.