Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
| Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
|
Страница 2 из 2 |
[ Сообщений: 20 ] | На страницу Пред. 1, 2 |
|
| Автор | Сообщение | |
|---|---|---|
| novichok |
|
|
|
Sonic писал(а): novichok писал(а): Я предлагаю новый подход к этой задаче. Не, я Вас понимаю У меня есть уже наработки по оптимизации, но они пока не столь эффективны. Я Вас просто предупреждаю сразу, что это серьезная теоретическая задача, на которую легко убить кучу времени, вряд ли она решается так "насильно".Но что и как делать - решать, конечно, Вам. Я за красивые и простые решения ). Уверен, что решение есть и простое. |
||
| Вернуться к началу | ||
| Sonic |
|
|
|
Короче, я не вижу пока явный способ переписать соотношение [math]AB=F[/math] полностью в виде системы уравнений в [math]\mathbb{Z}_2[/math] в виде битовых переменных [math]a_j,b_j,f_j[/math]
. Надо сначала суметь это сделать, а потом пытаться упрощать полученные уравнения.Т.е. Вы делаете так: [math]A=\sum\limits_{j=0}^na_j2^j, \ B=\sum\limits_{j=0}^nb_j2^j, \ F=\sum\limits_{j=0}^{2n}f_j2^j[/math] Перемножаем [math]A,B[/math], вводим обозначение [math]s_k=\sum\limits_{j=0}^ka_jb_{k-j}[/math], получаем соотношение [math]\sum\limits_{j=0}^{2n}s_j2^j=\sum\limits_{j=0}^{2n}f_j2^j[/math], но здесь [math]f_j\in\{0;1\}[/math], а [math]s_j[/math] таково, что [math]0\leqslant s_j\leqslant n[/math], т.е. [math]s_j[/math] - уже не булева переменная. И надо исхитряться. Ясно, что [math]s_j\equiv f_j \pmod 2[/math] и тогда [math]s_j=r_j+2p_j[/math], Вы пишите сложение битов, но [math]p_j[/math] - не булево, оно потенциально неограниченно при возрастании [math]n[/math]. Надеюсь, я понятно написал ![]() |
||
| Вернуться к началу | ||
| novichok |
|
|
|
Понятно. Вы главное не поняли
Вся фишка в p[i] - я смог прописать его в виде булевого выражения, как и значение s[i]. Очень много времени и сил потратил на это, а решение оказалось простым.Пересмотрите внимательно пост с примером системы уравнений. Особенно на f[1], p[1], f[2], p[2], f[3], p[3] Постараюсь пояснить на примере. Кстати все вычисления подразумевают полином Жегалкина, а не вычеты по модулю 2. Так проще. e[i]={0,1} r[3]={0,1} r[3] = e[0]+e[1]+e[2]+e[3] r[3]/2 = e[0](e[1]+e[2]+e[3])+e[1](e[2]+e[3])+e[2]e[3] [math]p\limits_{n}=\sum\limits_{i=0}^{n-1}e_{i}\sum\limits_{k=i+1}^{n}e_{k}[/math] И еще, чтобы не путаться отделите сумму бит (xor) для каждого разряда s[i] от суммы бит переноса и p[i]. Иначе есть риск запутаться и усложнить формулу. |
||
| Вернуться к началу | ||
| novichok |
|
|
|
Использовал данный рисунок при анализе умножения в двоичном виде. Возможно и вам он поможет как наглядное пособие.
![]() |
||
| Вернуться к началу | ||
| Sonic |
|
|
|
Цитата: Понятно. Вы главное не поняли Так ведь [math]p_j[/math] не является булевой переменной. Либо является (определений явных нет, потому мутно буду писать), но тогда надо аккуратно формулы выписать Вся фишка в p[i] - я смог прописать его в виде булевого выражения, как и значение s[i]. Очень много времени и сил потратил на это, а решение оказалось простым.Цитата: Пересмотрите внимательно пост с примером системы уравнений. Особенно на f[1], p[1], f[2], p[2], f[3], p[3] Ну как обычно попробую понять...Цитата: Постараюсь пояснить на примере. Кстати все вычисления подразумевают полином Жегалкина, а не вычеты по модулю 2. Так проще. Не понял. Полиномы Жегалкина - они всегда по модулю 2. Цитата: e[i]={0,1} А как [math]e_i[/math] определяются?r[3]={0,1} r[3] = e[0]+e[1]+e[2]+e[3] r[3]/2 = e[0](e[1]+e[2]+e[3])+e[1](e[2]+e[3])+e[2]e[3] [math]p\limits_{n}=\sum\limits_{i=0}^{n-1}e_{i}\sum\limits_{k=i+1}^{n}e_{k}[/math] Цитата: И еще, чтобы не путаться отделите сумму бит (xor) для каждого разряда s[i] от суммы бит переноса и p[i]. Иначе есть риск запутаться и усложнить формулу. Тоже не понял ![]() Боюсь, придется все формально выписывать. Посмотрел на рисунок: ну вот, я же говорил: [math]p_j[/math] не является булевой переменной, значит для нее не существует полинома Жегалкина (в смысле, бессмысленно говорить о полиноме Жегалкина для [math]p_j[/math]). Короче, я сейчас картинку поразбираю и сам все выпишу. Наверное... upd: на картинке в предпоследней строке надо писать [math]S_i+P_i[/math], а не дробь ![]() Вообще на картинке обычное умножение в двоичной системе счисления. В ней [math]f_j=s_j+p_j \bmod 2[/math], а [math]p_j=\left[\frac{s_j}{2}\right][/math]. Это все понятно, но как Вы это в булев вид переводите - это проблема. |
||
| Вернуться к началу | ||
| novichok |
|
|
|
Цитата: Так ведь p[i] не является булевой переменной. p[i] - содержит кол-во бит переноса для текущего разряда. информацию о кол-во нужно сохранять, чтобы корректно рассчитывать последующие разряды. ((s[i]+p[i-1])/2)(mod 2)=f[i] - так для вас привычней. вычет по модулю два от выражения суммы бит текущего разряда плюс сумма бит переноса деленное на два равно значению текущего разряда. поскольку булевой алгебре нет понятия кол-во и нет понятия деления на два, я и придумал формулы на основе XOR (исключающие или и их я называю полиномами Жегалкина) чтобы и кол-во разрядов сохранялось для последующих вычислений и чтобы все вычисления делались в двоичной системе. в приведенном примере раскрыт подход e[i] - это булева переменная + в данном примере означает ИСКЛЮЧАЮЩЕЕ ИЛИ r[3] = e[0]+e[1]+e[2]+e[3] r[3]/2 = e[0](e[1]+e[2]+e[3])+e[1](e[2]+e[3])+e[2]e[3] допустим все значения e равны 1 тогда r[3] = 1+1+1+1 = 0, а математически = 4 кол-во бит хранимой информации r[3]/2 = 1(1+1+1)+1(1+1)+1(1)=0, а математически = 2 кол-во бит хранимой информации другой пример r[3] = 1+1+1+0 = 1, а математически = 3 r[3]/2 = 1(1+1+0)+1(1+0)+1(0)=1, а математически 1. так и есть целое(3/2) = 1 рисунок помогал мне перепроверять корректность формулы я не могу записать формулу для p[15] - пятнадцатого разряда, потому что мне не хватит места в теле сообщений. такое большое выражение будет из-за рекурсии. но для 3 бит пример я привел в первых постах. |
||
| Вернуться к началу | ||
| novichok |
|
|
|
надо смотреть на p[n] не в контексте значения 0 или 1, а в контексте булевого выражения с N переменными.
|
||
| Вернуться к началу | ||
| novichok |
|
|
|
Придумал простое решение как отказаться от "тяжелой" рекурсии для вычисления выражения p[i]
|
||
| Вернуться к началу | ||
| romus |
|
|
|
Жаль автор не оставил решения. Очень надо.
|
||
| Вернуться к началу | ||
| romus |
|
|
|
В продолжение данной темы. Я понял, что автор не смог решить свою проблему. А мне надо ее решить.
f - известно надо найти a и b + = [math]\oplus[/math] = XOR Для 5 бит: f0=a0*b0 a0 и b0 - всегда равны 1 Размер битности a и b достигает 100. Методом перебора, постройкой таблиц решить данную задачу не могу. Пробовал подстановкой. Но получаются слишком сложные вложенности. Помогите решить задачу. Или, что почитать. |
||
| Вернуться к началу | ||
|
На страницу Пред. 1, 2 | [ Сообщений: 20 ] |
| Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
|---|---|---|---|---|
|
Матрица
в форуме Линейная и Абстрактная алгебра |
7 |
561 |
20 ноя 2015, 22:05 |
|
|
Матрица
в форуме Линейная и Абстрактная алгебра |
1 |
355 |
25 сен 2017, 20:09 |
|
|
Матрица
в форуме Линейная и Абстрактная алгебра |
1 |
434 |
14 июн 2019, 21:16 |
|
|
Матрица
в форуме Линейная и Абстрактная алгебра |
3 |
191 |
22 сен 2021, 20:13 |
|
| Матрица | 1 |
255 |
18 май 2015, 14:19 |
|
|
Матрица
в форуме Линейная и Абстрактная алгебра |
6 |
707 |
23 сен 2017, 18:09 |
|
|
Матрица
в форуме Линейная и Абстрактная алгебра |
1 |
336 |
03 ноя 2015, 11:51 |
|
|
Матрица
в форуме Линейная и Абстрактная алгебра |
5 |
493 |
02 янв 2017, 16:15 |
|
|
Матрица Якоби
в форуме Численные методы |
0 |
305 |
23 ноя 2016, 20:43 |
|
|
Матрица перехода
в форуме Линейная и Абстрактная алгебра |
12 |
390 |
05 ноя 2020, 16:15 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 6 |
| Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |