Conheci o CORDIC ao pesquisar como as calculadoras de bolso funcionam. O algoritmo original foi usado para calcular as funções trigonométricas usando apenas operações de adição, subtração e shift. Alterações do algoritmo posteriormente permitiram o cálculo de funções logaritmicas, hyperbólicas, multiplicação, divisão e raiz quadrada. Isto acabou resultando na primeira calculadora científica de bolso a HP-35. O uso em calculadoras portáteis se deve ao fato deste tipo de hardware ser limitado, sem a presença de um processador matemático.
revisão de conteúdo para entender o algoritmo CORDIC ver
Matrizes de Rotação no R2
Sistemas Lineares e Determinantes: Origens e Desenvolvimento
Cayley e a Teoria das Matrizes
Ótimo o texto CORDIC For Dummies onde explica a tecnica em termos de busca binária
[01.05.18]
A coleção FORTH Dimensions é um conjunto de revistas da década de 80 com foco na linguagem Forth. No Volume 5 Nº 3 (V5N3) tem uma explicação sobre o algoritmo CORDIC e uma referência à edição V4N1 por seu bom material em "fixed-point arithmetic"
Link
Forth no STM32F103 (comprei o ST-Link v2)
quarta-feira, 25 de abril de 2018
sexta-feira, 6 de abril de 2018
Exemplo de Uso com FFT
Multiplicação de inteiros com FFT
Como é que isto se faz? (https://blol.org/94-multiplicacao-com-fft)
1 - Transformar os números a multiplicar num polinómio, escolhendo uma base apropriada (e.g. 10, 16, 2^32, etc).
2 - Calcular a DFT de ambos, através do uso de uma FFT. (Não é necessário ser estritamente a FFT, qualquer convolução em teoria dá.) [interessante]
3 - Multiplicar ponto a ponto ao longo do array obtido (multiplicação diádica).
4 - Calcular a DFT inversa do resultado.
5 - Avaliar o polinómio para obter o número final.
do site LeGauss
entendimento passa pela Matriz de Vandermonde (é uma matriz em que os termos de cada linha estão em progressão geométrica, ela surge naturalmente do problema de interpolação polinomial.)
mais ou menos assim (da wikipedia Algoritmo Schönhage-Strassen)
para multiplicar 147 e 258 (em decimal), serão realizadas as seguintes operações:
Representação de 147 como x^2+4x+7 e 258 - como 2x^2+5x+8, onde x = 10.
Multiplique polinômios x^2+4x+7 e 2x^2+5x+8 usando a transformada rápida de Fourier. Obter o produto dos polinômios 2x4+13x^3+42x^2+67x+56.
Ao fazer transferências entre as fileiras, temos 3x4+7x^3+9x^3+2x+6., ou seja, 37.926.
interpolar - método que permite construir um novo conjunto de dados a partir de um conjunto discreto de dados pontuais previamente conhecidos (wikipedia)
interolação polinomial - dado um conjunto de dados (pontos) achar um polinomio que passe por estes pontos
Como é que isto se faz? (https://blol.org/94-multiplicacao-com-fft)
1 - Transformar os números a multiplicar num polinómio, escolhendo uma base apropriada (e.g. 10, 16, 2^32, etc).
2 - Calcular a DFT de ambos, através do uso de uma FFT. (Não é necessário ser estritamente a FFT, qualquer convolução em teoria dá.) [interessante]
3 - Multiplicar ponto a ponto ao longo do array obtido (multiplicação diádica).
4 - Calcular a DFT inversa do resultado.
5 - Avaliar o polinómio para obter o número final.
do site LeGauss
entendimento passa pela Matriz de Vandermonde (é uma matriz em que os termos de cada linha estão em progressão geométrica, ela surge naturalmente do problema de interpolação polinomial.)
mais ou menos assim (da wikipedia Algoritmo Schönhage-Strassen)
para multiplicar 147 e 258 (em decimal), serão realizadas as seguintes operações:
Representação de 147 como x^2+4x+7 e 258 - como 2x^2+5x+8, onde x = 10.
Multiplique polinômios x^2+4x+7 e 2x^2+5x+8 usando a transformada rápida de Fourier. Obter o produto dos polinômios 2x4+13x^3+42x^2+67x+56.
Ao fazer transferências entre as fileiras, temos 3x4+7x^3+9x^3+2x+6., ou seja, 37.926.
interpolar - método que permite construir um novo conjunto de dados a partir de um conjunto discreto de dados pontuais previamente conhecidos (wikipedia)
interolação polinomial - dado um conjunto de dados (pontos) achar um polinomio que passe por estes pontos
quinta-feira, 5 de abril de 2018
Algumas anotações sobre análise de Séries Temporais
Análise de Séries Temporais
do artigo
A comprehensive beginner’s guide to create a Time Series Forecast
https://www.analyticsvidhya.com/blog/2016/02/time-series-forecasting-codes-python/|https://www.analyticsvidhya.com/blog/2016/02/time-series-forecasting-codes-python
Muitos modelos de análise partem do princípio que uma ST é estacionária
Como checar se uma ST é estacionária?
analisando suas propriedades estatísticas: se a média e a variância permanecem constantes no tempo
Idéia geral: se uma ST tem um comportamento particular no tempo, há uma alta probabilidade que ela seguirá a mesma no futuro.
Teste de estacionariedade:
- Plotar a série temporal e ver graficamente tendências e sazonalidades
- plotar a média móvel (ou variância móvel) e ver se varia ao longo do tempo, estes valores não tendem a aumentar em uma ST estacionária
- teste de Dickey-Fuller
Como tornar uma série estacionária?
uma vez que:
Como estimar e eliminar trends?
com transformações, exemplo: log ou raiz quadrada
mas em presença de ruído talvez não seja tão intuitivo, então se usa outras técnicas uma delas é a tecnica de Alisamento (smoothing) da ST para isto toma-se a Média Móvel
do artigo
How to Use Power Transforms for Time Series Forecast Data with Python
https://machinelearningmastery.com/power-transform-time-series-forecast-data-python/|https://machinelearningmastery.com/power-transform-time-series-forecast-data-python
Square Root Transform
A time series that has a quadratic growth trend can be made linear by taking the square root
sendo a estrutura dos dados de natureza quadrática, com tendência ao crescimento neste caso, para fazer uma análise é importante que se tranforme esta ST em linear (onde a média e a variância não se alteram...) isto é feito com a operação inverça à operação quadrática que é a raiz quadrada.
o mesmo para transformação log, se os dados tem uma natureza exponencial ao longo do tempo, aplicando a invesa desta operação (log <=> exp) a série torna-se linear
Log Transform
A class of more extreme trends are exponential, often graphed as a hockey stick.
Time series with an exponential distribution can be made linear by taking the logarithm of the values. This is called a log transform.
pergunta a exclarecer, por falta de tempo
a final porque tranformar uma ST para linear? Linearidade é sinônimo de estacionário? (onde média e variância são constantes)
do artigo
A comprehensive beginner’s guide to create a Time Series Forecast
https://www.analyticsvidhya.com/blog/2016/02/time-series-forecasting-codes-python/|https://www.analyticsvidhya.com/blog/2016/02/time-series-forecasting-codes-python
Muitos modelos de análise partem do princípio que uma ST é estacionária
Como checar se uma ST é estacionária?
analisando suas propriedades estatísticas: se a média e a variância permanecem constantes no tempo
Idéia geral: se uma ST tem um comportamento particular no tempo, há uma alta probabilidade que ela seguirá a mesma no futuro.
Teste de estacionariedade:
- Plotar a série temporal e ver graficamente tendências e sazonalidades
- plotar a média móvel (ou variância móvel) e ver se varia ao longo do tempo, estes valores não tendem a aumentar em uma ST estacionária
- teste de Dickey-Fuller
Como tornar uma série estacionária?
uma vez que:
- Tendência: variação da média no tempo (ex: em média o número x está crescendo no tempo..)
- Sazonalidade: variações em frames de tempo específicos
Como estimar e eliminar trends?
com transformações, exemplo: log ou raiz quadrada
mas em presença de ruído talvez não seja tão intuitivo, então se usa outras técnicas uma delas é a tecnica de Alisamento (smoothing) da ST para isto toma-se a Média Móvel
do artigo
How to Use Power Transforms for Time Series Forecast Data with Python
https://machinelearningmastery.com/power-transform-time-series-forecast-data-python/|https://machinelearningmastery.com/power-transform-time-series-forecast-data-python
Square Root Transform
A time series that has a quadratic growth trend can be made linear by taking the square root
sendo a estrutura dos dados de natureza quadrática, com tendência ao crescimento neste caso, para fazer uma análise é importante que se tranforme esta ST em linear (onde a média e a variância não se alteram...) isto é feito com a operação inverça à operação quadrática que é a raiz quadrada.
o mesmo para transformação log, se os dados tem uma natureza exponencial ao longo do tempo, aplicando a invesa desta operação (log <=> exp) a série torna-se linear
Log Transform
A class of more extreme trends are exponential, often graphed as a hockey stick.
Time series with an exponential distribution can be made linear by taking the logarithm of the values. This is called a log transform.
pergunta a exclarecer, por falta de tempo
a final porque tranformar uma ST para linear? Linearidade é sinônimo de estacionário? (onde média e variância são constantes)
Assinar:
Postagens (Atom)