Como executar uma aproximação de valor pequeno para sqrt (x) no FPGA

Estou tentando implementar uma rotina de ponto fixo que envolve calcular o valor de $\sqrt{x}$ para pequenas $x$que se aproxima de . A arquitetura de destino é um FPGA. Um problema é que essa função não se presta facilmente ao uso da expansão de Taylor. Pode-se ver que, para pequenos valores de x, a inclinação de atinge o infinito quando aproxima de , portanto, avaliar a função usando uma série de potências envolve a multiplicação de coeficientes enormes por um pequeno . Este método é, portanto, numericamente instável.$0$$\sqrt{x}$$x$$0$$x$

Usando uma abordagem iterativa, o Newton-Raphson produz a seguinte equação iterativa: , onde estamos tentando aproximar . Porém, mais uma vez, como é pequeno, mesma forma teria que ser pequeno para a solução convergir. Como a equação envolve dividir um número pequeno por outro número pequeno, é provável que a aritmética do ponto fixo falhe.$x_{n+1} = \frac {x_{n}}{2}- \frac{\alpha} {2x_{n}}$$\sqrt {\alpha}$$\alpha$$x_{n}$

Com isso, gostaria de saber como implementar uma aproximação de valor pequeno para usando aritmética de ponto fixo, usando coeficientes pré-computados ou métodos iterativos.$\sqrt{x}$

Uma rotina que eu usei antes (não sei se é "adequada" ou não) é uma abordagem de dividir e conquistar.

Você começa com um valor superior e inferior arbitrário (digamos 5 e 0 respectivamente - as raízes quadradas mais alta e mais baixa que deseja encontrar) e encontra o ponto médio entre elas. Quadrado esse valor.

Se o valor ao quadrado for maior que o seu objetivo, defina o valor superior como seu valor ao quadrado. Se for menor, defina o valor mais baixo.

Repita até que o valor do quadrado corresponda ao seu valor de pesquisa ou você tenha executado iterações suficientes para ter a precisão que desejar.

Aqui está uma pequena versão que reuni em perl:

#!/usr/bin/perl

my $val = shift;

my $max = 5;
my $min = 0;

my $iterations = 0;
my $maxiter = 40;

while(($max > $min) and ($iterations<$maxiter))
{
    $iterations++;
    my $diff = $min + ($max - $min) / 2;
    my $square = $diff * $diff;

    if($square == $val)
    {

        print "Square root found at $diff\n";
        print "$iterations iterations\n";
        exit(0);
    } else {
        if($square > $val)
        {
            $max = $diff;
        } else {
            $min = $diff;
        }
    }
}

my $diff = $min + ($max - $min) / 2;
print "Approximate square root after $iterations iterations: $diff\n";

Obviamente, isso está usando ponto flutuante, mas pode ser facilmente adicionado ao ponto fixo. Você pode variar a precisão alterando o limite de iteração. Cada iteração fica um pouco mais precisa do que a anterior.

por exemplo: - encontre a raiz quadrada de 9:

Approximate square root after 40 iterations: 2.99999999999955
   - or - 
Approximate square root after 10 iterations: 3.00048828125
   - or - 
Approximate square root after 5 iterations: 3.046875

Se tivesse encontrado o valor 3, teria parado cedo, é claro.

Faça iterações suficientes e deve ser muito preciso:

./sqrt.pl 0.00284
Square root found at 0.0532916503778969
59 iterations

Aqui estão algumas idéias e rotinas do mestre / guru transcendente ascendente Scott Dattalo aqui .
É claro que isso é uma piada, exceto a parte do guru (Guru?). Scott é excelente.

Discussão relevante. 2005 e PIC e alguns são C, mas podem ser úteis.

Scott novamente - 2003

Dois Mestres !!!
Dattallo e Golovchenko.
Uma variedade de métodos

Você não especificou o que quer dizer com "pequeno valor" ou "aproximação". Então, o que estou prestes a propor pode não funcionar, mas aqui vai.

O mais fácil seria criar uma tabela de consulta. Essencialmente, uma ROM em que o barramento de endereços é o número que você deseja com raiz quadrada e a saída de dados é o resultado. Com um único BRAM, você poderia fazer um LUT de 9 bits e 8 bits. Obviamente, mais BRAM's oferecem uma mesa maior.

(BRAM = O termo Xilinx para uma RAM de bloco, que também pode ser usado como ROM. Outros FPGAs têm coisas semelhantes.)

Se você quiser mais precisão do que o BRAM fornecer, poderá fazer uma interpolação linear simples de duas entradas LUT. Por exemplo, digamos que você queira uma entrada de 12 bits, mas você só tem BRAMs para 10 bits. Você pega os 10 bits mais importantes da sua entrada e consulta isso no LUT. Adicione 1 a esses 10 bits e procure também esse valor. Em seguida, você faz uma interpolação linear simples entre os dois resultados, usando os 2 bits inferiores para informar a proporção de um valor sobre o outro. Claro que isso só lhe dará uma aproximação, mas acho que se você fizer as contas, descobrirá que isso pode ser bom o suficiente.

Este método é o menos preciso com números de baixo valor, mas conforme a entrada aumenta para valores mais altos, a precisão aumenta.

Uma otimização do método acima seria usar os BRAMs como uma ROM de porta dupla. Dessa forma, você pode ler dois valores sem aumentar o número de BRAMs usados. Isso também permitirá que você calcule um SQRT para cada ciclo de clock, com alguns atrasos na tubulação.

Aliás, este método também funciona para SINE / COSINE!

Tente a seguinte abordagem

• Se o número for negativo, manuseie de acordo.
• Se o número for 0, retorne 0.
• De outra forma:
• normalize para um número no intervalo [1/4, 1]: conte quantas vezes k você precisa multiplicar seu número por 4 ( x <<= 2em C) até que esteja dentro do intervalo acima.
• use uma abordagem arbitrária (aproximações polinomiais, método de Newton para sqrt a [n] = (a [n-1] + k / a [n-1]) / 2, etc.) para calcular a raiz quadrada dentro desse intervalo
• desnormalizar: deslocar para a direita em k bits

Tentar $x=(y+d)^2 \approx y^2+2dy$ então deixe $d=(x-y^2)/2y = (x/y-y) \gg 1$ e a seguir $y=y+d.$ Se MSb for n da direita, deixe primeiro$y=1 \ll (n/2)$. Converge em <4 iterações.

Tente: adivinhação aprimorada da 1ª variável

Seu número pode ser considerado: A * 2 ^ n
A primeira aproximação é então: A * 2 ^ (n / 2)

Digamos que você esteja usando um número de 32 bits, com 24 bits usados ​​para armazenar frações. Para números> 1:
1. Conte o número de bits usados ​​na parte inteira (N)
2. Reduza pela metade esse número (N '= N / 2, ou seja,
desloque- se 1 bit para a direita ) 3. Desloque à direita o número original por N' : esse é seu primeiro palpite.

Nesse formato, o menor número que você pode ter é 2 ^ -24. A raiz quadrada terá cerca de 2 ^ -12. Portanto, para números <1:
1. Conte o número de bits "zero" na fração, até atingir um bit definido (N)
2. Divida pela metade esse número (N '= N / 2, ou seja, 1 bit com a direita deslocada)
3. ESQUERDA, desloque o número original pela contagem revisada: este é seu primeiro palpite.

Exemplo:
0,0000 0000 0000 0000 1 [16 zeros à esquerda] se aproxima de: 0,0000 0000 1

Finalmente, se você ainda tiver problemas com o A pequeno: você pode calcular 1 / A?
Nesse caso, inverta seu número e tente usar o algoritmo Raiz quadrada inversa:
x' = 0.5x * (3 - Ax^2)