История изменений
Исправление Waterlaz, (текущая версия) :
Т.е. ты выносишь инвариант из цикла.
Если и выношу, то уж точно не инвариант.
А именно — дорогое умножение выносишь наружу, вычисляя его предварительно.
В приведенном мною примере умножения нет вовсе.
Это и есть твои S(x,y).
S(x, y) — всего лишь суммы a[k][j], 0<=k<=x, 0<=j<=y
Фишка тут в способе хранения этих S, т.к. они очень похожи(S(x,y1) ~= S(x,y2)), ты хранишь не сами площади, а их разности.
Я храню не площади и уж тем более не их разности, а суммы по модулю некоторого числа.
Это широко известное дельта кодирование.
Это не дельта кодирование.
И естественно не целиком, а только младшие биты. Не слишком надёжно(ибо вообще говоря никто не обещал, что все дельты будут меньше M, это просто маловероятно, что их будет «много»), но для графики к тупой гаме — потянет. Подумаешь — небольшие артефакты...
Соответственно, вот это все бред.
И да, умножение тут не при чём. Функция может быть вообще любой. Лишь бы её производная была-бы маленькой(т.е. функция должна быть достаточно гладкой, как умножение например).
О какой функции идет речь? В моем примере ни о какой функции речь не шла.
Исправление Waterlaz, :
Т.е. ты выносишь инвариант из цикла.
Если и выношу, то уж точно не инвариант.
А именно — дорогое умножение выносишь наружу, вычисляя его предварительно.
В приведенном мною примере умножения нет вовсе.
Это и есть твои S(x,y).
S(x, y) — всего лишь суммы a[k][j], 0<=k<=x, 0<=j<=y
Фишка тут в способе хранения этих S, т.к. они очень похожи(S(x,y1) ~= S(x,y2)), ты хранишь не сами площади, а их разности.
Я храню не площади и уж тем более не их разности, а суммы по модулю.
Это широко известное дельта кодирование.
Это не дельта кодирование.
И естественно не целиком, а только младшие биты. Не слишком надёжно(ибо вообще говоря никто не обещал, что все дельты будут меньше M, это просто маловероятно, что их будет «много»), но для графики к тупой гаме — потянет. Подумаешь — небольшие артефакты...
Соответственно, вот это все бред.
И да, умножение тут не при чём. Функция может быть вообще любой. Лишь бы её производная была-бы маленькой(т.е. функция должна быть достаточно гладкой, как умножение например).
О какой функции идет речь? В моем примере ни о какой функции речь не шла.
Исходная версия Waterlaz, :
Т.е. ты выносишь инвариант из цикла.
Если и выношу, то уж точно не инвариант.
А именно — дорогое умножение выносишь наружу, вычисляя его предварительно.
В приведенном мною примере умножения нет вовсе.
Это и есть твои S(x,y).
S(x, y) — всего лишь суммы a[j], 0<=i<=x, 0<=j<=y
Фишка тут в способе хранения этих S, т.к. они очень похожи(S(x,y1) ~= S(x,y2)), ты хранишь не сами площади, а их разности.
Я храню не площади и уж тем более не их разности, а суммы по модулю.
Это широко известное дельта кодирование.
Это не дельта кодирование.
И естественно не целиком, а только младшие биты. Не слишком надёжно(ибо вообще говоря никто не обещал, что все дельты будут меньше M, это просто маловероятно, что их будет «много»), но для графики к тупой гаме — потянет. Подумаешь — небольшие артефакты...
Соответственно, вот это все бред.
И да, умножение тут не при чём. Функция может быть вообще любой. Лишь бы её производная была-бы маленькой(т.е. функция должна быть достаточно гладкой, как умножение например).
О какой функции идет речь? В моем примере ни о какой функции речь не шла.