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

сдвигать на n

* занулять n.

Короче, вопрос терминологии. Ты считаешь, что (арифметическая, надеюсь) функция «однозначно определена» только когда это функция-биекция. Для меня определённость это «просто последовательность действий, которая даёт результат», то есть функция. Или надо явно говорить «не определена обратная», «не биекция».

ок, согласен.

но там ближе к началу я это уже говорил. Задолбало.

Что эквивалентно сдвигу, что эквивалентно взятию остатка по модулю от результата

...что эквивалентно ПОТЕРЕ информации. Т.е. это не просто «обычное умножение», это «необратимое умножение». Разница тут ИМХО принципиальная. Потому как на практике подразумевается, что раз мы помножили на x, то и поделить на x сможем, если конечно x не является «ничем».

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

Вот только я всё равно не понимаю, нахрена оно нужно?

Можно придумывать бесконечно много правил, которые никому не нужны. В этом разве есть смысл?

Что это у тебя за нотация такая чудная? Это сейчас в научных трудах так пишут?

У меня гарантированно будет правильный ответ.

позволь узнать, ЗАЧЕМ тебе нужен такой ответ? На практике, если мы что-то на что-то умножаем, то в конце нам ещё и поделить надо. Вот тут-то нам и понадобятся старшие биты, которые ты потерял. Терять-то надо именно младшие биты, а никак не наоборот, потому-что их ценность — либо такая же, либо ниже. Информация в битах произведения распределена неравномерно: в нулевом бите содержится смесь нулевых битов, в первом бите — смесь нулевых и первых, и так далее. Т.е. чем старше бит, тем от большего количества бит он зависит. Если ты сохранил старшие биты, то ты примерно знаешь интервал, в котором лежит истинное произведение, если сохранил младшие биты, то ты знаешь точно расстояние от модуля, умноженного на какое-то неизвестное число(которое ты потерял). Вот я и спрашиваю: ЗАЧЕМ тебе это расстояние? Какой в нём вообще физический смысл? Есть хоть одно явление в этом мире, которое характеризуется таким числом?

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

unsigned char r = 15*b-20*a

Если я знаю, что результат помещается в мой беззнаковый тип

теперь нарисуй мне ПРОВЕРКУ того, что оно действительно помещается. А то мне этот момент не совсем ясен в твоём коде. Если я все числа ЗНАЮ, то зачем вообще заставлять компьютер считать? А если не все, то какие именно я НЕ знаю? И как получилось, что я, не зная результат, знаю, что он куда-то влезает?

А еще такой вот swap всегда корректно работает для unsigned

есть только три проблемы:

1. а это unsigned?

2. код намного медленнее, чем имеющееся практически везде машинная инструкция. И я не представляю настолько гениальный компилятор, который это распарсит. Такое и программист не каждый поймёт(если не в курсе).

3. код очевидно не подходит для многозадачных систем.

Вот только я всё равно не понимаю, нахрена оно нужно?

Представь себе - для того, чтобы умножать. При этом деление может и не быть вовсе. Потому что нам надо умножать - не делить. Умножать надо. А делить - не надо.

Обычная нотация, хз.

На практике, если мы что-то на что-то умножаем, то в конце нам ещё и поделить надо.

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

∃ n f₁ f₂. ∀ a b k l. f(a + k * n, b + l * n) = f₁(a, b, n) + f₂(a, b, k, l, n) * n

Я привык видеть в таких записях типизацию внутри кванторов, а еще непонятно с точками - обычно двоеточия же. Это западный стиль какой-то или просто общий современный, а я отстал лет на дцать?

Я привык видеть в таких записях типизацию внутри кванторов, а еще непонятно с точками - обычно двоеточия же. Это западный стиль какой-то или просто общий современный, а я отстал лет на дцать?

Это стандартная запись, хз, так все пишут вплоть до 80-летних преподавателей по матану. Ну разве что обычно двоеточия, а не точки, и запятые ставят

Если я хочу посчитать площадь прямоугольника, то мне не нужно ничего делить, только умножать. И таких задач - мильон.

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

теперь нарисуй мне ПРОВЕРКУ того, что оно действительно помещается. А то мне этот момент не совсем ясен в твоём коде. Если я все числа ЗНАЮ, то зачем вообще заставлять компьютер считать? А если не все, то какие именно я НЕ знаю? И как получилось, что я, не зная результат, знаю, что он куда-то влезает?

Вот так и палятся люди, которые ничего не пишут, а только теоретизируют.

Типичная подзадача, возникающая просто на кажждом ходу, например, в обработке изображений:

Есть массив неотрицательных чисел a[n][m]. Необходимо периодически вычислять суммы этих чисел на прямоугольниках:

s(n1, n2, m1, m2) = \sum_{n1<=k<=n2, m1<=j<=m2}a[k][j]

Решение: предварительно вычисляем числа S(x, y) = s(0, x, 0, y)

тогда s(n1, n2, m1, m2) = S(n2, m2)+S(n1, m1)-S(n1, m2)-S(n2, m1)

Как правило, нам нужны суммы прямоугольников небольших площадей(скажем, 10х10), которые вполне помещаются в наш беззнаковый тип. При этом числа S(x, y) могут быть очень большими и не влазить

Типичная подзадача, возникающая просто на кажждом ходу, например, в обработке изображений...

Во-первых, на всём пространстве задач данная таки сверх-узко-специализированная. И при всём при этом, как данная задача, так и все остальные не избавляют от правильного выбора размера оперируемых данных. И таки да - надо помнить про «удвоении разрядности результата» при умножении (я не про разрядность переменных, если вдруг кто взъерошится на эти слова).

Но для меня это где-то на уровне азбуки в информатике. И мне всё равно не понятно, как один умудрился раздуть из мухи слона, а другие повелись на этот троллинг... :\

Вот так и палятся люди, которые ничего не пишут, а только теоретизируют.

Решение: предварительно вычисляем числа S(x, y) = s(0, x, 0, y)

а вот так палятся люди, которые в состоянии лишь нагуглить формулу, и скопипастить её в свой код...

Ладно, объясняю, как это работает: у тебя вычисления предварительные здесь. Т.е. ты выносишь инвариант из цикла. А именно — дорогое умножение выносишь наружу, вычисляя его предварительно. Это и есть твои S(x,y). Фишка тут в способе хранения этих S, т.к. они очень похожи(S(x,y1) ~= S(x,y2)), ты хранишь не сами площади, а их разности. Это широко известное дельта кодирование. И естественно не целиком, а только младшие биты. Не слишком надёжно(ибо вообще говоря никто не обещал, что все дельты будут меньше M, это просто маловероятно, что их будет «много»), но для графики к тупой гаме — потянет. Подумаешь — небольшие артефакты...

Я так часто делаю, но в отличие от тебя, я использую не «младшие M битов», а специальный код переменной длинны, например Хаффмана.

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

И да, умножение тут не при чём. Функция может быть вообще любой. Лишь бы её производная была-бы маленькой(т.е. функция должна быть достаточно гладкой, как умножение например).

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

ИМХО основной косяк не в этом, а в том, что алгоритм сам по себе ошибочный. Это типичное «сжатие с потерями», когда любая музыка приводится к модели «зайка моя.mp3», а всё, что не лезет, нещадно обрезается. Да, быстро, и да, жмёт хорошо. И да, «зайка моя.mp3» звучит не хуже, чем на живом концерте Ф.Киркорова. (:

В принципе, подход имеет смысл, если данные более-менее одинаковы, и если подобрать эмпирические константы для нормализации данных в пространство вычислителя, так, что-бы нам надо было хранить именно M битов модуля. Потому-что тут мы считаем не так, как надо, а так, как нам _удобнее_.

И мне всё равно не понятно, как один умудрился раздуть из мухи слона, а другие повелись на этот троллинг...

это ЛОР.

Ну да. И еще пишут типы переменных и функций.

Во-первых, на всём пространстве задач данная таки сверх-узко-специализированная

Просили пример, получили пример. В других областях есть другие задачи.

ИМХО основной косяк не в этом, а в том, что алгоритм сам по себе ошибочный.

Не ошибочный.

Это типичное «сжатие с потерями»

Никаких потерь нет.

Ладно, объясняю, как это работает: у тебя вычисления предварительные здесь. Т.е. ты выносишь инвариант из цикла. А именно — дорогое умножение выносишь наружу, вычисляя его предварительно.

Я нигде не вычисляю умножение. Его тут нет в принципе.

Фишка тут в способе хранения этих S, т.к. они очень похожи(S(x,y1) ~= S(x,y2)), ты хранишь не сами площади, а их разности. Это широко известное дельта кодирование.

Нет. Фишка тут вовсе не в этом, а в быстром вычислении суммы(за время не зависящее от размера прямоугольника, на котором вычисляется сумма).

Я так часто делаю, но в отличие от тебя, я использую не «младшие M битов», а специальный код переменной длинны, например Хаффмана.

Ну и дурак, Хаффман тут ни при чем.

Но для меня это где-то на уровне азбуки в информатике. И мне всё равно не понятно, как один умудрился раздуть из мухи слона, а другие повелись на этот троллинг... :\

Троллинг? Никто же не спорит, что для представления произведения двух n-битных чисел нужно 2*n бит. Мне не нравятся другие ошибочные его утверждения

Нет. Фишка тут вовсе не в этом, а в быстром вычислении суммы(за время не зависящее от размера прямоугольника, на котором вычисляется сумма).

С быстрым вычислением не понятно: как вычисление 4-х сумм размерностью x000*y000 может быть быстрее вычисления одной суммы n*m, пусть и «глубоко в матрице»?

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

Все суммы S(x, y) можно вычислить за линейное время от размеров изображения. После этого любая сумма s(n1, n2, m1, m2) вычисляется за константу.

Никаких потерь нет.

просто ты их не видишь. Ибо не понимаешь, как это работает.

Есть массив неотрицательных чисел a[n][m]. Необходимо периодически вычислять суммы этих чисел на прямоугольниках: s(n1, n2, m1, m2) = \sum_{n1<=k<=n2, m1<=j<=m2}a[k][j]

Я нигде не вычисляю умножение. Его тут нет в принципе.

ты действительно идиот, или теперь ты тут клоунаду устраиваешь?

Нет. Фишка тут вовсе не в этом, а в быстром вычислении суммы(за время не зависящее от размера прямоугольника, на котором вычисляется сумма).

ох...

Ну и дурак, Хаффман тут ни при чем.

абсолютно верно. Это тупой терминальный вариант кода Хаффмана, когда «лишние» биты тупо отрезаются. В нормальном коде, для каждого символа входного алфавита вычисляется код оптимальной длинны, а в твоём варианте ты тупо положил, что дескать «оптимальная длинна == M». Да, при некоторых допущениях оно даже работает. Криво, но для говнографики пойдёт.

А теперь представь что мне надо найти разность между двумя этими площадями. Каждая из них - больше 2^32, но разность - меньше.

но там ближе к началу я это уже говорил

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

Вот только я всё равно не понимаю, нахрена оно нужно?

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

А теперь представь что мне надо найти разность между двумя этими площадями. Каждая из них - больше 2^32, но разность - меньше.

представил. А зачем? Как так получилось, что площади больше 2^32, а разности — меньше? Откуда такое ПРАВИЛО? Ты из пальца высосал? Ну высасывай дальше...

Все ответы в первой главе sicp.

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

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

Ну у нас регистры и типы фиксированной точности, так что если вычислять операции и отсекать верхние части, то их значения будут вести себя точно как вычеты во всём.

угу. Фишка в том, что это искусственное ограничение, и к железу оно отношения НЕ имеет. Эти ваши вычеты никому IRL не нужны, и потому их никто и никогда не реализовывал в железе. Ну просто нет смысла умножать 3/4 мусора, который ни на что не влияет. В сишечку оно попало лишь для совместимости и кроссплатформенности. Подразумевалось, что эти int'ы — исключительно индексы, произведения индексов — суть матрицы, а матрицы не могут быть больше регистра адреса. Ибо меньше char'а чисел не бывает. Потому-то int'ы никогда и не должны переполняться. Если же тебе нужна действительно целая арифметика — обмазывайся ассемблером. Она в принципе не переносима. Наверное из этих соображений K&R подложили такую свинью.

Все ответы в первой главе sicp.

ТСа уже неоднократно туда посылали. Надеюсь — он уже там. А мы тут про другое.

Типизация там не нужна, так как тип f уже был озвучен — кроме целых чисел и функций на них там ничего не может быть.

Остальное ок? А то там ещё тернарный оператор, чтобы не считать, что расходящийся интервал совпадает с множеством на котором задаётся (в дополнение к изоморфизму Z и Z/0Z и x % 0 = x).

просто ты их не видишь. Ибо не понимаешь, как это работает.

Нет там потерь. Я n*m чисел кодирую другими n*m чисел, по которым исходные можно восстановить внезависимости от того, было там переполнение или нет.

ты действительно идиот, или теперь ты тут клоунаду устраиваешь?

Оператор умножения я нигде не использую. Так что скажи мне, что на что я умножаю там?

Это тупой терминальный вариант кода Хаффмана, когда «лишние» биты тупо отрезаются.

ты любое кодирование называешь «вариант кода Хаффмана»? :D

В нормальном коде, для каждого символа входного алфавита вычисляется код оптимальной длинны, а в твоём варианте ты тупо положил, что дескать «оптимальная длинна == M»

Ничего подобного я и близко не делал. Никаких оптимальных длин не предполагал.

Еще раз. У меня был массив беззнаковых n*m чисел a[x][y]. Я из него построил массив беззнаковых n*m чисел s[x][y], из которого:

во-первых, однозначно и без потерь можно восстановить исходный массив a[x][y]

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

Если ты с этим не согласен, то либо неправильно понял то, что я делаю, либо не понимаешь, как работает unsigned арифметика.

Как так получилось, что площади больше 2^32, а разности — меньше?

Очень легко. А в чем проблема с тем, чтобы так получилось?

Нет, я не спорю с записью, просто интересуюсь.

У нас, особенно в теорвере, иногда в подобных случаях индикатор используют: http://goo.gl/5dnfSY

Оператор умножения я нигде не использую. Так что скажи мне, что на что я умножаю там?

школьного курса арифметики для этого похоже не хватит. Извини.

школьного курса арифметики для этого похоже не хватит. Извини.

Слив защитан?

Т.е. ты выносишь инвариант из цикла.

Если и выношу, то уж точно не инвариант.

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

В приведенном мною примере умножения нет вовсе.

Это и есть твои S(x,y).

S(x, y) — всего лишь суммы a[k][j], 0<=k<=x, 0<=j<=y

Фишка тут в способе хранения этих S, т.к. они очень похожи(S(x,y1) ~= S(x,y2)), ты хранишь не сами площади, а их разности.

Я храню не площади и уж тем более не их разности, а суммы по модулю некоторого числа.

Это широко известное дельта кодирование.

Это не дельта кодирование.

И естественно не целиком, а только младшие биты. Не слишком надёжно(ибо вообще говоря никто не обещал, что все дельты будут меньше M, это просто маловероятно, что их будет «много»), но для графики к тупой гаме — потянет. Подумаешь — небольшие артефакты...

Соответственно, вот это все бред.

И да, умножение тут не при чём. Функция может быть вообще любой. Лишь бы её производная была-бы маленькой(т.е. функция должна быть достаточно гладкой, как умножение например).

О какой функции идет речь? В моем примере ни о какой функции речь не шла.

О терминах не спорят, о терминах договариваются

И рекурсия и итерация это просто способы описать алгоритм.

Они почти эквивалентны. Циклы эквивалентны хвостовой рекурсии. Циклы с разного рода стеками эквивалентны нехвостовой.

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

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

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

Смысл твоего поста неочевиден. Ты не понял, что он имел в виду или решил «опровергнуть»?

Ты не понял, что он имел в виду

Возможно.

решил «опровергнуть»?

Написал то, что он предложил проверить, и это не сошлось с его словами. Хотя возможно и

не понял, что он имел в виду

ОК.

Товарищ написал что (a*a - b*b) !== (a-b)*(a+b)

Полагаю, что он имел в виду, что не всегда (a*a - b*b) равно (a-b)*(a+b) в случае «наивной» реализации. Как пример можно рассмотреть a и b представленные как целые числа фиксированной точности, со значениями, где a*a или b*b не влезают в диапазон значений. Этот эффект ты можешь наблюдать и в своём коде, если возьмешь достаточно большие величины а не 30 и 20.

Вообще, рекурсия и итерация это как по-быстрому и по осознанному. Побочка осознания - предсказуемость (как минимум автором и сочуствубщих)

Я знаю,что в математике есть некая аналитическая форма и рекурентная формула.Аналитическая форма это та форма,которая самодостаточна и ей не требуется никакого погружения через саму себя. т.е представима на подобие j(n)=2^n - 1.Рекурентная же j(n)=j(n-1) -1,j(1)=1 - явный пример.Итерационный процесс-процесс можно соотнести как-нибудь с аналитичной формой,а рекурентный процесс - рекурсией. Мое мнение таково,что возможно рекрусивный процесс-частный случай итерационного.Это мое личное мнение)