Как выполнить небольшое приближение значения для sqrt (x) на FPGA

Я пытаюсь реализовать процедуру с фиксированной запятой, которая включает вычисление значения для малого которое приближается к . Целевая архитектура - FPGA. Одна из проблем заключается в том, что эта функция не может легко использоваться для расширения Тейлора. Можно видеть, что для малых значений x наклон стремится к бесконечности, когда приближается к , поэтому оценка функции с использованием степенного ряда включает умножение огромных коэффициентов на маленький . Поэтому этот метод численно нестабилен.$\sqrt{x}$$x$$0$$\sqrt{x}$$x$$0$$x$

Используя итерационный подход, Ньютон-Рафсон дает следующее итеративное уравнение: , где мы находимся пытаясь приблизить . Но еще раз, поскольку мала, также должен быть маленьким, чтобы решение сходилось. Так как уравнение включает в себя деление небольшого числа на другое небольшое число, есть вероятность, что арифметика с фиксированной точкой потерпит неудачу.$x_{n+1} = \frac {x_{n}}{2}- \frac{\alpha} {2x_{n}}$$\sqrt {\alpha}$$\alpha$$x_{n}$

При этом я хотел бы знать, как реализовать приближение малых значений для используя арифметику с фиксированной точкой, используя предварительно вычисленные коэффициенты или итерационные методы.$\sqrt{x}$

Подпрограмма, которую я использовал ранее (я не знаю, является ли она «правильной» или нет), является подходом «разделяй и властвуй».

Вы начинаете с произвольного верхнего и нижнего значения (скажем, 5 и 0 соответственно - самый высокий и самый низкий квадратные корни, которые вы хотите найти) и находите среднюю точку между ними. Квадрат это значение.

Если значение в квадрате больше, чем ваша цель, установите верхнее значение в качестве значения в квадрате. Если оно ниже, установите меньшее значение.

Повторяйте до тех пор, пока либо квадратное значение не совпадет с вашим значением поиска, либо вы выполнили достаточно итераций, чтобы быть настолько точными, насколько вам нравится.

Вот небольшая версия, которую я собрал в 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";

Это, конечно, использует с плавающей запятой, но можно легко адаптировать к фиксированной точке. Вы можете изменить точность, изменив предел итерации. Каждая итерация становится немного более точной, чем предыдущая.

Например: - найти квадратный корень из 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

Если бы он нашел значение 3, он бы остановился рано, конечно.

Дайте ему достаточно итераций, и он должен получиться очень точным:

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

Вот некоторые идеи и процедуры от Вознесенного Трансцендентного Мастера / Гуру Скотта Даттало здесь .
Это, конечно, шутка, кроме части гуру (Гуру?). Скотт великолепен.

Актуальное обсуждение. 2005 и PIC, а некоторые - C, но могут иметь значение.

Скотт снова - 2003

Два Мастера !!!
Датталло и Головченко.
Диапазон методов

Вы не указали, что вы подразумеваете под «малым значением» или «приближением». Так что то, что я собираюсь предложить, может не сработать, но здесь идет.

Самым простым было бы составить справочную таблицу. По сути это ПЗУ, в котором адресная шина - это число, которое вы хотите получить в квадратном корне, а вывод данных - это результат. С одним BRAM вы можете сделать 9-битный, 8-битный LUT. Конечно, больше БРАМов даст вам больший стол.

(BRAM = термин Xilinx для Block RAM, который также может использоваться в качестве ROM. Другие FPGA имеют аналогичные вещи.)

Если вам нужна большая точность, чем дает BRAM, вы можете выполнить простую линейную интерполяцию двух записей LUT. Например, предположим, что вы хотите 12-битный вход, но у вас есть только BRAM для 10 бит. Вы берете первые 10 бит вашего ввода и смотрите это в LUT. Добавьте 1 к этим 10 битам и посмотрите это значение тоже. Затем вы выполняете простую линейную интерполяцию между двумя результатами, используя нижние 2 бита, чтобы определить пропорцию одного значения к другому. Конечно, это только даст вам приближение, но я думаю, что если вы сделаете математику, вы обнаружите, что она может быть достаточно хорошей.

Этот метод является наименее точным с числами с низким значением, но поскольку входные данные переходят к более высоким значениям, точность повышается.

Оптимизация вышеупомянутого метода будет заключаться в использовании BRAM в качестве двухпортового ПЗУ. Таким образом, вы можете прочитать два значения без увеличения количества используемых BRAM. Это также позволит вам рассчитать SQRT для каждого тактового цикла с некоторыми задержками в конвейере.

Кстати, этот метод работает и для SINE / COSINE!

Попробуйте следующий подход

• Если число отрицательное, обработайте соответственно.
• Если число равно 0, верните 0.
• В противном случае:
• нормализуйте до числа в диапазоне [1/4, 1]: посчитайте, сколько раз k вам нужно умножить свое число на 4 ( x <<= 2в C), пока оно не окажется в вышеуказанном диапазоне.
• использовать произвольный подход (полиномиальные приближения, метод Ньютона для sqrt a [n] = (a [n-1] + k / a [n-1]) / 2 и т. д.) для вычисления квадратного корня в этом диапазоне
• денормализация: сдвиг вправо на k бит

Пытаться $x=(y+d)^2 \approx y^2+2dy$ так что давайте $d=(x-y^2)/2y = (x/y-y) \gg 1$ и следующий $y=y+d.$ Если MSb n справа, пусть сначала$y=1 \ll (n/2)$, Сходится за <4 итерации.

Попробуйте: улучшенное гадание для 1-й переменной

Ваше число может быть рассмотрено: A * 2 ^ n
1-е приближение тогда: A * 2 ^ (n / 2)

Допустим, вы используете 32-разрядное число, а 24-разрядные используются для хранения дробей. Для чисел> 1:
1. Подсчитать количество битов, используемых в целочисленной части (N)
2. Половину этого числа (N '= N / 2, т. Е. 1 бит со
смещением вправо ) 3. Смещение вправо исходного числа на N' Это ваше первое предположение.

В этом формате наименьшее число, которое вы можете иметь, составляет 2 ^ -24. Квадратный корень будет около 2 ^ -12. Итак, для чисел <1:
1. Подсчитайте количество «нулевых» битов в дроби, пока не достигнете установленного бита (N)
2. Половину этого числа (N '= N / 2, т. Е. 1 бит, сдвинутый вправо)
3. ВЛЕВО сдвиньте оригинальное число на пересмотренный счет: это ваше первое предположение.

Пример:
0,0000 0000 0000 0000 1 [16 ведущих нулей] приближается к: 0,0000 0000 1

Наконец, если у вас все еще есть проблемы с маленьким А: можете ли вы рассчитать 1 / А?
Если это так, то инвертируйте свой номер и попробуйте использовать алгоритм обратного квадратного корня:
x' = 0.5x * (3 - Ax^2)