Pull to refresh

Comments 54

"При цифрах размером в 1 байт, размер таблицы всего лишь 1022 байт, что может позволить использовать этот трюк в 8-битных процессорах, не имеющих аппаратного умножения."
Выигрываем только в скорости вычислений, т.к. программная эмуляция даже для 32-битных операндов гораздо меньше памяти занимает, а для 8-битных тем более.

Вы правы, речь как раз и идёт об увеличении скорости при разумных затратах памяти.
Этот способ было бы любопытно прикинуть для ПЛИС по ресурсам и по частотам, например в контексте нейронных сетей. С одной стороны, в ПЛИС обычно валом DSP-слайсов как раз для умножения и сложения. Но с другой, использование блочной памяти (которой там примерно столько же, сколько DSP-слайсов, и каждая объемом 4Кб, т.е. прекрасно влезет такая табличка, а учитывая два независимых порта, к обоим квадратам можно делать одновременное обращение) для умножений таким способом потенциально сможет увеличить количество умножителей вдвое.
Спасибо за статью.
А можно узнать предпосылки к «вычитаем 2 из 1»?
Если я правильно понял вопрос,
то имелась в виду рутинная алгебра — вычитаем формулу (2) из формулы (1).
Нет, извините за не подробный вопрос. Я имею в виду — откуда возникла мысль вычесть одно выражение из другого и собственно откуда и как появилась идея начать с рассмотрения выражений для квадратов суммы и разности. Предполагаю, существуют какие-то работы или исследования, результатами которых вы и воспользовались. Не могли бы поделиться источниками или ссылками?
Так я и написал, что прочитал об этом в популярной книжке несколько десятков лет назад.
Книжка давно утрачена. Я пытался найти ссылки перед написанием заметки, так как опасался наткнуться на статью в Википедии на эту тему и попасть пальцем в небо с актуальностью материала, но в поиске не преуспел, может быть неудачно формировал поисковые запросы. Может быть у кого-то есть ссылки на эту тему, буду благодарен если поделитесь.
Начальные условия очень похожи на объяснение метода умножения Карацубы.
UFO just landed and posted this here
Огромное спасибо!
Ещё бы ссылку на книжку найти — там было ещё несколько интересных трюков.
Поскольку возведение в квадрат это тоже операция умножения, то интересно сколько элементов из таблицы можно вычислить из той-же таблицы за одно (а может и несколько) «умножений». Например любой квадрат нечётного числа сведётся к квадратам чётных, может быть половину таблицы можно так выкинуть.

Для вычисления таблицы не нужно ни одного умножения, достаточно только сложений.
(x + 1)^2 = x^2 + 2x + 1
Соответственно таблицу можно проредить в N раз ценой N-1 дополнительных операций при каждом вычислении квадрата, как пример.

Ну с таким же успехом можно и предыдущее значение найти
(x - 1)^2 = x^2 - 2x + 1
Это меньше операций, если идти от ближайшего :)
UFO just landed and posted this here
Современное железо с неисправным умножением скорее всего не сможет даже загрузить ОС. Статья скорее относится к неким бракованным микроконтроллерам, где неисправную инструкцию можно попробовать «обойти», а показатели скорости памяти и вычислительных ядер там могут очень сильно отличаться.
Причём тут брак и неисправная инструкция? Умножения может тупо не быть на микроконтроллере.
Хорошая статья. Надо напомнить, что, к примеру, очень популярный z80 не имеет аппаратного умножения.
Оптимизация так себе на самом деле. Смотрите, для 8-битных аргументов аппаратное умножение представляет собой 64 AND-операции с последующим сумированием получаемых 64 бит.

В вашем случае, перед обращением в таблицу нужно вычислить a+b и a-b, что соответствует суммированию 2*2*8=32 бит. После обращения к таблице нужно еще раз вычислить разницу уже для 16-битных значений, это еще 32 бита которые необходимо просуммировать.

Получается в обоих случаях нужно выполнить сумирование 64 бит, но в вашем подходе 64 параллельных AND заменяются на lookup таблицу и 2 обращения к ней – сомнительная оптимизация как по скорости, так и по площади или энергопотреблению.
Хотя я пожалуй соглашусь что такая реализация вычислений может быть эфективной в ситуации когда «работаем с тем что имеем»: есть процессор который умеет только сумирование и не жалко тратить память, которая при этом относительно быстрая. В таком случае действительно можно получить умножение за меньшее количество тактов, заменив кучу сдвигов на 2 обращения к памяти, правда энергопотребление будет скорее всего выше (обращение в память сильно дороже арифметики и работы с регистрами).
Там ещё было сравнение с перестановкой аргументов :)
перед обращением в таблицу нужно вычислить a+b и a-b, что соответствует суммированию 2*2*8=32 бит

Почему 32, а не 16?
a + b = 8 бит + флаг переполнения/переноса
a - b = 8 бит (тут наверное «бесплатное» сравнение)
Я считаю количество бит-аргументов, которые нужно сложить, а не количество результирующих бит, по-этому 32. Просто я смотрю на эту оптимизацию как на аппаратную, а не софтварную. :)

Кстати, обратил внимание, что даже после срезания 2 битов, оставшиеся младшие 3 бита повторяются с перодом цикла 16. Так что если есть задача уменьшить размер таблицы – можно смело отсекать еще 3 бита от каждого значения и добавлять еще одну таблицу с 16 значениями.

Думаю есть еще какие-то паттерны, которые позволят декомпозировать задачу и тем самым уменьшить размер таблицы. Например, 4ый бит повторяется с шагом 32.
А если + и — сделать одной операцией с двумя выходами :)
Хитрая операция ab+- где на выходе 16 бит a+b и a-b

Вряд ли можно сделать настолько хитрую операцию. Переносы-то пойдут совсем по-разному, так что максимум что удастся сэкономить — первый слой схемы распространения переноса, и то не факт.

Для доказательства возможности сэкономить два бита можно даже не рассматривать чётность или нечётность слагаемых в скобках, а также их младшие биты. Достаточно того факта, что всё выражение в скобках обязано нацело делиться на 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].
Подумав, должен признать, что WinPooh73 совершенно прав.
Просто психологически при отбрасывании бит возникает ощущение, что может произойти потеря информации, и желание убедить себя, что этого не происходит. Я это и сделал, рассматривая чётности, примерно как и вавилонские математики 4000 лет назад.
Аргумент WinPooh73 проще и лучше.
Спасибо.
На языке Lua, потому что с Луны. Вообще, Lua прекрасный язык.
UFO just landed and posted this here
UFO just landed and posted this here
UFO just landed and posted this here
UFO just landed and posted this here
UFO just landed and posted this here
1. а если перед вычислением определять максимальное и его назначать на u и минимальное на v? тогда таблица из отрицательных значений уходит.
2. при равенстве просто выдавать табличный квадрат?
UFO just landed and posted this here
UFO just landed and posted this here
Если сломалось умножение — то алгоритм проверки не должен содержать функции умножения.
А проверка банально выполняется делением.
Этот трюк реально применялся на 8080, z80 PDP11 без сопроцессора.
«результат берётся прямо из таблицы, а столбики отсутствуют. Однако размер классической таблицы Пифагора при этом оказывается около 17GB »

— я вытираю лужи слёз от смеха,

«Далее опишу некоторое улучшение, которого в книжке не было. Его я придумал сам, когда уже писал эту заметку. ))))
Заметим, что два младших бита квадрата чётного числа всегда 00, а квадрата нечётного — всегда 01. С другой стороны для любой пары чисел их сумма и разность имеют одинаковую чётность.»
Так это и заметно, что ты сам придумал.))
слушай, прекрати, озёра, реки, да что там, моря слёз от смеха сейчас пролили программисты 60-х, 70-х и особенно 80-х.
проблема только в том, что когда вы это придумываете, (а всё сделано ДО вас), то вы это слишком сильно цените в себе, и не любите здесь на Хабре, когда вам напоминают, что вы вообще-то последний в очереди. А тут ещё есть уважаемые люди. ))

Короче, как вы сами высокомерно выражаетесь по отношению к инженерам электроники, с подключением вас. Вы только что родились на Земле, человеки с Марса )))

Например, когда я здесь писал что таблицы синуса для 32 битной арифметики (да, именно таблица точности 0,4 ppb) достаточно 180 килобайт и она работает быстрее, чем любой сопроцессор, а для практической работы достаточно точности в 0,4 ppm таблица будет размером в 3,6 кбайт, то местные недоразвитые идиотики обсмеяли и выпилили своим любимым минусованием.

Теперь у вас тут все толерантные и слушаются американских ботов бесприкословно ))) Адью, алтернативные. ) Изобретайте дальше свои велосипеды, кастрюли и поварёшки.

PS, У меня давно составлена формула в Экселе, если пожертвовать точностью сильно, т.е. не выпендриваться, а сделать типа Брадиса, что хватает даже для космических полётов (с корректировкой всё равно), то при точности 1 промилле, хватит и таблицы в 72 байта через каждые 5 градусов )) что можно запихнуть вообще в любой современный проц прямо в программную память или даже в регистры.
И это будет намнооого быстрее сопроцессора с плавающей точкой. А ты про умножение. ) Тут трансцедентная функция.
если пожертвовать точностью сильно, т.е. не выпендриваться, а сделать типа Брадиса, что хватает даже для космических полётов

А специалисты по МДТТ и не знают, им даже float нужной точности не всегда даёт, не говоря уж о "таблицах в 72 байта"...

Советую Вам познакомиться с rybvv. Вы с ним явно найдете общий язык.

Кажется, Вы упомянутому товарищу устроили хабраэффект :)

Челябинские радиоинженеры настолько суровы…
размер классической таблицы Пифагора при этом оказывается около 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

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

Но, вообще, что это за привычка — сразу минусовать? Такие как вы сначала стреляли — а потом разговаривали.

У меня недостаточно кармы, чтобы плюсовать или минусовать, так что предъявы не по адресу.
Sign up to leave a comment.

Articles