APPLE divisão caindo

[Paul Curtis] sobre a Segger tem uma interessante série de posts sobre cálculo divisão. Isto costumava ser um tema mais quente, mas hoje em dia muitos computadores ou linguagens de computador tem suporte para multiplicação e divisão embutido. mas alguns processadores não têm as instruções e uma biblioteca para fazê-lo pode ser inferior a ideal. saber como rolar o seu próprio pode permitir que você otimizar a velocidade ou espaço. As tampas de parcelamento atuais utilizando o algoritmo de Newton para fazer a divisão.

Steve Martin teve um pouco famosa sobre como ser um milionário e nunca pagam impostos. Ele começou dizendo: “Primeiro … conseguir um milhão de dólares. Então …”Este método é um pouco como que desde que você primeiro tem que saber como multiplicar antes que você pode dividir. A premissa básica é duplo: o método de Newton permitem refinar a estimativa de uma recíproca por sucessivas multiplicações e multiplicando um número a recíproca é o mesmo que dividir. Em outras palavras, se precisamos dividir 34 por 6, você poderia reescrever 34/6 a 34 * 1/6 e a resposta é a mesma.

aproximação de Newton para recíprocos permite tirar um palpite sobre a resposta e depois refiná-lo através de uma série de multiplicações. Cada multiplicação cria uma melhor precisão. Você pode usar isso para executar a / espaço trade-off de velocidade clássico. Por exemplo, vamos supor que queremos encontrar o inverso de um byte (presumivelmente um ponto byte fixo). Uma tabela look-up de 256 elementos iria fornecer uma precisão perfeita e seria muito rápido. Não há mais a matemática é necessário. mas o que dizer de 32 bits? agora a mesa é muito grande. mas você pode olhar para cima, dizem, os primeiros 8 bits do número 32-bit. Ou mais. Ou menos. depende do que é importante para você.

Então agora você tem uma má estimativa do seu recíproco. Sir Issac pode torná-lo melhor. Para alguns número um, você toma sua estimativa (x) e multiplicá-los juntos. Subtrair esse número de 2 e você tem um fator para multiplicar sua estimativa de idade por ter uma nova estimativa. Pular à frente, é claro, se a sua estimativa estava certo, a multiplicação lhe daria 1 que não mudaria a velha estimativa em tudo. Se a estimativa estiver desligado, você vai ter um fator de escala.

Como uma fórmula que parece com isso:

x = x * (2-a * x);
Então, se você decidir o recíproco de 22 pode estar .02, a primeira passagem vai lhe dar:

0,02 * (2-22 * 0,02) = 0,0312

0,0312 * (2-22 * 0,0312) = 0,0410

0,0410 * (2-22 * 0,0410) = 0,0450
A resposta certa é uma dízima periódica 0.0454545 e se você continuar, você vai chegar lá.

Claro, então você tem que se multiplicam mais uma vez para fazer a divisão.

Nós gostaríamos que o posto tem uma implementação de ponto fixo e, em seguida, examina o código de montagem resultante de ARM, RISC-V, e dsPIC30. Vale a pena ler.

Nós amamos truques de matemática que podemos usar em linguagem assembly. Se você está trabalhando em AVR e ponto flutuante, não perca este método.