Nas curvas de Bezier e na velocidade do Arduino, parte dois

Passaremos por - e além

No meu post anterior, mostrei como você pode melhorar a velocidade dos pontos de cálculo em uma curva de Bezier (KB):

1. Transformações de fórmulas de cálculo - aceleração ~ 3 vezes.
2. Quase não há aceleração de PT para FT - mas permite 3.
3. A operação de substituição da divisão por multiplicação e deslocamento é uma aceleração de outros 40%.

No final do post mencionado, eu disse que os cálculos podem ser feitos ainda mais rapidamente, mas o que "o garoto disse - o garoto fez".

Deixe-me lembrá-lo mais uma vez da fórmula obtida para calcular o ponto no KB

$$

$$P = (A1 * e + B1) * e + C (=> 2 * 2 +)$$

O próximo aumento de velocidade está relacionado à peculiaridade do problema - precisamos não apenas calcular o valor de KB em diferentes valores do parâmetro “e”, mas encontrar uma série de valores ao alterar (neste caso, aumentar) esse parâmetro por um valor fixo conhecido (além disso). caso), que permite usar a técnica descrita abaixo. No meu tempo, isso foi chamado de método de cálculo da diferença (se a memória me serve bem, pelo menos era o que era chamado em palestras), toda a Internet está à sua disposição, talvez (mesmo com certeza), haja outro nome.

Consideramos o caso P = A * e (=> 1 *) e supomos que conhecemos o valor de P0 com algum argumento u0. Então o valor com o próximo argumento u0 + 1 pode ser calculado como P = A * (u0 + 1) = A * u0 + A = P0 + A (=> 1+). Sem perder precisão, fomos capazes de substituir a operação de multiplicação pela operação de adição, que é muito mais rápida.

Agora, um exemplo mais complexo P = A * e * e (=> 2 *), consideramos por analogia P = A * (e + 1) * (e + 1) = A * (e * e + 2 * e + 1) = A * e * e + 2 * A * e + A = P0 + 2 * A * e + A (=> 2 * 2 +). À primeira vista, não ganhamos nada, mas se calcularmos A '= 2 * A antecipadamente, obtemos (=> 1 * 2 +), uma vitória é bem possível. Mas não vamos parar no que foi alcançado com a expressão obtida A '* e aplicar a técnica já conhecida por nós, então obteremos duas operações em duas variáveis: P = P + A' + A; A '= A' + A (=> 3+). Se levarmos em conta que o valor inicial de A 'pode ser feito mais por A, em geral, existem apenas duas adições em vez de duas multiplicações. Sim, tivemos que obter duas variáveis ​​adicionais, mas essa é uma troca clássica - pagamos com memória pelo tempo.

Resta apenas calcular os valores iniciais corretos, mas isso é feito apenas uma vez no início das iterações e, se o valor inicial do parâmetro for u = 0, geralmente será trivial P = 0, A '= A. Testaremos nosso método em várias iterações (isso é completamente desnecessário, a matemática aplicada corretamente não pode dar a resposta errada), mas nos permitirá entender melhor o que está acontecendo. Então
iteração 0: e = 0; P = 0 (verdadeiro); A '= A; A '' = 2 * A;
iteração 1: e = 1; P = 0 + A '= 0 + A = A (verdadeiro); A '= A' + A '' = A + 2 * A = 3 * A;
iteração 2: e = 2; P = A + 3 * A = 4 * A (verdadeiro); A '= 3 * A + 2 * A = 5 * A;
iteração 3: e = 3; P = 9 * A (verdadeiro); A '= 7 * A e assim por diante.

Observamos a conexão entre as fórmulas obtidas e o método de Newton para calcular o valor de uma função na vizinhança de um ponto com um valor conhecido. Além disso, como nossa função é de segunda ordem e todas as derivadas, começando na terceira, são iguais a zero, podemos substituir com segurança o sinal de igual aproximado pelo exato. A única diferença desse método é que movemos constantemente o ponto em relação ao qual estamos construindo uma nova vizinhança, a fim de evitar a execução de operações de multiplicação na formulação original.

Reescreva nossa expressão original para KB em formato expandido

$$

$$P = A1 * e * e + B1 * e + C$$

então, para o cálculo usando este método, precisamos de 2+ para o primeiro termo (e duas variáveis), 1+ para o segundo termo (e uma variável) e 2+ para adicionar tudo (=> 5+). Pode-se esperar que mesmo essa abordagem (incorreta) traga um ganho em comparação com 2 * 2 +, mas tudo está muito melhor. Obviamente, a operação de adição é aditiva (obrigado, capitão), para que você possa agrupar os termos e substituir os termos constantes por novas expressões, o que fornece o seguinte algoritmo:

1. Os valores iniciais de P = C; A '= A1 + B1; A '' = 2 * A1;
2. no próximo passo P = P + A '; A '= A' + A '' (=> 2+), que é sem dúvida mais rápido que o esquema de Horner.

Implementamos nosso algoritmo na forma de um programa (isso não é tão trivial quanto parece, pois por simplicidade eu esqueci a necessidade de mudanças, mas não é muito difícil ... por 20 minutos), obtemos a complexidade computacional (=> 2 + 1 >>) e medimos velocidade - resultou em 140 (aumento de velocidade em mais 3 vezes) ciclos por ciclo, mas esse é um resultado quase ideal. O que precisamos fazer para obter a opção ideal (em certo sentido) é prestar atenção à dimensão dos operandos nas fórmulas. Agora, realizamos todas as operações em números inteiros longos (32 bits), e isso pode ser desnecessário em alguns lugares. Se reduzirmos a capacidade dos operandos ao mínimo necessário, obteremos um ganho de 20 a 25%, mas isso exigirá que troquemos para o montador (C não possui os meios adequados para essas operações) e analisemos cuidadosamente os dados do problema original. Se cabe ao leitor decidir se deve ou não fazê-lo, já aceleramos os cálculos mais de 1900/140 = 13 vezes em comparação com a abordagem "ingênua".

A última observação sobre a implementação do algoritmo é que ainda excluímos a operação de divisão, alterando-a por multiplicação constante, que levamos em consideração ao gerar os dados iniciais e deslocando-os por um múltiplo constante de 8. Isso pode ser feito de várias maneiras com tempos de execução ligeiramente diferentes, deixando esses experimentos à atenção de um leitor curioso .

No entanto, um problema surgiu completamente inesperadamente - vemos claramente duas operações de adição em números de 32 bits, que devem levar 4 + 4 = 8 ciclos de relógio, colocar outros 8 * 3 * 2 = 48 ciclos de relógio para enviar operandos, 4 ciclos de relógio para receber o resultado do turno, 4 um ciclo de relógio para chamar o procedimento de cálculo e retorno e 4 ciclos de relógio para organizar o ciclo - de onde outros 60 ciclos de relógio não são claros. Anteriormente, simplesmente não percebíamos isso no contexto de centenas de ciclos de relógio, mas agora você pode prestar atenção. Medidas excessivas foram facilmente encontradas - no ciclo, houve operações de depuração desnecessárias; se você limpar tudo com cuidado, restarão apenas 120 medidas e o objetivo de cada uma será bastante compreensível (bem, não tão claro, mas ainda assim). Em seguida, descobrimos o tempo de execução do ciclo vazio - 22 medidas, imagino o que eles estão fazendo lá o tempo todo, mas tudo bem, e limpamos o tempo de cálculo real, que será de 98 ciclos. Observe que a estimativa da aceleração do trabalho obtida muda: em vez de 1900/140 = 13, obtemos (1900-50) / (140-40) = 19 vezes, o que não faz sentido prático, pois o ciclo ainda é necessário, mas permite aumentá-lo ainda mais auto-estima.

E a última observação - como é fácil ver, começamos a procurar e eliminar pulgas apenas quando lidamos com grandes besouros de veados e sua existência (pulgas) tornou-se óbvia e, além disso, significativa. Eu recomendo exatamente essa abordagem (e não estou sozinho nessa recomendação) ao otimizar os programas em termos de desempenho.

Bem, em conclusão, sobre a nota "em certo sentido" - se estamos falando sobre o cálculo seqüencial das coordenadas do próximo ponto no KB ao alterar o parâmetro (representando o tempo), então o algoritmo proposto (depois de todas as otimizações) não é mais possível melhorar. Mas se você reformular a tarefa e, por exemplo, definir o objetivo de simplesmente criar uma agência de design na tela (sem referência ao tempo), haverá um método muito promissor, a palavra-chave "Brezenheim", mas "esta é uma história completamente diferente", que vou dedicar em outro post (talvez um dia se a irmã mais velha não se importar).