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!
Best Answer
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.