MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Hello to all,

I'm interested in fast algorithms for addition and multiplication of Zhegalkin polynomials. For example, let

$f_1(x_1, x_2, x_3) = 1+x_1+x_2x_3$

$f_2(x_1, x_2, x_3) = x_1+x_3$

I'd like to have a fast algorithm to find the sum

$f_3(x_1, x_2, x_3) = f_1(x_1, x_2, x_3)+f_2(x_1, x_2, x_3)=1+x_3+x_2x_3$

Google gives nothing, so I would be grateful for any useful links to any theoretical researches and/or realizations (with any program language).

Thanks in advance!

share|cite|improve this question
This question does not really make sense: What do you mean by "fast"? How do you represent your polynomials (by a list of monomials? Straight line programs? values at a set of points?) – Igor Rivin Dec 29 '11 at 10:45

If you are interested in parallel computing, the article

V. D. Malyugin, V. V. Sokolov, “Intensive logic computations”, Avtomat. i Telemekh., 1993, no. 4, 160–167 (in Russian) [English version: Automation and Remote Control, 1993, 54:4, 672–678]

may be useful.

share|cite|improve this answer

@Igor Rivin: Answering your question... Representations doesn't matter. Do you have a link to an algorithm which works with Zhegalkin polynomials represented as a set of coefficients? Please, share it with me! May be you are familiar with Python/Ruby/C++/etc library which works with Zhegalkin polynomials represented by strings? Please, give me a link to the web site!

"Fast" means "faster that the obvious direct calculation". For example, FFT allows us to multiply two polynomials $F(x)P(x)$ over $R$ faster that the obvious direct calculation. I need something like this for Zhegalkin polynomials.

P.S. "This question does not really make sense" sounds not really polite, IMHO. Thanks for your answer :)

share|cite|improve this answer
Representation absolutely does matter. For instance, if you represent the polynomials by circuits (or straight-line programs), then addition and multiplication can be done in constant time by including one new gate. OTOH, in a suitable dense representation, addition of polynomials amounts to pointwise addition (xor). FFT can be used also for multiplication of multivariate polynomials, Google is your friend. Finally, please, do not post comments as answers. – Emil Jeřábek Dec 29 '11 at 13:38
@Emil: Thanks for your answer :) @All: Ok, probably it was a mistake to post my question to this site. This site is for math gurus, obviously. For nubs like me, it is just time wasting :) Thanks to all. – dimaK Dec 29 '11 at 14:14
@Emil is absolutely correct. The point is also that dense polynomial representation is essentially useless in most cases, since the memory requirements blow up so fast, which is why the choice of representation has to be a part of the question. As for "not really polite", I was being truthful. If I were a paid consultant, I might have phrased my comment (very slightly) differently. – Igor Rivin Dec 31 '11 at 21:47

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.