Комментарии 54
"При цифрах размером в 1 байт, размер таблицы всего лишь 1022 байт, что может позволить использовать этот трюк в 8-битных процессорах, не имеющих аппаратного умножения."
Выигрываем только в скорости вычислений, т.к. программная эмуляция даже для 32-битных операндов гораздо меньше памяти занимает, а для 8-битных тем более.
Вы правы, речь как раз и идёт об увеличении скорости при разумных затратах памяти.
Этот способ было бы любопытно прикинуть для ПЛИС по ресурсам и по частотам, например в контексте нейронных сетей. С одной стороны, в ПЛИС обычно валом DSP-слайсов как раз для умножения и сложения. Но с другой, использование блочной памяти (которой там примерно столько же, сколько DSP-слайсов, и каждая объемом 4Кб, т.е. прекрасно влезет такая табличка, а учитывая два независимых порта, к обоим квадратам можно делать одновременное обращение) для умножений таким способом потенциально сможет увеличить количество умножителей вдвое.
Спасибо за статью.
А можно узнать предпосылки к «вычитаем 2 из 1»?
А можно узнать предпосылки к «вычитаем 2 из 1»?
Если я правильно понял вопрос,
то имелась в виду рутинная алгебра — вычитаем формулу (2) из формулы (1).
то имелась в виду рутинная алгебра — вычитаем формулу (2) из формулы (1).
Нет, извините за не подробный вопрос. Я имею в виду — откуда возникла мысль вычесть одно выражение из другого и собственно откуда и как появилась идея начать с рассмотрения выражений для квадратов суммы и разности. Предполагаю, существуют какие-то работы или исследования, результатами которых вы и воспользовались. Не могли бы поделиться источниками или ссылками?
Так я и написал, что прочитал об этом в популярной книжке несколько десятков лет назад.
Книжка давно утрачена. Я пытался найти ссылки перед написанием заметки, так как опасался наткнуться на статью в Википедии на эту тему и попасть пальцем в небо с актуальностью материала, но в поиске не преуспел, может быть неудачно формировал поисковые запросы. Может быть у кого-то есть ссылки на эту тему, буду благодарен если поделитесь.
Книжка давно утрачена. Я пытался найти ссылки перед написанием заметки, так как опасался наткнуться на статью в Википедии на эту тему и попасть пальцем в небо с актуальностью материала, но в поиске не преуспел, может быть неудачно формировал поисковые запросы. Может быть у кого-то есть ссылки на эту тему, буду благодарен если поделитесь.
Начальные условия очень похожи на объяснение метода умножения Карацубы.
НЛО прилетело и опубликовало эту надпись здесь
Поскольку возведение в квадрат это тоже операция умножения, то интересно сколько элементов из таблицы можно вычислить из той-же таблицы за одно (а может и несколько) «умножений». Например любой квадрат нечётного числа сведётся к квадратам чётных, может быть половину таблицы можно так выкинуть.
НЛО прилетело и опубликовало эту надпись здесь
Хорошая статья. Надо напомнить, что, к примеру, очень популярный z80 не имеет аппаратного умножения.
Оптимизация так себе на самом деле. Смотрите, для 8-битных аргументов аппаратное умножение представляет собой 64 AND-операции с последующим сумированием получаемых 64 бит.
В вашем случае, перед обращением в таблицу нужно вычислить a+b и a-b, что соответствует суммированию 2*2*8=32 бит. После обращения к таблице нужно еще раз вычислить разницу уже для 16-битных значений, это еще 32 бита которые необходимо просуммировать.
Получается в обоих случаях нужно выполнить сумирование 64 бит, но в вашем подходе 64 параллельных AND заменяются на lookup таблицу и 2 обращения к ней – сомнительная оптимизация как по скорости, так и по площади или энергопотреблению.
В вашем случае, перед обращением в таблицу нужно вычислить a+b и a-b, что соответствует суммированию 2*2*8=32 бит. После обращения к таблице нужно еще раз вычислить разницу уже для 16-битных значений, это еще 32 бита которые необходимо просуммировать.
Получается в обоих случаях нужно выполнить сумирование 64 бит, но в вашем подходе 64 параллельных AND заменяются на lookup таблицу и 2 обращения к ней – сомнительная оптимизация как по скорости, так и по площади или энергопотреблению.
Хотя я пожалуй соглашусь что такая реализация вычислений может быть эфективной в ситуации когда «работаем с тем что имеем»: есть процессор который умеет только сумирование и не жалко тратить память, которая при этом относительно быстрая. В таком случае действительно можно получить умножение за меньшее количество тактов, заменив кучу сдвигов на 2 обращения к памяти, правда энергопотребление будет скорее всего выше (обращение в память сильно дороже арифметики и работы с регистрами).
Там ещё было сравнение с перестановкой аргументов :)
Почему 32, а не 16?
перед обращением в таблицу нужно вычислить a+b и a-b, что соответствует суммированию 2*2*8=32 бит
Почему 32, а не 16?
a + b = 8 бит + флаг переполнения/переносаa - b = 8 бит (тут наверное «бесплатное» сравнение)Я считаю количество бит-аргументов, которые нужно сложить, а не количество результирующих бит, по-этому 32. Просто я смотрю на эту оптимизацию как на аппаратную, а не софтварную. :)
Кстати, обратил внимание, что даже после срезания 2 битов, оставшиеся младшие 3 бита повторяются с перодом цикла 16. Так что если есть задача уменьшить размер таблицы – можно смело отсекать еще 3 бита от каждого значения и добавлять еще одну таблицу с 16 значениями.
Думаю есть еще какие-то паттерны, которые позволят декомпозировать задачу и тем самым уменьшить размер таблицы. Например, 4ый бит повторяется с шагом 32.
Кстати, обратил внимание, что даже после срезания 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].
Если разность 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 проще и лучше.
Спасибо.
Просто психологически при отбрасывании бит возникает ощущение, что может произойти потеря информации, и желание убедить себя, что этого не происходит. Я это и сделал, рассматривая чётности, примерно как и вавилонские математики 4000 лет назад.
Аргумент WinPooh73 проще и лучше.
Спасибо.
На языке Lua, потому что с Луны. Вообще, Lua прекрасный язык.
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
Если сломалось умножение — то алгоритм проверки не должен содержать функции умножения.
А проверка банально выполняется делением.
А проверка банально выполняется делением.
Этот трюк реально применялся на 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
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
Приведённое вами равенство верно только для обычного деления, но не при делении нацело. А для двух слагаемых это и при делении нацело работает (при условии что сумма делится без остатка). И именно по этой причине не возникает проблем с нечётными числами.
Но, вообще, что это за привычка — сразу минусовать? Такие как вы сначала стреляли — а потом разговаривали.
У меня недостаточно кармы, чтобы плюсовать или минусовать, так что предъявы не по адресу.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Быстрое умножение целых чисел с использованием таблиц