|polynomial evaluation in GF(2) and common subexpression elimination email@example.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 firstname.lastname@example.org (drizzle) (2005-06-23)|
|Re: polynomial evaluation in GF(2) and common subexpression eliminatio email@example.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)|
|Date:||21 Jun 2005 13:57:10 -0400|
|Keywords:||arithmetic, optimize, question|
|Posted-Date:||21 Jun 2005 13:57:10 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
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
Do you have a good reference for "common subexpression elimination"
(applied to polynomial evaluation preferably)?
Do you have any advice?
Return to the
Search the comp.compilers archives again.