polynomial evaluation in GF(2) and common subexpression elimination

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