Как эффективно вычислить модуль в C вручную?

Я написал базовый вариант синусоидальной функции с фиксированной точкой, который использует справочную таблицу (нацеленный на микроконтроллер AVR без FPU). Моя реализация также принимает отрицательные значения и значения, превышающие 2π, как это делает подвеска с плавающей запятой в math.h.

Поэтому мне нужно сопоставить заданное значение с диапазоном от 0 до 2π (т. е. с их аналогами с фиксированной точкой). Положительные аргументы легко обрезать с помощью встроенного в C оператора остатка %. Поскольку это не вариант для отрицательных значений, я использую следующий (очевидный) подход:

    unsigned int modulus = (a - (INT_FLOOR(a / b) * b) + b) % b;

a и b являются значениями целочисленного типа, а INT_FLOOR() просто означает, что дробная часть (a/b) усекается. Эта формула гарантирует, что вычисляемый модуль (который используется в качестве индекса для массива таблиц) всегда положителен, а отрицательные аргументы сопоставляются с их положительными аналогами (сохраняя фазовые сдвиги в обоих направлениях).

Моя проблема с этим подходом заключается в том, что он кажется слишком сложным, поскольку включает не менее пяти арифметических операций. Есть ли более эффективный подход, который мне не хватает?


c trigonometry avr-gcc modulus
person Developer's Destiny    schedule 03.05.2012    source источник
comment
Синус — нечетная функция, поэтому sin(-x) = -sin(x) косинус четный, cos(-x) = cos(x). Это должно упростить дело.   -  person Daniel Fischer    schedule 04.05.2012
comment
Можете ли вы использовать fmod для выполнения оставшихся чисел с плавающей запятой? Он корректно работает как с отрицательными числами, так и с положительными.   -  person Sergey Kalinichenko    schedule 04.05.2012
comment
Похоже, вам нужны оставшиеся абсолютные значения, так почему бы не сделать это напрямую: unsigned in modulus = abs(a) % abs(b); Альтернативно, что-то вроде: modulus = a % b; if (modulus < 0) modulus += b;   -  person Jerry Coffin    schedule 04.05.2012
comment
@DanielFischer: Большое спасибо, я упустил очевидное (что может объяснить, почему кто-то пометил это как домашнее задание). К сожалению, мой наивный подход по-прежнему кажется лучшим решением, так как результирующий размер кода короче на 26 байт (avr-gcc -O2). dasblinkenlight: fmod предназначен только для математики с плавающей запятой, чего я хочу избежать любой ценой в этой архитектуре JerryCoffin: использование abs() здесь и там увеличивает размер кода больше, чем при использовании моего наивного подхода, avr-gcc иногда делает странные вещи   -  person Developer's Destiny    schedule 04.05.2012

Ответы (2)


arrow_upward
4
arrow_downward

Если ваши целочисленные аргументы не были масштабированы таким образом, что они кратны π (например, 65536 означает 2π), попытка сокращения аргумента, вероятно, будет ошибочной, поскольку 2π иррационально, и любое сокращение по модулю 2π внесет ошибку, которая масштабируется с количество периодов до тех пор, пока весь результат сокращения не станет ошибкой. На самом деле это серьезная проблема во многих реализациях триггеров с плавающей запятой.

Я бы рекомендовал либо вообще не уменьшать аргументы, либо использовать угловую шкалу, основанную на степени двойки, а не на радианах (так, например, 0x10000 или 0x1000000 соответствует 2π или 360 градусам). Тогда редукция аргумента становится одной побитовой операцией.

person R.. GitHub STOP HELPING ICE    schedule 03.05.2012
comment
Я знаю о накоплении ошибок округления. К счастью, они находятся в допустимых пределах относительно моих задач даже после нескольких сотен раундов (я не превышаю 1000 раундов, и промежуточные результаты не сильно вложены). Поскольку я использую таблицы поиска на архитектурах с (максимум) 65536 байтами флэш-памяти, я не понимаю, как можно обойтись без сокращения аргументов. Но ваше второе предложение очень интересное. Это включает в себя модификации всех окружающих процедур, которые используют эту синусоидальную функцию, но это может значительно повысить точность. Определенно то, о чем мне нужно больше думать. - person Developer's Destiny; 04.05.2012
comment
Я думаю, что это значительно повысит точность и производительность. - person R.. GitHub STOP HELPING ICE; 04.05.2012

arrow_upward
0
arrow_downward

Я вижу вашу формулу правильной, хотя и не такой красивой.

Если вы сделаете b степенью числа 2, то некоторые операции можно будет выполнять с битовыми масками. Что-то вроде:

unsigned int modulus = (a - (a & ~(b-1)) + b) & (b-1);

И если b является константой или макросом, он должен немного оптимизироваться.

person rodrigo    schedule 03.05.2012
comment
b действительно является макросом, но нецелесообразно изменять его или окружающие вычисления для обработки степеней двойки (что приводит как к увеличению размера кода, так и к потере точности). В моем случае b — это количество шагов временного квантования моей аппроксимированной синусоиды. Он должен быть делителем моей версии 2π с фиксированной точкой, чтобы я мог эффективно отображать углы с фиксированной точкой в ​​соответствующий им шаг квантования (который действительно включает только один битовый сдвиг). Но все равно спасибо за подсказку. - person Developer's Destiny; 04.05.2012
comment
Вот почему математические программы старой школы (например, игры для MS-DOS) делили круг на 2^x (512 или 256) бинарных степеней. Этот старый обычай 360 градусов бесполезен в компьютерах. - person rodrigo; 04.05.2012