Como calcular a função Sin com mais rapidez e precisão?

8

Quero calcular y(n)=32677Sin(45/1024•n)onde yé um número inteiro e nvaria de 0 a 2048. Como posso tornar esse processo mais rápido e mais preciso? Agora, quero mostrar uma resposta de referência: Desde Sin(a+b)=Sin(a)Cos(b)+Cos(a)Sin(b) And Cos(a+b)=Cos(a)Cos(b)-Sin(a)Cos(b). Para que eu possa armazenar Sin(45/1024•1)e Cos(45/1024•1)somente. Em seguida, use esta fórmula:

Sin(45/1024•2)=Sin(45/1024•1+45/1024•1), Cos(45/1024•2)=Cos(45/1024•1+45/1024•1), Sin(45/1024•n)=Sin(45/1024•(n-1)+45/1024•1), Cos(45/1024•n)=Cos(45/1024•(n-1)+45/1024•1), Desta forma, talvez mais rápido sem armazenar grande variedade.

c++ algorithms LaiJong
fonte
Esta pergunta é apropriada para programadores, assumindo que a intenção é aprender sobre os algoritmos e / ou estruturas de dados apropriados, da perspectiva das preocupações de engenharia de software.
Thomas Owens
8
Aquele 45 é um pouco suspeito; isso me faz pensar que você quer sin(x)onde xestá em graus. Se for esse o caso, você deve estar ciente de que o argumento para as funções trigonométricas é tipicamente em radianos. O argumento está em radianos em C ++, que é como essa pergunta é marcada.
David Hammen
Por que você precisa desta pergunta respondida? Qual é a aplicação?
GlenPeterson
Quão preciso você precisa que o resultado seja?
dan04
@ dan04 Como y é um número inteiro, preciso dele preciso como um número inteiro.
LaiJong 9/10/12

Respostas:

18

Se nvaria de 0 a 2048, você pode pré-calcular os valores, armazenar em uma matriz. y(n)se tornaria values[n].

vartec
fonte
+1 e você pode interpolar para quaisquer valores intermediários (se isso for possível).
Daniel B
1
Essa é uma opção viável, embora eu ainda a defina como perfil para garantir que seja mais eficiente do que calculá-la (por exemplo, as FPUs fsinpodem ser usadas e mais amigáveis ​​ao cache do que alguma matriz).
Benjamin Bannier
Que tal não armazenar valor [n]?
LaiJong
3
As funções trigonométricas são muito lentas para calcular em tempo real. Tenho certeza de que toda implementação rápida usa valores pré-calculados. Como sin () e cos () são periódicos, você só precisa armazenar os primeiros 90 graus. Você pode retornar -sin (), ou sin (90 - o ângulo), ou -sin (90 - o ângulo), dependendo do quadrante. Você também pode definir cos () em termos de sin (). Se você conhece o possível intervalo de valores de entrada, é possível pré-calcular e armazenar apenas os valores necessários para o seu programa. Caso contrário, a interpolação entre um número limitado de valores pode ser sua opção mais rápida.
GlenPeterson
1
@ Glen: os valores do pecado estão entre -1 e 1, então ele realmente se encaixa em 16 bits sem sinal.
vartec 9/10/12
1

Calcule a tabela no tempo de compilação em vez do tempo de execução.

Você está criando uma tabela de 2048 elementos de valores inteiros em escala de 16 bits.

Escreva um script Matlab barato, com uma impressão que ofereça uma linha de dados adequada para sua linguagem de programação final. Recorte e cole o resultado no seu código-fonte, como uma tabela de dados constante, e faça uma pesquisa de tabela no tempo de execução. Isso leva o tempo de computação inicial para o ciclo de construção, em vez do tempo de inicialização do programa.

John R. Strohm
fonte
Quanto tempo de execução economiza em comparação com o custo extra do programador?
JBRWilkinson
Rapido e sujo. Agradável.
quant
1

Dada a forma da função, a resposta natural é o algoritmo CORDIC . É uma abordagem muito mais limpa do que a quebra na questão. Por outro lado, a tabela de que precisa é muito, muito menor do que a que outros sugeriram.

MSalters
fonte