Evitando aritmética de ponto flutuante

Question

Eu escrevi um pequeno sintetizador de software para o iPhone.
Para ainda mais o desempenho melodia Eu medi a minha candidatura com tubarão e descobriu que eu estou perdendo muito tempo no flutuador conversões / SInt16.
Então eu reescrevi algumas partes para contornar as conversões por pré-cálculo lookup tabelas que retornam amostras SInt16 "ready-to-use". Isso funciona bem até agora.
Atualmente estou tentando reescrever alguns filtros e minha implementação ADSR envelope para usar somente inteiro aritmética, mas eu poderia usar alguns tipps como realizar multiplicações / divisões sem carros alegóricos.
Estou targetting o iPhone formato canônico :

• LPCM
• amostras inteiras de 16 bits

O que são boas abordagens para aplicar uma amplitude à minha amostra final sem usar um float?

Editar:
A única coisa que eu descobri até agora é, que eu possa dividir por potências de 2 por direito de mudança de minha amostra atual.

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

Mas eu não posso pensar de qualquer maneira elegante de criar um envelope ADSR suave com isso.

Edit2: Obrigado por todos os seus grandes respostas!
Minha abordagem atual:

• trazer todos os valores envelope meus ADSR para a faixa de SInt16 positivo
• multiplicar com o valor corrente da tabela de ondas (armazenar intermediários como SInt32)
• mudar o resultado por 16 para a direita

Isso parece funcionar:)

Answer 1

ponto fixo é bom, já que neste caso você está usando 16 bits. A maneira mais simples é multiplicar por uma potência de 10, dependendo da precisão que você precisa. Se você pode usar 32 ints bit como um intermediário, você deve ser capaz de obter precisão decente. No final você pode converter de volta para um de 16 bits int, arredondamento ou truncamento como você preferir.

Edit: Você quer desvio para a esquerda, para fazer os valores maior. Armazenar o resultado da mudança de um tipo com maior precisão (32 ou 64 bits, dependendo do que você precisa). mudança simples não vai funcionar se você estiver usando tipos assinados

Watch se você está multiplicar ou dividir dois números de ponto fixo. Multiplicando acaba sendo (a n *) * (b n) e você vai acabar com um b n ^ 2 em vez de um b n. A divisão é (a n) / (b n) que é (a / b) em vez de ((a n) / b). É por isso que sugeriu o uso de potências de 10, torna mais fácil para encontrar seus erros, se você não estiver familiarizado com o ponto fixo.

Quando você terminar seus cálculos, você mudar de volta para a direita para voltar a um 16 bit int. Se você quiser começar a fantasia, você também pode fazer o arredondamento antes de mudar.

Eu sugiro que você faça alguma leitura se você está realmente interessado em implementar ponto fixo eficiente. http://www.digitalsignallabs.com/fp.pdf

Answer 2

As respostas a esta pergunta SO são bastante abrangente em termos de implementação. Aqui está um pouco mais de uma explicação do que eu vi lá:

Uma abordagem é forçar todos os seus números em um intervalo, dizer [-1.0,1.0). Em seguida, mapear os números para o intervalo [-2 ^ 15, (2 ^ 15) -1]. Por exemplo,

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

Quando você multiplicar esses dois números que você começa

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

Dividindo por 32768 na última linha é o ponto Patros feitas sobre multiplica necessitam de um passo de escala adicional. Isto faz mais sentido se você escrever a 2 ^ N escala explicitamente:

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

Então essa é a aritmética. Para a implementação, nota que a multiplicação de dois números inteiros de 16 bits precisa de um resultado de 32 bits, por isso Temp deve ser de 32 bits. Além disso, 32768 não é representável em uma variável de 16 bits, por isso, estar ciente de que o compilador fará imediatos de 32 bits. E, como você já observou, você pode mudar para multiplicar / divisão por potências de 2 para que você possa escrever

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);

Mas suponha que [-1,1) não é o intervalo certo? Se preferir limitar seus números para, digamos, [-4.0,4.0), você pode usar N = 13. Então você tem 1 bit de sinal, dois bits antes do ponto binário, e 13 após. Estes são chamados 1.15 e 3.13 tipos fraccionais ponto fixo, respectivamente. Você troca precisão na fração de altura livre.

Adicionando e subtraindo tipos fracionários funciona bem, desde que você olhar para a saturação. Para dividir, como disse Patros, a escala realmente anula. Então você tem que fazer

Quotient = (x1/x2) << N;

ou, para preservar a precisão

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

multiplicar e dividir por números inteiros funciona normalmente. Por exemplo, para dividir por 6 você pode simplesmente escrever

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

E, no caso de se dividir por uma potência de 2,

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

Adição e subtração de números inteiros, porém, não funciona ingenuamente. Você tem que primeiro ver se os ajustes inteiros em seu tipo X.Y, fazer o tipo fracionário equivalente, e prosseguir.

Espero que isso ajude com a idéia, olhada no código em que outra questão para implementações limpas.

Answer 3

Tenha um olhar para esta página que descreve rápida multiplicação algoritmos.

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

Answer 4

Em geral, diga que você vai usar uma representação de ponto assinado 16.16 fixo. De modo que um número inteiro de 32 bits terá uma parte 16bit inteiro assinado e uma parte fracionária de 16 bits. Então eu não sei o que a linguagem é usada no desenvolvimento do iPhone, mas este exemplo é em C (Objective-C, talvez?):

#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 ;
}

Note que o acima é uma implementação simplista, e não fornece nenhuma proteção contra estouro aritmético. Por exemplo, em div16q16 () Eu múltiplos antes da divisão para manter a precisão, mas dependendo dos operandos a operação pode transbordar. Você pode usar um 64 bit intermediário para superar isso. Além disso, a divisão sempre arredonda para baixo, porque ele usa inteiro divisão. Isso dá um melhor desempenho, mas pode afetar a precisão dos cálculos iterativos. Correções são simples, mas adicionar à sobrecarga.

Note que ao multiplicar ou dividir por uma constante potência de dois, a maioria dos compiladores vai manchar a otimização trivial e usar um turno. No entanto C não define o comportamento para um shift direita de um número inteiro negativo assinado, então eu tê-lo deixado para o compilador para trabalhar com isso para a segurança e portabilidade. YMV em qualquer linguagem que você está usando.

Em uma linguagem OO, fixed16q16_t seria naturalmente um candidato para uma classe com sobrecarga de operador para que você possa usá-lo como um tipo de aritmética normal.

Você pode achar que é útil para converter entre os tipos:

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) ;
}

Isso é o básico, é possível obter mais sofisticados e adicionar trig e outras funções matemáticas.

adição fixo e subtração obras com o built-in + e -. operadores e suas variantes