Избегание арифметики с плавающей точкой

Question

Я написал небольшой программный синтезатор для iPhone.
Для дальнейшей настройки производительности я измерил свое приложение с Shark и обнаружил, что теряю много времени в конверсиях float/SInt16.
Итак, я переписал некоторые части, чтобы обойти преобразования, предварительно вычислив таблицы поиска, которые возвращают «готовые к использованию» образцы SInt16. Пока это прекрасно.
В настоящее время я пытаюсь переписать некоторые фильтры и реализацию конверта ADSR для использования только целочисленной арифметики, но я мог бы использовать некоторые подсказки, как выполнять умножения/деления без поплавков.
Я ориентируюсь в iPhone canonical format:

• LPCM
• 16-разрядного целого число выборок

Каких хорошие подходы применять амплитуду к моей последней выборке без использования поплавка?

Edit:
Единственное, что я понял, до сих пор есть, что я могу разделить на степени 2 по сдвига вправо мой текущий образец.

inBuffer[frame] = wavetable[i % cycleLengthInSamples] >> 4; 

Но я не могу придумать какой-либо элегантный способ создания гладкого конверта ADSR с этим.

Редактировать2: Спасибо за все ваши замечательные ответы!
Моего текущий подхода:

• принести всю мою ADSR конверта значения в положительный диапазон SInt16
• многократно с текущим значением из табличных (магазина промежуточных как SInt32)
• сдвига результата от 16 до право

это похоже на работу :)

Answer 1

Фиксированная точка хорошо, так как в этом Если вы используете 16 бит. Самый простой способ - умножить на мощность 10 в зависимости от требуемой точности. Если вы можете использовать 32-битные int в качестве промежуточного уровня, вы должны иметь возможность получить точную точность. В конце вы можете конвертировать обратно в 16-битный int, округлять или усекать, как вы предпочитаете.

Редактировать: Вы хотите сдвинуть влево, чтобы значения были больше. Сохраняйте результат сдвига в типе с большей точностью (32 или 64 бит в зависимости от того, что вам нужно). Простое переключение не будет работать, если вы используете подписанные типы

Остерегайтесь, если вы умножаете или делите два числа с фиксированной точкой. Умножение происходит вверх (a * n) * (b n), и вы закончите с b n^2 вместо b n. Подразделение (a n)/(b n), которое является (a/b) вместо ((a n)/b). Вот почему я предложил использовать полномочия 10, позволяет легко находить свои ошибки, если вы не знакомы с фиксированной точкой.

Когда вы закончите свои вычисления, вы переходите вправо, чтобы вернуться к 16-битовому int. Если вы хотите получить фантазию, вы также можете сделать округление перед сменой.

Предлагаю вам прочитать, если вы действительно заинтересованы в реализации эффективной фиксированной точки. http://www.digitalsignallabs.com/fp.pdf

Answer 2

Посмотрите на эту страницу, которая описывает алгоритмы быстрого умножения.

http://www.newton.dep.anl.gov/askasci/math99/math99199.htm

Answer 3

Ответы на this SO question довольно всеобъемлющими с точки зрения реализации. Вот немного больше объяснений, чем я видел там:

Один из подходов состоит в том, чтобы заставить все ваши номера в диапазоне, скажем [-1.0,1.0]. Затем вы сопоставляете эти числа в диапазоне [-2^15, (2^15) -1]. Например,

Half = round(0.5*32768); //16384 
Third = round((1.0/3.0)*32768); //10923 

Если умножить эти два числа вы получаете

Temp = Half*Third; //178962432 
Result = Temp/32768; //5461 = round(1.0/6.0)*32768 

разделив на 32768 в последней строке является точкой Patros составила около размножаются нуждающимися дополнительного шага масштабирования. Это имеет смысл, если вы явно пишете масштабирование 2^N:

x1 = x1Float*(2^15); 
x2 = x2Float*(2^15); 
Temp = x1Float*x2Float*(2^15)*(2^15); 
Result = Temp/(2^15); //get back to 2^N scaling 

Итак, это арифметика. Для реализации обратите внимание, что для умножения двух 16-разрядных целых чисел требуется 32-разрядный результат, поэтому Temp должен быть 32-битным. Кроме того, 32768 не представляется в 16-битной переменной, поэтому имейте в виду, что компилятор сделает 32-битные операторы. И, как вы уже отметили, вы можете перейти к умножить/разделить на степени 2, так что вы можете написать

N = 15; 
SInt16 x1 = round(x1Float * (1 << N)); 
SInt16 x2 = round(x2Float * (1 << N)); 
SInt32 Temp = x1*x2; 
Result = (SInt16)(Temp >> N); 
FloatResult = ((double)Result)/(1 << N); 

Но предположим, что [-1,1) не правильный диапазон? Если вы предпочитаете ограничить свои номера, скажем, [-4.0.4.0), вы можете использовать N = 13. Затем у вас есть 1 знаковый бит, два бита перед двоичной точкой и 13 после. Они называются дробными типами с фиксированной точкой 1.15 и 3.13 соответственно. Вы торгуете точностью во фракции для запаса.

Добавление и вычитание дробных типов прекрасно работает, пока вы смотрите на насыщение. Для деления, как сказал Патрос, масштабирование фактически отменяет. Таким образом, вы должны сделать

Quotient = (x1/x2) << N; 

или, чтобы сохранить Прецизионный

Quotient = (SInt16)(((SInt32)x1 << N)/x2); //x1 << N needs wide storage 

Умножение и деление на целые числа работает нормально. Так, например, разделить на 6, вы можете просто написать

Quotient = x1/6; //equivalent to x1Float*(2^15)/6, stays scaled 

А в случае деления на степень 2,

Quotient = x1 >> 3; //divides by 8, can't do x1 << -3 as Patros pointed out 

Сложение и вычитание целых чисел, хотя, не работает наивности , Вы должны сначала увидеть, подходит ли целое к вашему типу x.y, сделать эквивалентный дробный тип и продолжить.

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

Answer 4

В общем, скажем, вы будете использовать подписанное 16.16 фиксированное представление точки. Так что 32-битное целое будет иметь подписанную 16-битную целую часть и 16-битную дробную часть. Тогда я не знаю, какой язык используется в разработке iPhone, но этот пример в C (Objective-C, возможно?):

#include <stdint.h> 

typedef fixed16q16_t int32_t ; 
#define FIXED16Q16_SCALE 1 << 16 ; 

fixed16q16_t mult16q16(fixed16q16_t a, fixed16q16_t b) 
{ 
    return (a * b)/FIXED16Q16_SCALE ; 
} 

fixed16q16_t div16q16(fixed16q16_t a, fixed16q16_t b) 
{ 
    return (a * FIXED16Q16_SCALE)/b ; 
} 

Обрати внимание, что выше, является упрощенной реализацией, и не дает никакой защиты от арифметики переполнение. Например, в div16q16() я несколько перед делением для поддержания точности, но в зависимости от операндов операция может переполняться. Вы можете использовать 64-битное промежуточное звено, чтобы преодолеть это. Также разделение всегда округляется, потому что оно использует целочисленное деление. Это дает лучшую производительность, но может повлиять на точность итерационных вычислений. Исправления просты, но добавляются дополнительные накладные расходы.

Обратите внимание, что при умножении или делении на постоянную мощность-два большинство компиляторов обнаружит тривиальную оптимизацию и использует сдвиг. Однако C не определяет поведение для сдвига вправо от отрицательного целого числа со знаком, поэтому я оставил его компилятору для его работы для обеспечения безопасности и переносимости. YMV на любом языке, который вы используете.

В языке OO fixed16q16_t, естественно, является кандидатом на класс с перегрузкой оператора, поэтому вы можете использовать его как обычный арифметический тип.

Вы можете найти его полезным для преобразования между типами:

double fixed16q16_to_double(fixed16q16_t fix) 
{ 
    return (double)fix/FIXED16Q16_SCALE ; 
} 

int fixed16q16_to_int(fixed16q16_t fix) 
{ 
    // Note this rounds to nearest rather than truncates 
    return ((fix + FIXED16Q16_SCALE/2))/FIXED16Q16_SCALE ; 
} 

fixed16q16_t int_to_fixed16q16(int i) 
{ 
    return i * FIXED16Q16_SCALE ; 
} 

fixed16q16_t double_to_fixed16q16(double d) 
{ 
    return (int)(d * FIXED16Q16_SCALE) ; 
} 

Это основы, можно получить более сложные и добавить триг и другие математические функции.

Исправлено сложение и вычитание работает со встроенными операторами + и - и их вариантами.