Вычисление x mod y, где y не может быть представлен как плавающая точка
В качестве канонического примера рассмотрим проблему уменьшения аргумента для тригонометрических функций, например, при вычислении x mod 2π в качестве первого шага для вычисления sin (x). Проблема такого рода сложна тем, что вы не можете просто использовать fmod , потому что y (2π в примере) не является представимым.
Я придумал простое решение, которое работает для произвольных значений y , а не просто 2π, и мне любопытно, как он сравнивается (по производительности) с типичными алгоритмами уменьшения аргументов.
Основная идея состоит в том, чтобы сохранить таблицу, содержащую значение 2 n mod y для каждого значения n в диапазоне log2 (y) до максимально возможной экспоненты с плавающей запятой, а затем использовать линейность модульного арифметические, суммируйте значения в этой таблице по битам, установленным в значении x. Он составляет N ветвей и самое большее N добавлений, где N - количество бит мантиссы в вашем типе с плавающей запятой. Результат не обязательно меньше y, но он ограничен N * y, и процедуру можно применить снова, чтобы получить результат, ограниченный log2 (N) * y или fmod , можно просто использовать при этот момент с минимальной ошибкой.
Можно ли это улучшить? И работают ли типичные алгоритмы тригонометрического сокращения аргументов для произвольного y или только для 2π?