Por que o algoritmo CORDIC mora de graça no meu coração
Evitando Floating Point com o uso de Fixed Point
- Ao usar Fixed Point em vez de Floating Point, é possível representar números reais
- Usando um inteiro de 32 bits, os 16 bits superiores são usados para a parte inteira e os 16 bits inferiores para a parte fracionária
- Com isso, é possível representar aproximadamente de -32768.99997 até 32767.99997
- O programador pode definir a posição do ponto fixo para ajustar a precisão
- Para converter de Float para Fixed Point, multiplica-se por 2^16 e depois faz-se cast para
int32_t
- Para converter de Fixed Point para Float, divide-se por 2^16
- Soma e subtração funcionam diretamente, enquanto multiplicação e divisão exigem ajuste do fator de escala
Visão geral do algoritmo CORDIC
- CORDIC é a sigla de "Co-ordinate Rotation Digital Computer" e foi desenvolvido em meados da década de 1950
- É um método para obter valores de seno e cosseno rotacionando gradualmente um vetor sobre o círculo unitário em pequenos ângulos
- De forma semelhante à busca binária, ele se aproxima do ângulo-alvo movendo-se primeiro por ângulos maiores e depois reduzindo o ângulo pela metade no sentido horário ou anti-horário até convergir
- O ângulo máximo de rotação é 90 graus (
π/2 radiano), e o processo é repetido 16 vezes para convergir ao ângulo desejado
- O valor de
y do vetor convergido é aproximadamente sin(a), e o valor de x é aproximadamente cos(a)
Simplificação da matriz para usar apenas multiplicação por constantes
- A matriz de rotação inclui as funções seno, cosseno e tangente, o que torna o cálculo complexo
- Como a função tangente usa ângulos fixos de rotação, seus valores podem ser pré-calculados e armazenados em uma tabela (cerca de 64 bytes)
- O termo do cosseno aparece em todas as iterações, mas como seu valor convergente é constante (aproximadamente 0.6366), basta multiplicar uma única vez no final
Usando apenas operações de Shift e Add
- Os ângulos usados na função tangente são escolhidos com a função arco-tangente como valores de
2^-i
- Com isso, a multiplicação pode ser substituída por operações de deslocamento de bits
- O valor convergente do termo do cosseno também é recalculado e passa a ser aproximadamente 0.60725, sendo definido como o valor inicial de
x do vetor
- Cada iteração do algoritmo CORDIC é simplificada da seguinte forma
- Se
z for maior ou igual a 0, rotaciona no sentido anti-horário (subtrai y>>i de x, soma x>>i a y)
- Se
z for menor que 0, rotaciona no sentido horário (soma y>>i a x, subtrai x>>i de y)
- Atualiza
z subtraindo ou somando o valor do ângulo da tabela
- Assim, torna-se possível calcular funções trigonométricas usando apenas multiplicação por constantes, deslocamentos de bits e somas
Opinião do GN⁺
- O CORDIC parece ser um algoritmo bastante útil em ambientes com recursos de hardware limitados, como sistemas embarcados ou FPGA. É uma abordagem especialmente válida quando não há suporte a operações de ponto flutuante.
- A ideia de escolher estrategicamente os ângulos da função tangente para substituir multiplicações por deslocamentos de bits é impressionante. É um ótimo exemplo da combinação entre percepção matemática e entendimento de arquitetura de computadores.
- Também é interessante que ele possa ser usado não só para funções trigonométricas, mas também para calcular logaritmos, exponenciais, raiz quadrada e outras funções. Vale a pena olhar também o algoritmo relacionado BKM.
- Por outro lado, muitos hardwares modernos já vêm com FPU embutida, e operações em ponto fixo podem causar perda de precisão, então é preciso cuidado ao aplicar essa técnica.
- Em sistemas que precisam realizar muitos cálculos semelhantes, talvez também valha considerar o projeto de hardware dedicado ao CORDIC.
1 comentários
Comentários do Hacker News
O algoritmo CORDIC pode ser usado não só em FPGA, mas também em desenvolvimento de jogos e simulações físicas distribuídas. Cálculos em ponto flutuante dificultam garantir comportamento determinístico entre plataformas, então implementar um motor de física em ponto fixo e usar CORDIC para funções trigonométricas pode ser uma solução.
O CORDIC pode ser usado não apenas para seno e cosseno, mas também para logaritmos, exponenciais, raiz quadrada, magnitude de vetores, conversão entre coordenadas polares e cartesianas, rotação de vetores e outras operações. Com quaternions, parece possível realizar operações baseadas em CORDIC de forma mais eficiente e precisa.
Relato de alguém que aprendeu numa aula de pré-cálculo no ensino médio sobre a implementação de funções trigonométricas em calculadoras e depois descobriu que não era série de Taylor, mas sim CORDIC, chegando a implementar isso por conta própria em TI Basic.
Em 2023, até MCUs baratos como o STM32G4 já trazem FPU embutida, então é possível usar ponto flutuante livremente em vez de ponto fixo. Mas o G4 também tem um periférico CORDIC implementado em hardware dedicado, o que parece servir para evitar perda de precisão de ponto flutuante.
Parece haver um erro na explicação de que uma rotação de 22,75° é igual a uma rotação de 45° seguida de uma de -22,5°. Ao que tudo indica, o correto seria 22,5°.
O sistema de octree de Meagher foi implementado apenas com operações inteiras, sem multiplicação/divisão inteira. Isso facilita a criação de hardware acelerador gráfico VLSI rápido e sob medida para representar octrees.
O CORDIC pode ser visto como um conceito semelhante à sequência de Farey para ângulos, ou ao mediant, a soma ingênua de frações.
O CORDIC também foi implementado em calculadoras programáveis HP vintage com CPU de 4 bits. Métodos de aproximação usando a expansão de Taylor da função seno também podem ser programados.
Se você gostou deste texto, também vale a pena ler o clássico de Donald Knuth, "The Art of Computer Programming", que explica algoritmos matemáticos com exemplos.
O CORDIC foi um algoritmo muito popular na área de DSP antigamente.
É um algoritmo muito legal e parece útil para executar redes neurais em hardware de baixo desempenho.