Comments 54
"При цифрах размером в 1 байт, размер таблицы всего лишь 1022 байт, что может позволить использовать этот трюк в 8-битных процессорах, не имеющих аппаратного умножения."
Выигрываем только в скорости вычислений, т.к. программная эмуляция даже для 32-битных операндов гораздо меньше памяти занимает, а для 8-битных тем более.
А можно узнать предпосылки к «вычитаем 2 из 1»?
то имелась в виду рутинная алгебра — вычитаем формулу (2) из формулы (1).
Книжка давно утрачена. Я пытался найти ссылки перед написанием заметки, так как опасался наткнуться на статью в Википедии на эту тему и попасть пальцем в небо с актуальностью материала, но в поиске не преуспел, может быть неудачно формировал поисковые запросы. Может быть у кого-то есть ссылки на эту тему, буду благодарен если поделитесь.
Для вычисления таблицы не нужно ни одного умножения, достаточно только сложений.
(x + 1)^2 = x^2 + 2x + 1
Соответственно таблицу можно проредить в N
раз ценой N-1
дополнительных операций при каждом вычислении квадрата, как пример.
В вашем случае, перед обращением в таблицу нужно вычислить a+b и a-b, что соответствует суммированию 2*2*8=32 бит. После обращения к таблице нужно еще раз вычислить разницу уже для 16-битных значений, это еще 32 бита которые необходимо просуммировать.
Получается в обоих случаях нужно выполнить сумирование 64 бит, но в вашем подходе 64 параллельных AND заменяются на lookup таблицу и 2 обращения к ней – сомнительная оптимизация как по скорости, так и по площади или энергопотреблению.
перед обращением в таблицу нужно вычислить a+b и a-b, что соответствует суммированию 2*2*8=32 бит
Почему 32, а не 16?
a + b
= 8 бит + флаг переполнения/переносаa - b
= 8 бит (тут наверное «бесплатное» сравнение)Кстати, обратил внимание, что даже после срезания 2 битов, оставшиеся младшие 3 бита повторяются с перодом цикла 16. Так что если есть задача уменьшить размер таблицы – можно смело отсекать еще 3 бита от каждого значения и добавлять еще одну таблицу с 16 значениями.
Думаю есть еще какие-то паттерны, которые позволят декомпозировать задачу и тем самым уменьшить размер таблицы. Например, 4ый бит повторяется с шагом 32.
Для доказательства возможности сэкономить два бита можно даже не рассматривать чётность или нечётность слагаемых в скобках, а также их младшие биты. Достаточно того факта, что всё выражение в скобках обязано нацело делиться на 4, по построению.
Если разность a и b нацело делится на 4, следовательно дробные части {a/4} и {b/4} — равны.
А, поскольку, нам нужна разность:
a/4 — b/4 = ([a/4]+{a/4}) — ([b/4]+{b/4}) = ([a/4] — [b/4]) — ({a/4} — {b/4}) = [a/4] — [b/4].
Просто психологически при отбрасывании бит возникает ощущение, что может произойти потеря информации, и желание убедить себя, что этого не происходит. Я это и сделал, рассматривая чётности, примерно как и вавилонские математики 4000 лет назад.
Аргумент WinPooh73 проще и лучше.
Спасибо.
А проверка банально выполняется делением.
«результат берётся прямо из таблицы, а столбики отсутствуют. Однако размер классической таблицы Пифагора при этом оказывается около 17GB »
— я вытираю лужи слёз от смеха,
«Далее опишу некоторое улучшение, которого в книжке не было. Его я придумал сам, когда уже писал эту заметку. ))))Так это и заметно, что ты сам придумал.))
Заметим, что два младших бита квадрата чётного числа всегда 00, а квадрата нечётного — всегда 01. С другой стороны для любой пары чисел их сумма и разность имеют одинаковую чётность.»
слушай, прекрати, озёра, реки, да что там, моря слёз от смеха сейчас пролили программисты 60-х, 70-х и особенно 80-х.
проблема только в том, что когда вы это придумываете, (а всё сделано ДО вас), то вы это слишком сильно цените в себе, и не любите здесь на Хабре, когда вам напоминают, что вы вообще-то последний в очереди. А тут ещё есть уважаемые люди. ))
Короче, как вы сами высокомерно выражаетесь по отношению к инженерам электроники, с подключением вас. Вы только что родились на Земле, человеки с Марса )))
Например, когда я здесь писал что таблицы синуса для 32 битной арифметики (да, именно таблица точности 0,4 ppb) достаточно 180 килобайт и она работает быстрее, чем любой сопроцессор, а для практической работы достаточно точности в 0,4 ppm таблица будет размером в 3,6 кбайт, то местные недоразвитые идиотики обсмеяли и выпилили своим любимым минусованием.
Теперь у вас тут все толерантные и слушаются американских ботов бесприкословно ))) Адью, алтернативные. ) Изобретайте дальше свои велосипеды, кастрюли и поварёшки.
PS, У меня давно составлена формула в Экселе, если пожертвовать точностью сильно, т.е. не выпендриваться, а сделать типа Брадиса, что хватает даже для космических полётов (с корректировкой всё равно), то при точности 1 промилле, хватит и таблицы в 72 байта через каждые 5 градусов )) что можно запихнуть вообще в любой современный проц прямо в программную память или даже в регистры.
И это будет намнооого быстрее сопроцессора с плавающей точкой. А ты про умножение. ) Тут трансцедентная функция.
если пожертвовать точностью сильно, т.е. не выпендриваться, а сделать типа Брадиса, что хватает даже для космических полётов
А специалисты по МДТТ и не знают, им даже float нужной точности не всегда даёт, не говоря уж о "таблицах в 72 байта"...
размер классической таблицы Пифагора при этом оказывается около 17GBХе-хе… Наверное тогда этот тип женоподобный, как типичный программист, не смогший бороться с системой. «Ой не смогла, напрудила 17 GB.»
В этом и разница между профи в 72 байта и 17 ГБ — от «альтернативно одарённых» (кстати эти слова, я подхватил у вас, на Хабре, и применяю их исключительно про вас, программеров, кесарю — кесарево, а слесарю — слесарево ))) хе-хе…
«17 Гб на таблицу Пифагора» — это мне кажется, что некоторые из вас, программистов, уже не просто альтернативные дурачки для нормальных людей, а уже откровенно идиоты, нуждающиеся в психиатрическом лечении.
Это я ещё не говорю про статистику по национальностям, которую вы тут боитесь ), по программерам. А она есть у меня. )) Пруф такой неплоххой про псих -заболевания, медицинский факт вполне.
2 Cerberuser — «специалисты по МДТТ»
Вы откуда свалились вообще, Вы понимаете для чего таблицы делают в системах? Судя по вашему высказыванию, нет.
Их делают для скорости вычислений в реальном времени, когда времени на сопроцессор и ожидание — нет совсем и из железа выжимают максимум. А ваши конструкторские вычисления подождут в тишине. Их делают намного заранее до боя или действия, «до экшона». Вы если не понимаете, то не встревайте в тему, пожалуйста.
Туда же — каждая пичужка норовит уколоть и высказаться.
А специалисты по МДТТ и не знают, им даже float нужной точности не всегда даёт, не говоря уж о «таблицах в 72 байта»...писец какой-то. у него есть чувство сарказма. На Хабре? )) неее, не может быть… показалось… ))
90 градусов через 5 — это 18 значений по 32 бита. Ноль вычислять не нужно, если вы не знали )) Как малолетние дети, ей-богу, сами восстановить ничего не могут. Реверс-инжиниринг — это удел богов наверное )
Так, может быть, расскажете нам, как же правильно сделать таблицу 65536 на 65535 с 32х-разрядными значениями, чтобы ее размер был меньше 16 ГиБ? (17 Гб — невнимательность автора, там их ровно 16)
Лично я вижу только 1 вариант: не делать эту таблицу. Собственно, критикуемый вами автор именно так и поступил.
Их делают для скорости вычислений в реальном времени, когда времени на сопроцессор и ожидание — нет совсем и из железа выжимают максимум
Прошу прощения. Из Вашего комментария было, мягко говоря, не очевидно (по крайне мере, не-специалисту в Вашей области), что Вы рассматриваете только частный случай, а не общеприменимый метод.
Остальное лучше проигнорировать, а то ещё закончите, как автор по ссылке из комментария выше. Не хотелось бы.
А тут ещё есть уважаемые люди. ))Есть. Но вы к ним явно не относитесть.
ab = ((a+b)^2 — a^2 — b^2) / 2
помоему, переусложнили в вашей книжке
Между тем, в вашем варианте на 1 операцию больше (1 обращение к памяти), чем в книжном.
Поэтому, если уж быть корректным, в некоторых раскладах может быть удобней что-то одно — а в некоторых других — другое. Ну или дорабатывать. Там, разумеется, если подшаманить, то можно придумать, чтобы эти биты не терялись.
Но, вообще, что это за привычка — сразу минусовать? Такие как вы сначала стреляли — а потом разговаривали.
Знаменатель там на самом деле ни на что не влияет. Поскольку заведомо известно, что деление будет нацело — можно просто не хранить младшие биты в таблице квадратов, что автоматически освобождает место для старших. То есть реальная используемая формула такая: ((a+b)2 >> 2) — ((a-b)2 >> 2)
А вот с вашей такой фокус не провернуть, потому что у вас 3 слагаемых, а не 2. Так что выходной диапазон ниже именно у вас.
Но, вообще, что это за привычка — сразу минусовать? Такие как вы сначала стреляли — а потом разговаривали.
А с каких пор минус комментарию равносилен выстрелу?
с вашей такой фокус не провернуть, потому что у вас 3 слагаемых,
Интересное объяснение.
Во-первых, 3 слагаемых на двойку точно так же делятся: (a+b+c)/2 = a/2 + b/2 +c/2
Во-вторых, таблицу полуквадратов именно как вы написали просто так без допиливания алгоритма хранить все же нельзя, потому что есть всякие нечетные: 3*3=9.
Так что пример из книжки — и переусложнен, и ненагляден, и если уж и экономить — то так, как предлагается автором. Так что суть ваших претензий довольно странная. А еще надо учесть, что там где а-b — там должен быть на самом деле модуль, иначе снова будет потеря разряда, потому что полтаблицы будут для отрицательных чисел, то есть равны первой половине. А это, извините, сравнение. (Навскидку, например, классика — сравните, мне числа, записанные в системе остаточных классов. А еще лучше — сравните точки в ecdsa. Вообще, к черту таблицы: готов простить любое кол-во дизов и минусов и тому, кто расскажет мне по секрету, как корректно сравнить положительную ecdsa-точку с отрицательной, если известно, что по модулю они равны)
А с каких пор минус комментарию равносилен выстрелу?
Минус выстрелу не равносилен. Но минусование неразобравшись — психологически близко к стрельбе неразобравшись. Потому что человек начинает совершать ненужное на эмоциях. Я привел более наглядный и простой способ, который когда-то даже работал на z80, в игрушке. Разумеется его можно улучшить, и разумеется у него есть недостатки.
вообще, я вам объясняю. Если мы что-то оптимизируем по какому-то одному параметру — то как правило по какому-то другому характеристики ухудшаются. Так работает наш мир. И впринципе, я рассчитывал, что хабровчане достаточно умны, чтобы это знать, и чтобы это ненужно было явно проговаривать. Поэтому, комментарии, что пример хуже, необоснованы. Хотите показать, что пример — говно? Придумайте оптимальней именно по тем параметрам, по которым я оптимизировал (наглядность, простота). Или дооптимизируйте по той оси, что у автора статьи. Тогда по крайней мере, суть претензии будет ясна. А то, что комментаторы пишут- ну как бы да, так можно. И я это знаю. А еще можно лампочку в гараже мощней поставить, будет светлей. И?
Во-первых, 3 слагаемых на двойку точно так же делятся: (a+b+c)/2 = a/2 + b/2 +c/2
Приведённое вами равенство верно только для обычного деления, но не при делении нацело. А для двух слагаемых это и при делении нацело работает (при условии что сумма делится без остатка). И именно по этой причине не возникает проблем с нечётными числами.
Но, вообще, что это за привычка — сразу минусовать? Такие как вы сначала стреляли — а потом разговаривали.
У меня недостаточно кармы, чтобы плюсовать или минусовать, так что предъявы не по адресу.
Быстрое умножение целых чисел с использованием таблиц