2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Произведение многочленов над Z_2 через СФЭ
Сообщение07.11.2013, 06:19 
Доброго времени суток всем!

Для решения моей задачи необходимо сделать одну из таких вещей:
Два многочлена степени $n-1$ над $\mathbb{Z}_2$. Представить их произведение через схему из функциональных элементов.
Переменные, подающиеся на вход СФЭ - просто коэффициенты многочленов.
Соответственно на выходе будет $2n$ переменных. И они будут задавать многочлен степени $2n$.
Задача состоит в том, чтобы глубина схемы была $O(\log(n))$. Соответственно, здесь надо как-то прикрутить в эту схему деревья Уоллеса.

Мои попытки решения.
Вручную расписал что будет, если перемножить два многочлена.
Соответственно пусть $a_0 + a_1x + ... a_{n}x^{n}$ и $b_0 + b_1x + ... b_{n}x^{n}$ - перемножаемые многочлены. Далее, пусть $c_0+c_1x+...+c_{2n}x^{2n}$ - полученный многочлен-произведение. Далее, я получил , что $c_i=\sum\limits_{k+l=i}a_kb_l$.
Собственно говоря, алгебраическое выражение есть (просьба на всякий случай проверить). Теперь, как это реализовать через СФЭ и при том, чтобы глубина схемы была $O(\log(n))$, как указано выше.
Интересная мысль - так как всё над $\mathbb{Z}_2$, то возможно тут можно местами умножение заменить на коньюнкцию. И как дальше использовать деревья Уоллеса? На каком этапе? (Их использование как раз поможет дать логарифмическую глубину)

Сам пробую и начинаю путаться.

Заранее спасибо!

 
 
 
 Posted automatically
Сообщение07.11.2013, 08:46 
Аватара пользователя
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

Zurabman
Приведите попытки решения задачи, укажите конкретные затруднения
Наберите все формулы и термы $\TeX$ом. Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
Вернул

 
 
 
 Re: Произведение многочленов над Z_2 через СФЭ
Сообщение08.11.2013, 00:33 
Аватара пользователя
Zurabman в сообщении #785923 писал(а):
Интересная мысль - так как всё над $\mathbb{Z}_2$, то возможно тут можно местами умножение заменить на коньюнкцию
Умножение в $\mathbb{Z}_2$ --- это и есть конъюнкция. Можно заменить его везде :)

Дерево, конечно, нужно, но не дерево Уоллеса, а все значительно проще. Переносов никаких нет, все коэффициенты занимают один бит, никаких сложностей. Вот, скажем, есть $n$ элементов $a_1,\dots,a_n\in \mathbb{Z}_2$. Как построить схему, которая вычисляет $a_1 + a_2 + \dots + a_n$ в $\mathbb{Z}_2$?

 
 
 
 Re: Произведение многочленов над Z_2 через СФЭ
Сообщение08.11.2013, 03:28 

(Оффтоп)

Цитата:
Как построить схему, которая вычисляет $a_1 + a_2 + \dots + a_n$ в $\mathbb{Z}_2$?
При $n\leq 8$ на языке си это выглядит так:
Код:
sum = (((a * 0x0101010101010101ULL) & 0x8040201008040201ULL) % 0x1FF) & 1;
т.е. за $O(1)$ операций.
http://www-graphics.stanford.edu/~seander/bithacks.html

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group