рекурсия и итерация

Просто ты не знаешь матана, в этом вся проблема. Подходы со временем очень сильно меняются. Те доказательства, которыми пользовались математики полторы сотни лет назад, например, сейчас и за доказательства не считаются особо.

а те теоремы тоже устарели? Сумма квадратов катетов уже не равна квадрату гипотенузы? Да? Ну дай пруф на ютуб, я посмотрю ролик с доказательством, и пойду топится.

но для функциональных кейзов эти способы неприменимы. И сборщик тут - это как раз оптимальный алгоритм выделения памяти для данного кейза.

это верно. Осталось немного: докажи, что стратегия использования памяти в ФП сама по себе является оптимальной для существующих архитектур. А то для меня это не очевидно.

докажи это странное заключение.

А чего тут доказывать? Вся сборка состоит из обхода корней и перемещения достижимых данных. Допустим, у тебя десяток корней (преувеличим) и пара десятков элементов в дереве - значит, на все про все ты затратишь меньше сотни разыменовываний и те самые два десятка memcpy. По сравнению с тормозным маллоком - это совсем не много.

они освобождают какую-то другую память?

Нет, ту же самую. но при этом выполнение программы им останавливать не надо.

это пока сборка не запустилась, а откладывается. Да, тогда malloc медленный. Вот только работа GC всё равно только ОТКЛАДЫВАЕТСЯ.

Смотри, фишка в том, что _удаление_ информации с перемещающим сборщиком вообще не вызывает времени. Выделение - вызывает очень мало времени. Реальное время занимает компактификация - которая зависит от размера _достижимых_ данных. Другими словами, с ростом интенсивности выделения/освобождений памяти стоимость GC практически не растет. С другой стороны она растет с ростом текущей потребности памяти.

С аллокаторами все наоборот - их стоимость практически не растет с ростом потребностей в памяти, но линейна по вызываемым маллок/фри.

В ФП языках мы имеем как раз первый случай - и там GC резко выигрывают. Еще раз, фактически, алгоритм GC - это алгоритм оптимального аллокатора для подобной ситуации.

Повторяю: чудес не бывает, если ты отложил работу, то ты НЕ СДЕЛАЛ работу. Так вот, GC именно ОТКЛАДЫВАЕТ работу по наведению порядка.

Да нет, GC совершает ДРУГУЮ работу. Это другой алгоритм. И сложность у GC и у аллокаторов разная (зависит от разных параметров).

так и будет, когда твой перемещающий GC начнёт _перемещать_. Включи голову и осознай, что для этого нужно ВСЁ останавливать.

Еще раз - читай про конкурентные сборщики.

тут главное, что-бы сборка не включилась во время теста.

Тебе вопрос на засыпку - сколько будет время занимать сборка перемещающего сборщика после выполнения задачи? Правильно - 0 (точнее время, слабо отличимое от нуля, сколько-то он работать все-таки будет). Сам догадаешься почему, или тебе объяснить?

область применимости описана — когда памяти не хватает, и приходится запускать GC (или когда maloc(3) уже не справляется, и тратит слишком много времени на поиск)

Это зависит от того, чем забита память. Если данные достижимы - то времени потратится много, а если нихуя достижимых нет - то и времени нихуя затрачено не будет. Т.к. недостижимые данные в процессе сборки вообще никак не участвуют. Сборщик их не обходит, не помечает, не перемещает. Ничего с ними не делает - его для них вообще нет.

а те теоремы тоже устарели?

Теоремы не устарели. Я говорил о методах доказательства.

это верно. Осталось немного: докажи, что стратегия использования памяти в ФП сама по себе является оптимальной для существующих архитектур. А то для меня это не очевидно.

Не является. Как и стратегия дефолтных аллокаторов. Вообще говоря для каждой задачи есть определенный оптимальный способ использования памяти. И вероятность того, что он совпадет с оптимальным для данной архитектуры - около нуля (если только это не специализированный заточенный под узкую задачу девайс).

Ага, замечательно. Быстро мне определение кольца - только без подсказок из гугла!

продолжаешь пытаться навязать мне экзамен? А я тебе как раз наоборот пытаюсь предложить воспользоваться гуглом, и избавить меня от повторения очевидных вещей.

Я не знаю, какая мат. структура у тебя на часах. может Z_12, может Z_24, может N, может что еще изощреннее. Я мысли читать не умею.

ты часов не видел? 12 цифр. И да, с 24ю только хуже, ибо неоднозначностей только больше. Т.ч. считай как попроще, с 12.

Ну ради бога. Все равно все пользуются интами и довольны. Умножение и деление кстати вполне однозначны, только деление не всюду определено (только если делитель с модулем взаимно просты).

да потому-что int'ы это НЕ вычеты. Твоя изначальная предпосылка ложна. Они «вычеты» исключительно по сложению, а по умножению/делению — это конечная подобласть таки области целых. Т.е. результат умножения/деления int эквивалентен умножению/делению целых, если нет переполнения. А если есть — UB для сишечки.

Немного наоборот - делить можно всегда, кроме тех случае, когда делитель не взаимно прост с модулем.

ты ошибаешься. Всё намного хуже, если модуль — не целая степень простого числа. Проблема в том, что по модулю 12, 2*6==6*6==3*4==...==0; И ты не можешь разделить даже ноль на что угодно.

А если модуль — целая степень простого числа, то всё только хуже. Вот тебе таблица умножения по модулю 3

0*2=0
1*2=2
2*2=1

А чего тут доказывать? Вся сборка состоит из обхода корней и перемещения достижимых данных. Допустим, у тебя десяток корней (преувеличим) и пара десятков элементов в дереве - значит, на все про все ты затратишь меньше сотни разыменовываний и те самые два десятка memcpy. По сравнению с тормозным маллоком - это совсем не много.

ОК, а что такого тормозного нужно сделать моему malloc'у? Выиграть партию в преферанс?

Нет, ту же самую. но при этом выполнение программы им останавливать не надо.

это как, если у тебя скажем массив, с которым ты СЕЙЧАС работаешь наполовину в одном месте, а на другую половину — в другом?

Смотри, фишка в том, что _удаление_ информации с перемещающим сборщиком вообще не вызывает времени. Выделение - вызывает очень мало времени. Реальное время занимает компактификация - которая зависит от размера _достижимых_ данных. Другими словами, с ростом интенсивности выделения/освобождений памяти стоимость GC практически не растет. С другой стороны она растет с ростом текущей потребности памяти.

тебе просто не подходит ЭТОТ malloc(3). Используй другой, не вижу проблемы.

и избавить меня от повторения очевидных вещей.

Но ты же этих вещей не знаешь. Или не помнишь. Значит - надо повторить. А ну быстро в гугл иди!

ты часов не видел? 12 цифр. И да, с 24ю только хуже, ибо неоднозначностей только больше. Т.ч. считай как попроще, с 12.

Замечательно, 6+6=0. Дальше что?

да потому-что int'ы это НЕ вычеты.

Нет, это именно что вычеты.

Они «вычеты» исключительно по сложению, а по умножению/делению — это конечная подобласть таки области целых.

По умножению они тоже точно такие же вычеты, т.к. умножение нельзя определить иначе, не нарушив дистрибутивность, то есть тогда у тебя в интах будет ситуация, при которой a+a!=2a. Ну а операции деления, как противоположной умножению на интах просто не определено, есть только целочисленное деление с вариациями.

Т.е. результат умножения/деления int эквивалентен умножению/делению целых, если нет переполнения. А если есть — UB для сишечки.

Хохо, так ты не только начальной алгебры, но и сишки не знаешь? ub - только в случае знаковых, а вот беззнаковые как раз обязаны modulo 2^n - то есть вести себя как классы вычетов при сложении и умножении.

ты ошибаешься. Всё намного хуже, если модуль — не целая степень простого числа.

Это ты сам хуйню придумал.

Проблема в том, что по модулю 12, 2*6==6*6==3*4==...==0; И ты не можешь разделить даже ноль на что угодно.

Деление - это, по определению, умножение на обратный элемент, а не то, что ты придумал. 0/5 = 0*5^-1, например, то есть ноль, по определению нуля. У пятерки в Z_12 обратный есть (как и у любого числа взаимно простого с 12), по-этому все что угодно в этом кольце можно делить на пятерку.

Таблица умножения по модулю 7

Кольцо классов вычетов по модулю 7 является полем, да будет тебе известно (поле Галуа GF(7)). В нем можно умножать что угодно на что угодно и делить что угодно на что угодно (кроме нуля, конечно).

ну, например, в этом поле 5*6=2, 3*4=5, 6*4=3. Таблицу целиком мне лениво писать.

тебе просто не подходит ЭТОТ malloc(3). Используй другой, не вижу проблемы.

Тот маллок, который подходит, у меня уже есть - и это GC. О чем я и говорю. Если хочешь оптимального маллока для этой задачи - придется реализовать полноценный GC.

ОК, а что такого тормозного нужно сделать моему malloc'у?

В общем случае - это системный вызов, которому надо сделать очень много.

это как

Иди и гугли, как. Что гуглить я тебе указал, конкретные алгоритмы найдешь сам.

Иди и гугли, как. Что гуглить я тебе указал, конкретные алгоритмы найдешь сам.

Есть мнение, что ты сам эти алгоритмы не знаешь. Ибо не смотря на название, они не делают то, что говоришь ты. И еще, современные GC плохо работают тогда, когда мало мусора и много объектов, которые реально нужны. Особенно это все проявляется, когда речь идет хотя бы о нескольких десятках гигобайт. В то время как кастомные аллокаторы на C++ показывают себя очень хорошо. Поэтому, повторюсь, не существует оптимальных алгоритмов на все случаи жизни. Опциональный(полностью) сборщик в C++ может быть полезен, возможно, что он таки появится рано или поздно в стандарте.

Тебе вопрос на засыпку - сколько будет время занимать сборка перемещающего сборщика после выполнения задачи? Правильно - 0 (точнее время, слабо отличимое от нуля, сколько-то он работать все-таки будет). Сам догадаешься почему, или тебе объяснить?

нет, спасибо. Но меня никто не просит писать helloworld'ы, задача которых — напечатать helloworld и завершиться.

И злится не нужно. Пиши пожалуйста по-русски. Со своими друзьями будешь так общаться. Не нужно тут всем доказывать, что у тебя друзья такие тупые, что кроме ненормативной лексики ничего больше не разумеют.

Теоремы не устарели. Я говорил о методах доказательства.

а я говорил о _доказанных_ теоремах.

Не является. Как и стратегия дефолтных аллокаторов. Вообще говоря для каждой задачи есть определенный оптимальный способ использования памяти. И вероятность того, что он совпадет с оптимальным для данной архитектуры - около нуля (если только это не специализированный заточенный под узкую задачу девайс).

именно по этому аллокатор и НЕ ВХОДИТ в спецификацию C/C++. Мало того, в эту спецификацю входит возможность его ЗАМЕНИТЬ. Т.е. использовать свой malloc, или перезагрузить class::new, или даже ::new. Так, как нужно в _этой_ задаче.

А в твоих недоязычках такой возможности, увы, нет. Потому-то они никому и не нужны. Разве что в ТЗ не прописано требований по стоимости. Или это разовая задача, на решение которой ты можешь потратить пару ночей работы своего домашнего компьютера.

Но ты же этих вещей не знаешь. Или не помнишь. Значит - надо повторить. А ну быстро в гугл иди!

я оттуда не выходил. Это ты мне почему-то запрещаешь его юзать. А я — наоборот, и сам юзаю, и тебе советую. Ибо незнание != невежество. Невежество, это когда у тебя есть гугл, но ты НЕ ХОЧЕШЬ им пользоваться.

Замечательно, 6+6=0. Дальше что?

дальше то, что 0+0==1+11==2+10==...==0. Потому, что есть «ноль» — неоднозначно. Сравни с натуральными числами, в которых 0+0==0, ВСЕГДА. Из неоднозначности сложения следует неоднозначность всего остального, и до кучи — невозможность ВСЕХ обратных операций. Для обычных чисел есть только проблема с неоднозначностью умножения на ноль, из которой следует невозможность деления на ноль.

(с отрицательными числами тоже есть проблемы, но они исправимы. Например неоднозначно деление с остатком. Это не проблема, т.к. математики постулируют, что истинный остаток всегда >=0. О чём, кстати, не знают большинство архитектур, вроде x86/amd64. Однако с вычетом проблемы не устранимы, как и при делении на ноль)

Нет, это именно что вычеты.

тогда определи умножение вычетов. И сравни с тем, что есть.

По умножению они тоже точно такие же вычеты, т.к. умножение нельзя определить иначе, не нарушив дистрибутивность

ВНЕЗАПНО: в поле Галуа — можно. Вот только это ДРУГОЕ «умножение», которое например для модуля 3 даёт 2*2=1. А теперь попробуй определить «умножение» например по модулю 16, и удивись. Как не странно, дистрибутивность там работает, как и деление(исключая /0 конечно).

Ну а операции деления, как противоположной умножению на интах просто не определено, есть только целочисленное деление с вариациями.

потому-что int-ы != вычеты. А подмножество целых чисел. Ограниченное и конечное. Т.е. это такие целые, из которых вычеркнуто всё, больше INT_MAX и меньше -(INT_MAX+1). И если аргумент и/или результат выходит за диапазон, то «результат» === тоже самое UB, как и при делении на ноль. Это так в сишечке. В других ЯП обычно просто бардак, на который всем пофиг.

Хохо, так ты не только начальной алгебры, но и сишки не знаешь? ub - только в случае знаковых, а вот беззнаковые как раз обязаны modulo 2^n - то есть вести себя как классы вычетов при сложении и умножении.

пруф найди пожалуйста. Я не осилил.

ты ошибаешься. Всё намного хуже, если модуль — не целая степень простого числа.

Это ты сам * придумал.

Это тебе к Галуа с такими вопросами — он придумал. Мопед не мой.

Деление - это, по определению, умножение на обратный элемент, а не то, что ты придумал.

я ничего не придумывал. Это ты фантазируешь, что обратный эл-т у тебя один. А он один только в случае бесконечного счётного множества элементов за исключением нуля. Если множество конечно, то вопрос единственности открыт.

Кольцо классов вычетов по модулю 7 является полем, да будет тебе известно (поле Галуа GF(7)). В нем можно умножать что угодно на что угодно и делить что угодно на что угодно (кроме нуля, конечно).

ну, например, в этом поле 5*6=2, 3*4=5, 6*4=3. Таблицу целиком мне лениво писать.

а погуглить тебе тоже лениво? Вот тебе таблица умножения по модулю 256

i alpha index i alpha index i alpha index i alpha index i alpha index i alpha ind
000 001  -1   043 119 218   086 177 219   129 023 112   172 123 220   215 239 170
001 002   0   044 238 240   087 127 189   130 046 192   173 246 252   216 195 251
002 004   1   045 193  18   088 254 241   131 092 247   174 241 190   217 155  96
003 008  25   046 159 130   089 225 210   132 184 140   175 255  97   218 043 134
004 016   2   047 035  69   090 223  19   133 109 128   176 227 242   219 086 177
005 032  50   048 070  29   091 163  92   134 218  99   177 219  86   220 172 187
006 064  26   049 140 181   092 091 131   135 169  13   178 171 211   221 069 204
007 128 198   050 005 194   093 182  56   136 079 103   179 075 171   222 138  62
008 029   3   051 010 125   094 113  70   137 158  74   180 150  20   223 009  90
009 058 223   052 020 106   095 226  64   138 033 222   181 049  42   224 018 203
010 116  51   053 040  39   096 217  30   139 066 237   182 098  93   225 036  89
011 232 238   054 080 249   097 175  66   140 132  49   183 196 158   226 072  95
012 205  27   055 160 185   098 067 182   141 021 197   184 149 132   227 144 176
013 135 104   056 093 201   099 134 163   142 042 254   185 055  60   228 061 156
014 019 199   057 186 154   100 017 195   143 084  24   186 110  57   229 122 169
015 038  75   058 105   9   101 034  72   144 168 227   187 220  83   230 244 160
016 076   4   059 210 120   102 068 126   145 077 165   188 165  71   231 245  81
017 152 100   060 185  77   103 136 110   146 154 153   189 087 109   232 247  11
018 045 224   061 111 228   104 013 107   147 041 119   190 174  65   233 243 245
019 090  14   062 222 114   105 026  58   148 082  38   191 065 162   234 251  22
020 180  52   063 161 166   106 052  40   149 164 184   192 130  31   235 235 235
021 117 141   064 095   6   107 104  84   150 085 180   193 025  45   236 203 122
022 234 239   065 190 191   108 208 250   151 170 124   194 050  67   237 139 117
023 201 129   066 097 139   109 189 133   152 073  17   195 100 216   238 011  44
024 143  28   067 194  98   110 103 186   153 146  68   196 200 183   239 022 215
025 003 193   068 153 102   111 206  61   154 057 146   197 141 123   240 044  79
026 006 105   069 047 221   112 129 202   155 114 217   198 007 164   241 088 174
027 012 248   070 094  48   113 031  94   156 228  35   199 014 118   242 176 213
028 024 200   071 188 253   114 062 155   157 213  32   200 028 196   243 125 233
029 048   8   072 101 226   115 124 159   158 183 137   201 056  23   244 250 230
030 096  76   073 202 152   116 248  10   159 115  46   202 112  73   245 233 231
031 192 113   074 137  37   117 237  21   160 230  55   203 224 236   246 207 173
032 157   5   075 015 179   118 199 121   161 209  63   204 221 127   247 131 232
033 039 138   076 030  16   119 147  43   162 191 209   205 167  12   248 027 116
034 078 101   077 060 145   120 059  78   163 099  91   206 083 111   249 054 214
035 156  47   078 120  34   121 118 212   164 198 149   207 166 246   250 108 244
036 037 225   079 240 136   122 236 229   165 145 188   208 081 108   251 216 234
037 074  36   080 253  54   123 197 172   166 063 207   209 162 161   252 173 168
038 148  15   081 231 208   124 151 115   167 126 205   210 089  59   253 071  80
039 053  33   082 211 148   125 051 243   168 252 144   211 178  82   254 142  88
040 106  53   083 187 206   126 102 167   169 229 135   212 121  41   255 000 175
041 212 147   084 107 143   127 204  87   170 215 151   213 242 157
042 181 142   085 214 150   128 133   7   171 179 178   214 249  85

http://www.insidepro.com/kk/027/027r.shtml

а теперь объясни, ГДЕ ты видел ТАКОЕ умножение? В котором 2**8==29

Тот маллок, который подходит, у меня уже есть - и это GC. О чем я и говорю. Если хочешь оптимального маллока для этой задачи - придется реализовать полноценный GC.

я всё равно не понимаю, в чём проблема-то? Не можешь реализовать? Исходники твоей ракеты закрыты?

Регистровые переменные в пул не вернуть? Не используй регистровые переменные. Не используй стек. Да, на сишечке с интами и глупыми указателями не очень удобно(оператор = и всякие +- не перезагрузить, и придётся делать функции), используй C++.

В общем случае - это системный вызов, которому надо сделать очень много.

ну запроси Over9000Mb, один раз, в начале программы, и не доставай больше систему.

это как, если у тебя скажем массив, с которым ты СЕЙЧАС работаешь наполовину в одном месте, а на другую половину — в другом?

Иди и гугли, как. Что гуглить я тебе указал, конкретные алгоритмы найдешь сам.

я их без тебя и твоего гугла знаю — всё затормозить, и начать двигать туда-суда. Что в php, что в javascript'е, который в FF/Opera/IE. Потому-то это дерьмо и тормозит, и жрёт память сотнями и тысячами метров. Об этом любой школьник знает. Про вашу ынтерпрайзную java я тоже в курсе, которой нужен отдельный сервер под какой-то сраный сайт на 1К юзеров.

Опциональный(полностью) сборщик в C++ может быть полезен, возможно, что он таки появится рано или поздно в стандарте.

будь мужиком, сделай СЕЙЧАС. У тебя есть для этого все возможности. Я уже делал, там нет ничего такого уж сложного.

При поддержке компилятора будет лучше. Можно сделать как плагинчик к clang'у.

ну запроси Over9000Mb, один раз, в начале программы, и не доставай больше систему.

9000мб в стандартной ФП-программе выделяется и освобождается за время порядка секунд, постоянно.

я их без тебя и твоего гугла знаю — всё затормозить

Нет. я же сказал - гугли. Алсо, в том же эрланге, например, сборщик в каждом процессе свой, независимый. СБорка во дном процессе не останавливает другие и кроме того проходит очень быстро за счет того, что памяти процесс потребляет мало и unidirectional heap.

а погуглить тебе тоже лениво?

Зачем мне это гуглить?

Вот тебе таблица умножения по модулю 256

Это не таблица умножения по Z_256. Это поле Галуа GF(2^8). Это разные вещи. В частности, Z_256 не поле.

а теперь объясни, ГДЕ ты видел ТАКОЕ умножение? В котором 2**8==29

Так ты не умножение в поле Галуа смотри а в кольце классов вычетов.

Невежество, это когда у тебя есть гугл, но ты НЕ ХОЧЕШЬ им пользоваться.

так воспользуйся. Не будь невеждей.

дальше то, что 0+0==1+11==2+10==...==0.

Ну да. Прямо как в интах.

Сравни с натуральными числами, в которых 0+0==0, ВСЕГДА.

Ну и тут 0+0=0 ВСЕГДА.

Из неоднозначности сложения следует неоднозначность всего остального

Я не понимаю откуда ты высрал неоднозначность сложения. Оно вполне однозначно. в Z_12 6+6 = 0. Не 1, не 2, только 0.

и до кучи — невозможность ВСЕХ обратных операций.

Они вполне однозначны. Для любого элемента кольца классов вычетов определен обратный (при чем однозначно!), если элемент взаимно прост с модулем.

потому-что int-ы != вычеты.

Тебе тогда нетрудно будет привести пример, где инты - это не вычеты.

Т.е. это такие целые, из которых вычеркнуто всё, больше INT_MAX и меньше -(INT_MAX+1).

Вообще-то речь шла об unsigned, не надо подменять понятия.

пруф найди пожалуйста. Я не осилил.

http://lmgtfy.com/?q=c unsigned integer overflow

Это тебе к Галуа с такими вопросами — он придумал.

Галуа был одним из гениальнейших математиков за всю историю человечества (скорее всего даже - самым гениальным). Не надо приписывать ему придуманную тобой хуйню.

Это ты фантазируешь, что обратный эл-т у тебя один.

Он один, если взаимно прост с модулем. Если у тебя поле по простому модулю - то для любого элемента есть единственный обратный, а кольцо становится полем.

Если множество конечно, то вопрос единственности открыт.

Да нет, вполне закрыт. Точно известно, когда он есть и единственен, а когда его нет.

тогда определи умножение вычетов. И сравни с тем, что есть.

Умножение вычетов не надо определять - за меня это уже давным-давно сделали математики. Работает оно так - в кольце классов вычетов Z_n чтобы перемножить два числа надо перемножить их как натуральные, а потом взять остаток от деления на n. И это в точности то, как ведут себя инты.

И еще, современные GC плохо работают тогда, когда мало мусора и много объектов, которые реально нужны.

Да, я об этом говорил. Дело все в том что в ФП языках ситуация обратная - обычно мусора сильно больше, чем достижимых объектов.

Ибо не смотря на название, они не делают то, что говоришь ты.

Да нет, как раз то.

Регистровые переменные в пул не вернуть?

Опять ты эту хуйню несешь? Какой пул? что и куда ты собрался возвращать, дубина?

именно эта прокладка впитывает то, что из тебя вытекает. Только благодаря ей твой GC имеет нужную информацию о переменных в периметре GC. В сишечке такой прокладки нет, потому надёжное и быстрое определение утечек невозможно.

можно было бы долго объяснять, почему ты ничего в этом не понимаешь, но достаточно сказать, что есть реализации языков с GC, но без JIT. Сюрприз, да?

не нужно IRL

то есть AES IRL не используется, я правильно тебя понял?

В не поле не определено умножение и деление

умножение всюду определено в любом кольце. деление определено на обратимых элементах кольца (единицах)

Не включает и никогда не включало

каноническое вложение строится тривиальным образом

При чем тут вложение, если речь о включении?

Так ты не умножение в поле Галуа смотри а в кольце классов вычетов.

так дай мне ссылку на такое умножение. А то я не нашёл.

Ну и тут 0+0=0 ВСЕГДА.

это потому, что 2**n — допустимый модуль для построения поля Галуа. Но ведь ты его строить отказался. Ты как-то в кольце вычетов умножаешь. Вот и расскажи — КАК.

Я не понимаю откуда ты высрал неоднозначность сложения. Оно вполне однозначно. в Z_12 6+6 = 0. Не 1, не 2, только 0.

проблема в том, что есть разные разложения числа 12. 3*4 или 2*6 например. Потому, когда мы прыгаем на 12 ед. вперёд, невозможно узнать, КАК мы прыгали. Может 3 раза по 4, а может 2 раза по 6. Это и называется — неоднозначность.

Они вполне однозначны. Для любого элемента кольца классов вычетов определен обратный (при чем однозначно!), если элемент взаимно прост с модулем.

ага, а значит для элементов 0,1,2,3,4,6 для Z_12 соорудить обратный эл-т невозможно. Подумаешь — половину множество похерили...

Тебе тогда нетрудно будет привести пример, где инты - это не вычеты.

легко: в int'ах определено умножение и деление, а в вычетах — увы.

Вообще-то речь шла об unsigned, не надо подменять понятия.

да вообще-то без разницы. Пусть будет от 0 до 2*INT_MAX-1.

Умножение вычетов не надо определять - за меня это уже давным-давно сделали математики. Работает оно так - в кольце классов вычетов Z_n чтобы перемножить два числа надо перемножить их как натуральные, а потом взять остаток от деления на n. И это в точности то, как ведут себя инты.

ага. Для Z_12 получаем кучу делителей нуля, ибо 3*4==0, 2*6==0, 6*6==0, и так далее.

Ну и тут 0+0=0 ВСЕГДА.

надоело спорить. В вычетах Z_12:

1*2=2;
7*2=2;
2/2=?

можно было бы долго объяснять, почему ты ничего в этом не понимаешь, но достаточно сказать, что есть реализации языков с GC, но без JIT. Сюрприз, да?

посмотри в удалённых, я про этот «сюрприз» уже писал. Не ты один тут такой умный.

то есть AES IRL не используется, я правильно тебя понял?

нет, неправильно.

умножение всюду определено в любом кольце. деление определено на обратимых элементах кольца (единицах)

изучи смысл слова «определено». Умножение определено лишь в бесконечном поле целых и вещественных чисел, и то частично, исключая ноль.

В поле Галуа умножение тоже частично определено, но ПО ДРУГОМУ.

так дай мне ссылку на такое умножение. А то я не нашёл.

http://ru.wikipedia.org/wiki/Кольцо_вычетов#.D0.9A.D0.BB.D0.B0.D1.81.D1.81.D1...

Вот и расскажи — КАК.

Точно так же, как в подполе констант поля Галуа, представь себе. Z_n как поле изоморфна подполю констант GF(n^k),

Потому, когда мы прыгаем на 12 ед. вперёд, невозможно узнать, КАК мы прыгали.

А зачем нам это знать? При чем тут умножение?

Это и называется — неоднозначность.

Неоднозначность - это если я «а» умножил на «б» и получил то ли «с», то ли «х», то ли хуй пойми что. Но я если умножаю в кольце, то получаю всегда одно конкретное значение. Не два, не три - одно. Единственное. По-этому умножение в кольце классов вычетов задано однозначно - если у нас есть два конкретных вычета, то умножим их мы всегда получим какой-то один единственный конкретный вычет.

ага, а значит для элементов 0,1,2,3,4,6 для Z_12 соорудить обратный эл-т невозможно.

Для нуля нигде невозможно (потому как на 0 - не делят). Для единицы в любом кольце возможно - обратный единице сама единица и только она. 2,3,4,6 в Z_12 пролетают, да.

легко: в int'ах определено умножение и деление, а в вычетах — увы.

И в вычетах определено, точно так же.

да вообще-то без разницы.

Да вообще-то есть разница. Для знаковых overflow - undefined behaviour, а вот для беззнаковых - должен быть взят остаток по модулю. Что и делает unsigned int изоморфным кольцу классов вычетов.

ага. Для Z_12 получаем кучу делителей нуля, ибо 3*4==0, 2*6==0, 6*6==0, и так далее.

Ну да, получаем. И что дальше? Умножение от этого не становится менее корректным. Вот деление, как операцию обратную умножению, уже не получается определить - ну так и на интах не получается.

посмотри в удалённых, я про этот «сюрприз» уже писал. Не ты один тут такой умный.

посмотрел, не писал.

изучи смысл слова «определено». Умножение определено лишь в бесконечном поле целых и вещественных чисел, и то частично, исключая ноль.

Вот и изучи. По _определению_ кольца (даже полукольца) умножение любых двух элементов этого кольца _определено_

На 2 в z_12 делить нельзя. от этого умножение не становится неоднозначным. Неоднозначно взятие обратного элементе. Не умножение. В int взятие обратного элемента точно так же неоднозначно - ты не можешь однозначно делить int'ы на степени двойки, точно так же есть делители нуля.

В поле Галуа умножение тоже частично определено, но ПО ДРУГОМУ.

Любое поле является кольцом, в кольце умножение полностью и однозначно определено, поэтому определено и в любом поле, в том числе - в поле Галуа. Но в поле Галуа еще однозначно определено и деление чего угодно на что угодно (кроме нуля).

http://ru.wikipedia.org/wiki/Кольцо_вычетов#.D0.9A.D0.BB.D0.B0.D1.81.D1.81.D1...

википедики слабо знают математику. Попробуй таки составить эту таблицу умножения, и ей воспользоваться. И ты всё поймёшь. Действительно, для поля Галуа можно определить умножение, вот только оно совсем ДРУГОЕ. Цифры другие в таблице. А для вычетов данное правило НЕ работает, т.к. умножение НЕ ОДНОЗНАЧНО.

Т.е. данная математика википедиков бесполезна и не нужна. Это тоже самое, что сказать, что 0/0==17. Можно. А зачем?

википедики слабо знают математику.

Ок. Алгебра, Ленг, страница 78.

Попробуй таки составить эту таблицу умножения, и ей воспользоваться.

Составил, воспользовался, какие проблемы?

А для вычетов данное правило НЕ работает, т.к. умножение НЕ ОДНОЗНАЧНО.

Приведи мне пример неоднозначности умножения на вычетах. То есть два таких вычета, результат умножения которых неоднозначен.

Т.е. данная математика википедиков бесполезна и не нужна.

Кольца классов вычетов - это в точности все факторкольца натуральных. Они очень нужны.

натуральных.

Целых, конечно.

А зачем нам это знать? При чем тут умножение?

при том, что умножение — многократный сдвиг числа. Любое число в поле можно разложить на произведение простых чисел, и оно единственно и однозначно. Потому умножением можно пользоваться. А твоим «умножением» пользоваться нельзя, ибо его результат непредсказуем.

Неоднозначность - это если я «а» умножил на «б» и получил то ли «с», то ли «х», то ли х пойми что.

так и есть.

т.е. 2 умноженное на 1/2 получается то-ли 2, то-ли 7. По модулю 12. Но это ещё пол беды, беда в том, что у тебя сам модуль получается неоднозначным способом. Потому-то х..ня и получается, потому-что 2*2*3 можно представить несколькими разными способами. Как именно — хрен его знает. На этом и «держится» твоя математика.

И в вычетах определено, точно так же.

это в каких таких «целых» 2*2==1???

Да вообще-то есть разница. Для знаковых overflow - undefined behaviour, а вот для беззнаковых - должен быть взят остаток по модулю. Что и делает unsigned int изоморфным кольцу классов вычетов.

толку с этой изоморфности, если в кольце всё равно умножение не работает?

Ну да, получаем. И что дальше? Умножение от этого не становится менее корректным. Вот деление, как операцию обратную умножению, уже не получается определить - ну так и на интах не получается.

1. умножение без деления никому не нужно.

2. деление в int таки определено. Что-бы ты там не говорил.