Комментарии 22
Быстрое? где тесты?
Это зависит от процессора и поставленных задач. В своей минимальной реализации приближённое умножение - это одно сложение и одно вычитание целых чисел. И всё. Вся остальная обвязка из кода - на случай специальных значений, которых может и не быть.
в минимальной реализации у вас даже знак не учитывается. на современном x86 процессоре умножение занимает 3 такта.
Как я ответил на другой пост под этой статьёй, мир не ограничивается ПК и смартфонами, и идея, неактуальная на них, может быть очень даже востребованной в других случаях.
в минимальной реализации у вас даже знак не учитывается
Знак учитывается. В статье я показал, что для чисел со знаком используется та же самая формула.
Умножение хоть и занимает 3 такта, но до arrow lake умножение происходило только на одном ALU, а значит на 3 умножения тратится 9 тактов всегда, а не 3, как на arrow lake. Умножения должны быть независимы. Да, в случае идеальном можно вообще добиться 3 умножения за цикл, но это сложно.
А там не конвейерное умножение? Т.е. не может несколько умножений выполняться одновременно, но на разных стадиях конвейера? Тогда 3 умножения подряд выполнялись бы за 5 тактов...
Я упростил... На arrow lake если очень много независимых умножений можно добиться 3 умножений за такт. Потому что pipeline... То есть arrow lake может начать 3 операции умножения с каждым тактом, то есть уже на втором такте будет 6 операций умножения в исполнении, а на 3 уже завершится умножение 1 такта... То есть в пределе 3 пайплайна умножения могут одновременно делать 9 различных ассемблерных приказов на умножение, то есть если поддерживать насышение можно достичь технического 0.3333... на умножение. То есть умножение всё ещё 3 цикла занимает, так как умножение это ступенчатый процесс — но внутри можно делать 9 ступеней сразу из разных команд ассемблера, а значит это эквивалентно 3 умножениям за цикл.
fp умножение, о котором идет речь, запускается 2 штуки в параллель каждый такт.
интересуют тесты. Всё же для операция деления есть реализация аппаратная. Даже были, когда то сопроцессоры для плавающей точки *87. Потом функционал включили в процессор. А у Вас это программная реализация. Не факт, что быстрее будет
Аппаратная реализация, о которой Вы говорите, есть в обязательном порядке на современных ПК и смартфонах, но мир ими не исчерпывается. А временами приходится выполнять достаточно сложные вычисления на какой-нибудь, грубо говоря, Ардуине, где даже целочисленных умножения-деления нет, не то что команд для работы с вещественными числами.
Лично я впервые увидел приближённые вычисления -- правда, для квадратного корня, -- в промышленном контроллере на базе микропроцессора КР580ВМ80А, в девичестве 8080, на рубеже 1980-90-х годов.
А ещё это может потребоваться при создании своей железки на ПЛИС. Да, там можно и полноценную обработку вещественных чисел реализовать, но будет медленнее и сожрёт больше ресурсов, что не есть хорошо.
Если делать на микроконтроллере, где аппаратного умножения вообще нет, то можно повысить точность алгоритма, если использовать таблицу поправок. Мы берём старшие биты мантиссы, и используем их как индекс в таблице поправок. Поправка будет суммироваться с мантиссой. Так как мы используем формулу M ≈ log_2 (1+M), то понадобится две таблицы: одна будет заменять M на более точное значение log_2 (1+M), затем мы складываем два числа (то есть, находим сумму логарифмов), вычитаем BIAS, после чего с помощью второй таблицы поправок заменяем то, что у нас сейчас в поле мантиссы: а там сейчас логарифм log_2 (1+M) на M. Нулевой и последний элемент таблицы поправок, видимо, стоит сделать равными нулю: нулевой - чтобы не испортить умножение чисел, кратных степени двойки, а последний - чтобы не вызвать случайного переполнения.
на какой Ардуине из?
на какой Ардуине из аппаратных ардуин?
на какой Ардуине из использующих Arduino framework?
Таки хотелось бы хоть один из примеров бенчмарков - за что можно побороться
попробуйте это
https://ru.wikipedia.org/wiki/Расширенный_алгоритм_Евклида еще есть китайская теорема об остатках - бегло посмотрел тоже интересно, у вас как раз деление есть и float )
Стоит добавить к тестам насколько результат отличается от эталонного:
Умножение: -9.05% .. -0.49%
Обратное значение: 1.38% .. 12.50%
Деление: 0.02% .. 11.17%
Грубо говоря ошибка 1/8 от значения.
Сфера применения - микроконтроллеры без поддержки плавающей точки? Но у них и с объёмом flash, ram тоже не очень. Какой приблизительный размер бинарный?
Почему вообще не использовать фиксированную точку? Гипотетически, мы можем получить команду управления микроконтроллером от другого устройства в float, но может отконвертировать в fixed point и уже в нём математику делать?
У МК без FPU вполне может быть несколько сотен килобайт флэша (пример -- NXP LPC17xx на ядре Cortex-M3, объём флэша -- по 512 Кбайт, объём внутреннего ОЗУ -- до 96 Кбайт в зависимости от конкретной модификации).
У арифметики с фиксированной запятой свои недостатки. В частности, если точность не важна, но диапазон чисел большой, без плавающей запятой обойтись проблематично. Так что один способ не отменяет и не заменяет другой -- нужно на задачу смотреть.
Спасибо, очень интересно и полезно. До складывания экспонент я сам когда-то догадался, но вот что бы сделать поправки меня уже не хватило. :)
Быстрое приближённое умножение и деление чисел с плавающей точкой