4
$\begingroup$

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!

Improve this question
$\endgroup$
1
  • 5
    $\begingroup$ 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?) $\endgroup$
    – Igor Rivin
    Commented Dec 29, 2011 at 10:45

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • 6
    $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Commented Dec 29, 2011 at 13:38
  • $\begingroup$ @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. $\endgroup$
    – dimaK
    Commented Dec 29, 2011 at 14:14
  • 2
    $\begingroup$ @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. $\endgroup$
    – Igor Rivin
    Commented Dec 31, 2011 at 21:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .