способ и устройство вычисления квадратного корня

Классы МПК:G06F7/552 для возведения в степень или извлечения корня
Автор(ы):, ,
Патентообладатель(и):Открытое акционерное общество "Муромский завод радиоизмерительных приборов" (RU)
Приоритеты:
подача заявки:
2008-12-04
публикация патента:

Изобретение относится к вычислительной технике и может быть использовано в специализированных устройствах обработки информации. Техническим результатом является повышение быстродействия. Устройство содержит блок нормализации аргумента, блок вычисления полинома, который содержит схему исключения значений аргумента x<xmin, блок нормализации функции. 5 ил., 9 табл. способ и устройство вычисления квадратного корня, патент № 2438160

способ и устройство вычисления квадратного корня, патент № 2438160 способ и устройство вычисления квадратного корня, патент № 2438160 способ и устройство вычисления квадратного корня, патент № 2438160 способ и устройство вычисления квадратного корня, патент № 2438160 способ и устройство вычисления квадратного корня, патент № 2438160

Формула изобретения

Устройство вычисления квадратного корня, содержащее блок нормализации аргумента 1, вход которого является входом устройства, блок нормализации функции 3, выход которого является выходом устройства, отличающееся тем, что введен блок вычисления полинома 4, вход которого соединен с первым выходом блока нормализации аргумента 1, который содержит схему исключения значений аргумента x<xmin, a выход с первым входом блока нормализации функции 3.

Описание изобретения к патенту

Изобретение относится к вычислительной технике и может быть использовано в специализированных устройствах обработки информации.

Известно устройство для вычисления квадратного корня способ и устройство вычисления квадратного корня, патент № 2438160 , в котором вычисление функции производится за n циклов (n - число разрядов двоичного кода значения квадратного корня) с вычислением за каждый цикл одной значащей цифры результата путем выполнения в каждом цикле трех операций с разрядной цифрой ai результата [1].

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

Недостаток указанного способа и устройства состоит в низком быстродействии. За один итерационный цикл необходимо осуществить возведение пробного значения операнда в квадрат, сравнить его со значением x и на основании результата сравнения получить одну двоичную цифру значения квадратного корня.

Для получения результата с погрешностью метода способ и устройство вычисления квадратного корня, патент № 2438160 м<2-n необходимо осуществить 3n операций. Например, для вычисления квадратного корня с погрешностью способ и устройство вычисления квадратного корня, патент № 2438160 м=2-10способ и устройство вычисления квадратного корня, патент № 2438160 0,001 потребуется 30 операций.

Описан способ вычисления квадратного корня [2]. Способ обеспечивает значение относительной погрешности способ и устройство вычисления квадратного корня, патент № 2438160 м=10-4 (способ и устройство вычисления квадратного корня, патент № 2438160 м=2-13) при шести итерациях для окна аргумента xспособ и устройство вычисления квадратного корня, патент № 2438160 [0,4; 1,6] и отношение значений аргумента на концах интервала xmax/xmin=4. Для реализации способа и алгоритма необходимо осуществить 26 арифметических операций.

В то же время при использовании разработанного авторами более быстродействующего оптимизированного алгоритма способ и устройство вычисления квадратного корня, патент № 2438160 с начальным приближением y0=0,2936+0,8378·х на интервале хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-2; 1], что также соответствует отношению xmax/xmin=4, получено при двух итерациях (10 алгебраических операций) значение максимальной погрешности метода способ и устройство вычисления квадратного корня, патент № 2438160 м=1,42·2-11.

Еще более убедительной является реализация приближения функции способ и устройство вычисления квадратного корня, патент № 2438160 полиномом четвертой степени. На таком же интервале хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-2; 1] (8 алгебраических операций) получено значительно меньшее значение максимальной погрешности метода способ и устройство вычисления квадратного корня, патент № 2438160 м=1,43·2-13. Более эффективные результаты повышения быстродействия (это показано ниже, в статье, принятой к публикации) получены и для всего диапазона погрешностей способ и устройство вычисления квадратного корня, патент № 2438160 мспособ и устройство вычисления квадратного корня, патент № 2438160 [5; 0,001%] путем компьютерного моделирования. В связи с этим проведем исследование улучшения полиномиальных методов и алгоритмов вычисления квадратного корня. Эти исследования не являются очевидными и не следуют из уровня техники. Например, предлагается «хорошая» формула для вычисления квадратного корня на основе биномиального ряда Ньютона [3]. Но погрешность вычисления по данной формуле в 22n+1 раз; выше, чем при использовании полинома Чебышева степени n. В то же время и применение обычных полиномов Чебышева также неэффективно, поскольку при хспособ и устройство вычисления квадратного корня, патент № 2438160 0 производная fспособ и устройство вычисления квадратного корня, патент № 2438160 (x)способ и устройство вычисления квадратного корня, патент № 2438160 способ и устройство вычисления квадратного корня, патент № 2438160 . Поэтому при поиске полиномов наилучшего приближения путем моделирования необходимо учитывать и соразмерную погрешности метода способ и устройство вычисления квадратного корня, патент № 2438160 м погрешность дискретизации способ и устройство вычисления квадратного корня, патент № 2438160 д, соответствующую интервалу дискретизации способ и устройство вычисления квадратного корня, патент № 2438160 х=xmin. За счет этого рациональным является уменьшение интервала изменения аргумента до хспособ и устройство вычисления квадратного корня, патент № 2438160 [xmin; 1]. Следует вместо минимального значения х=0 (как в прототипе) взять значение xmin и за счет сокращения интервала интерполяции на величину хспособ и устройство вычисления квадратного корня, патент № 2438160 [0; xmin], особенно при хспособ и устройство вычисления квадратного корня, патент № 2438160 0, существенно уменьшить погрешность вычисления квадратного корня. При этом целесообразно брать способ и устройство вычисления квадратного корня, патент № 2438160 На далеко не очевидные и не простые вопросы инженерного решения задач извлечения квадратного корня обращено внимание в основополагающей работе [4] (с.16-17, с.117-118 и т.д.). Исследованию методов оптимизации приближения функциональных зависимостей посвящен и ряд статей авторов, прошедших рецензирование и принятых в печать.

Цель изобретения - повышение быстродействия.

Поставленная цель достигается тем, что в способе вычисления квадратного корня путем поиска кратных степени числа 2 границ диапазона нахождения аргумента внутри интервала изменения аргумента xспособ и устройство вычисления квадратного корня, патент № 2438160 [0; 1,6] предварительной нормализацией значения аргумента х=22S·xн к нормализованному интервалу xспособ и устройство вычисления квадратного корня, патент № 2438160 [0,4; 1,6] итерационным вычислением значений функции способ и устройство вычисления квадратного корня, патент № 2438160 с нулевым приближением полиномом V0=0,9604+0,3983 (х-1), погрешностью метода способ и устройство вычисления квадратного корня, патент № 2438160 м=0,01% по итерационной шесть раз повторяемой формуле способ и устройство вычисления квадратного корня, патент № 2438160 на нормализованном интервале xспособ и устройство вычисления квадратного корня, патент № 2438160 [0,4; 1,6]; последующим масштабированием нормализованного значения функции V' в действительное значение в соответствии с интервалом нахождения значения аргумента, определенном при нормализации аргумента, предлагается при оптимальном соотношении по точностным характеристикам, быстродействию и программно-аппаратным затратам для диапазона максимальной погрешности метода способ и устройство вычисления квадратного корня, патент № 2438160 мспособ и устройство вычисления квадратного корня, патент № 2438160 [5; 0,001%] производить интерполяцию нормализованного значения функции на нормализованном интервале способ и устройство вычисления квадратного корня, патент № 2438160 полиномом наилучшего приближения с погрешностью метода способ и устройство вычисления квадратного корня, патент № 2438160 м, равной или превышающей погрешность дискретизации способ и устройство вычисления квадратного корня, патент № 2438160 для интервала изменения аргумента xспособ и устройство вычисления квадратного корня, патент № 2438160 [xmin; 1].

По второму исполнению дополнительно к п.1 с целью повышения быстродействия при погрешности метода способ и устройство вычисления квадратного корня, патент № 2438160 мспособ и устройство вычисления квадратного корня, патент № 2438160 [5; 0,001%] интерполяция нормализованного значения функции обеспечивается полиномом наилучшего приближения на нормализованном интервале xнспособ и устройство вычисления квадратного корня, патент № 2438160 [2-R; 1].

Дополнительно при значении погрешности метода способ и устройство вычисления квадратного корня, патент № 2438160 мспособ и устройство вычисления квадратного корня, патент № 2438160 [1; 0,2%] интерполяция нормализованного значения функции обеспечивается полиномом наилучшего приближения на интервале xнспособ и устройство вычисления квадратного корня, патент № 2438160 [2-4; 1].

Дополнительно при значении погрешности метода способ и устройство вычисления квадратного корня, патент № 2438160 мспособ и устройство вычисления квадратного корня, патент № 2438160 [0,2; 0,01%] интерполяция нормализованного значения функции обеспечивается полиномом наилучшего приближения на интервале xнспособ и устройство вычисления квадратного корня, патент № 2438160 [2-2; 1].

Дополнительно при значении погрешности метода способ и устройство вычисления квадратного корня, патент № 2438160 мспособ и устройство вычисления квадратного корня, патент № 2438160 [0,01; 0,001%] интерполяция нормализованного значения функции обеспечивается полиномом наилучшего приближения на интервале xнспособ и устройство вычисления квадратного корня, патент № 2438160 [2-1; 1]. По шестому исполнению дополнительно к вариантам 1-5 с целью исключения неопределенного значения (большой погрешности) при x<xmin функции присваивается нулевое значение.

Ниже приводится более подробное теоретическое обоснование реализации предлагаемого способа и устройства путем улучшения быстродействующих полиномиальных алгоритмов вычисления квадратного корня с погрешностью 5способ и устройство вычисления квадратного корня, патент № 2438160 0,01%.

В различных технических устройствах при проведении в реальном масштабе времени измерений средних квадратических значений сигналов, действующих значений тока, характеристик случайных сигналов, линеаризации квадратичных характеристик датчиков, при анализе гармоник вибраций, преобразовании координат и т.д. возникает необходимость вычисления квадратного корня. В связи с ограниченным временем (порядка 0,5способ и устройство вычисления квадратного корня, патент № 2438160 10 мкс) вычисления необходимо осуществлять с помощью быстродействующих специализированных процессоров, в которых, как правило, отсутствует операция вычисления квадратного корня [3].

Трудоемкие вычисления квадратного корня рассмотрены, в частности, в [1, 2, 4, 6, 7]. В то же время в данных работах практически не исследовано влияние погрешностей дискретизации аргумента и квантования функции на погрешность результата, а предлагаемые вычислительные алгоритмы не оптимизированы при различных значениях погрешности. В связи с этим целесообразно выработать более завершенные рекомендации по применению полиномиальных алгоритмов реализации функций способ и устройство вычисления квадратного корня, патент № 2438160 в быстродействующих специализированных вычислителях.

Проведем сравнительный анализ и улучшение быстродействующих полиномиальных алгоритмов вычисления квадратного корня с точки зрения предельных соотношений по оптимизации времени преобразования, точностных характеристик и программно-аппаратных затрат при значениях приведенной погрешности для максимального значения способ и устройство вычисления квадратного корня, патент № 2438160 от 5% до 0,001%. Такой диапазон представления погрешностей обеспечивает требуемую точность в подавляющем большинстве технических приложений, от измерения амплитуд гармоник вибраций до определения модуля вектора в радиолокационных станциях, например, на дальности до 400 км с предельной ошибкой 50 м, что соответствует приведенной погрешности способ и устройство вычисления квадратного корня, патент № 2438160 =0,0125%.

1. Факторы оптимизации вычисления квадратного корня

Эффективным методом вычисления функций является их приближение с помощью полиномов Ln (x) Чебышева.

В общем случае оценка максимальной погрешности интерполяции для полинома Чебышева степени n на интервале хспособ и устройство вычисления квадратного корня, патент № 2438160 [а; b] имеет вид:

способ и устройство вычисления квадратного корня, патент № 2438160

Выбор узлов аппроксимации значений функции xk производится в соответствии с выражением:

способ и устройство вычисления квадратного корня, патент № 2438160

В соответствии с (2) по значениям x k, f(xk) составляется система уравнений и определяется аналитическое выражение для полинома.

При переходе от аппроксимирующего полинома первой степени к полиному второй степени и т.д. уменьшение значения погрешности будет составлять величину:

способ и устройство вычисления квадратного корня, патент № 2438160

Таким образом, в соответствии с (1способ и устройство вычисления квадратного корня, патент № 2438160 3) оптимизация полиномов Чебышева при заданных точностных характеристиках, быстродействии и программно-аппаратных затратах может проводиться путем изменения длины и положения интервала аппроксимации хспособ и устройство вычисления квадратного корня, патент № 2438160 [xmin=а; xmax=b], а также степени полинома n.

Удобно разбивать заданный интервал аппроксимации на интервалы, кратные четной или нечетной степени числа 2, и сокращать в соответствии с (1) заданный интервал. Каков бы ни был аргумент, последовательное умножение (деление) его k раз на 22 можно выполнять до тех пор, пока его попадание в указанный интервал не будет достигнуто. В этом случае производится предварительная нормализация аргумента х=22k ·х1. Затем вычисляется соответствующее х 1 значение f(x1), и окончательный результат получается путем обратной нормализации f(х)=f(x1)/2 k.

Таким образом, путем нормализации аргумента можно получить дополнительный фактор оптимизации трудоемкой операции извлечения квадратного корня.

Важно отметить, что теоретические положения (1способ и устройство вычисления квадратного корня, патент № 2438160 3) при использовании полинома Чебышева степени n справедливы, когда производная функции f[n+1](x)=const. Для функции способ и устройство вычисления квадратного корня, патент № 2438160 это условие не выполняется, а при хспособ и устройство вычисления квадратного корня, патент № 2438160 0 производная fспособ и устройство вычисления квадратного корня, патент № 2438160 (x) устремляется в бесконечность. В связи с этим использование полиномов в соответствии с (1способ и устройство вычисления квадратного корня, патент № 2438160 3) может быть рассмотрено и рекомендовано к практическому применению только в качестве средства получения предварительной оценки результатов.

2. Компьютерное моделирование наилучшего полиномиального приближения квадратного корня

Дальнейшее исследование проведено на основе компьютерного моделирования путем эмпирического подбора с последующей оптимизацией приближения функции способ и устройство вычисления квадратного корня, патент № 2438160 при учете (1способ и устройство вычисления квадратного корня, патент № 2438160 3) и всех вышерассмотренных факторов [3]. С этой целью в системе Mathcad разработана универсальная программа оптимизации обычных полиномов Чебышева в полиномы наилучшего приближения с документированием значений функции f(x), полинома Ln (x) и текущего значения погрешности способ и устройство вычисления квадратного корня, патент № 2438160 (х). На фиг.1 показан результат работы программы при аппроксимации функции способ и устройство вычисления квадратного корня, патент № 2438160 полиномом наилучшего приближения четвертой степени.

В таблице 1 приведены результаты моделирования на ЭВМ полиномов наилучшего приближения Ln(x) функции способ и устройство вычисления квадратного корня, патент № 2438160 на отрезке xспособ и устройство вычисления квадратного корня, патент № 2438160 [0; 1] для специализированных процессоров, работающих с форматами чисел с фиксированной запятой. Максимальное значение погрешности метода способ и устройство вычисления квадратного корня, патент № 2438160 и число арифметических операций вычисления функции определяется степенью n полинома Ln(x).

Практически, уже при переходе к полиномам третьей, четвертой степени не обеспечивается уменьшение максимального значения погрешности аппроксимации несмотря на усложнение вычислений (повышение степени полинома на 1 сопровождается увеличением числа арифметических операций на 2).

Таблица 1
Полиномы для интервала хспособ и устройство вычисления квадратного корня, патент № 2438160 [0; 1]
nПолином Максимальная погрешность способ и устройство вычисления квадратного корня, патент № 2438160 m Число арифметических операций
10,125+х 0,1252
2 0,07328224+х(1,94208432-1,088328635х) 0,073284
3 0,0500693+х(2,799725119-х(4,1291223-2,333423442х)) 0,054586
4 0,0339+х(3,88574-х(10,81061-х(14,48332-х6,63036))) - см. фиг.1 0,0383 8
5 0,028193272+х(4,947722896-х(22,425058338-х(52,978853892-х(55,667898127-х21,171122999)))) 0,03314 10

При переходе от полинома первой степени к полиному второй и более высоких степеней соотношение максимальных погрешностей результата равно соответственно 1,706; 1,343; 1,425; 1,156 и стремится к единице. Таким образом, увеличение степени полинома начиная с третьей в соответствии с таблицей 1 при значении погрешности способ и устройство вычисления квадратного корня, патент № 2438160 м<5% в технических приложениях является практически нецелесообразным, поскольку не обеспечивает уменьшение погрешности вычислений.

Следует отметить, что небольшого снижения погрешности для полинома первой степени можно добиться путем соразмерного рационального ограничения диапазона минимального значения аргумента, поскольку кроме погрешности метода способ и устройство вычисления квадратного корня, патент № 2438160 м при вычислениях имеют место погрешности дискретизации аргумента способ и устройство вычисления квадратного корня, патент № 2438160 д, квантования способ и устройство вычисления квадратного корня, патент № 2438160 к, а также другие виды погрешностей.

Обеспечить существенное увеличение точностных характеристик при значении способ и устройство вычисления квадратного корня, патент № 2438160 м<5% в соответствии с (3) можно как за счет рационального уменьшения интервала представления аргумента х, так и за счет оптимизации его выбора в диапазоне хспособ и устройство вычисления квадратного корня, патент № 2438160 [a; b]. В таблице 2а приведены результаты поиска полинома наилучшего приближения для отрезка хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-2; 1].

Таблица 2а
Полиномы для интервала хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-2; 1]
nПолином Максимальная погрешность способ и устройство вычисления квадратного корня, патент № 2438160 m
10,35453431+0,6658287х - см. фиг.20,0209910=1,34342×2 -6
20,2646218+х(1,03024561-0,2983608х) 0,0035350=1,80992×2 -9
30,2202625+х(1,302534-х(0,7895374-0,2674745х)) 0,0007420=1,51962×2 -11
40,1927997+х(1,5270898-х(1,4217556-х(1,0000625-0,2983639х))) 0,0001745=1,4295×2 -13
50,173524+х(1,72338-х(2,171966-х(2,349734-х(1,448107-0,373478х)))) 0,0000437=1,43196×2 -15

По сравнению с таблицей 1 даже для полинома четвертой степени имеем значительное снижение погрешности вычислений по отношению к полиному третьей степени. При переходе от полинома первой степени к полиному второй степени и т.д. отношение максимальных значений погрешностей равно 6; 4,72; 4,26; 4, и потенциально имеем запас по уменьшению значения погрешности при увеличении степени полинома.

Таким образом, при значениях погрешности способ и устройство вычисления квадратного корня, патент № 2438160 м<5% необходимо уменьшать интервал интерполяции функции способ и устройство вычисления квадратного корня, патент № 2438160 . Для более всесторонней и наглядной оценки эффективности применения различных интервалов интерполяции приведены таблицы полиномов и для отрезков: хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-12; 2-10], хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-10; 2-8], xспособ и устройство вычисления квадратного корня, патент № 2438160 [2-8; 2-6], xспособ и устройство вычисления квадратного корня, патент № 2438160 [2-6;2-4], хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-4;2-2].

Таблица 2б
Полиномы для интервала хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-4;2-2]
nПолином Максимальная погрешность способ и устройство вычисления квадратного корня, патент № 2438160 m
10,176946982+1,333656965х 0,0105064=1,34482×2 -7
20,13233481+х(2,059764389-2,384422263х) 0,0017607=1,803×2 -10
30,1101948+х(2,603657-х(6,30735-8,54185х)) 0,0003707=1,5184×2 -12
40,09637+х(3,05506-х(11,38395-х(32,04807-38,267х))) 0,0000871=1,42754×2 -14

Таблица 2в
Полиномы для интервала хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-6; 2-4]
nПолином Максимальная погрешность способ и устройство вычисления квадратного корня, патент № 2438160 m
10,08847+2,66731x 0,0052532=1,34482×2 -8
20,066167+x(4,11953-19,07538x) 0,0008804=1,803×2 -11
30,0551+x(5,20731-x(50,4588-273,3392x)) 0,0001854=1,51839×2 -13
40,04819+x(6,11012-x(91,07163-x(1025,53821-4898,17592x))) 0,0000436=1,42754×2 -15

Таблица 2г
Полиномы для интервала хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-8; 2-6]
nПолином Максимальная погрешность способ и устройство вычисления квадратного корня, патент № 2438160 m
10,04423+5,33463х 0,0026266=1,34482×2 -9
20,03308+х(8,23906-152,60302х) 0,0004402=1,80298×2 -12
30,02755+х(10,41463-х(403,67043-8746,85439х)) 0,0000927=1,5184×2 -14
40,02409+х(12,22025-х(728,57302-х(32817,22273-626966,5181x))) 0,0000218=1,42757×2 -16

Таблица 2д
Полиномы для интервала хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-10; 2-8]
nПолином Максимальная погрешность способ и устройство вычисления квадратного корня, патент № 2438160 m
10,02212+10,66926х 0,0013133=1,34482×2 -10
20,01654+х(16,47812-1220,8242х) 0,0002200=1,80298×2 -13
30,01377+х(20,82925-х(3229,36346-279899,3404х)) 0,0000463=1,5184×2 -15
40,01205+х(24,4405-х(5828,58414-х(1050151,127-80251714,32х))) 0,0000109=1,42754×2 -17

Таблица 2е
Полиномы для интервала хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-12; 2-10]
nПолином Максимальная погрешность способ и устройство вычисления квадратного корня, патент № 2438160 m
10,01106+21,33851x 0,0006567=1,34482×2 -11
20,00827+х(32,95623-9766,59359х) 0,0001100=1,80299×2 -14
30,00688+х(41,65851-х(25834,90765-8956778,894x)) 0,0000232=1,5184×2 -16

Чтобы представить завершенный алгоритм, оценить полные вычислительные затраты на реализацию вычислений квадратного корня с заданной погрешностью метода и суммарной погрешностью, необходимо определить весь интервал изменения аргумента хспособ и устройство вычисления квадратного корня, патент № 2438160 [xmin; 1], дискрет изменения способ и устройство вычисления квадратного корня, патент № 2438160 х и соответствующую ему погрешность дискретизации.

3. Определение границ интервала изменения аргумента и погрешности дискретизации

Погрешность дискретизации должна быть соизмерима с погрешностью метода. При вычислении квадратного корня задать интервал дискретизации аргумента способ и устройство вычисления квадратного корня, патент № 2438160 x, соответствующий заданному приращению функции способ и устройство вычисления квадратного корня, патент № 2438160 f(х) по выражению способ и устройство вычисления квадратного корня, патент № 2438160 сложно, поскольку при хспособ и устройство вычисления квадратного корня, патент № 2438160 0 fспособ и устройство вычисления квадратного корня, патент № 2438160 (x)способ и устройство вычисления квадратного корня, патент № 2438160 способ и устройство вычисления квадратного корня, патент № 2438160 . Более целесообразно, исходя из обычного здравого смысла, выбрать дискрет изменения аргумента способ и устройство вычисления квадратного корня, патент № 2438160 x равным значению xmin. В свою очередь значение xmin взять таким, чтобы приращение функции, определяемое этим значением, не превышало значения погрешности метода или ее доли q<1, которую дает полином аппроксимации функции. Например, при аппроксимации функции способ и устройство вычисления квадратного корня, патент № 2438160 на интервале хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-4; 1] полиномом первой степени имеем, в соответствии с таблицей 3, погрешность метода способ и устройство вычисления квадратного корня, патент № 2438160 м=0,057.

Таблица 3
Полиномы для интервала хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-4; 1]
nПолином Максимальная погрешность способ и устройство вычисления квадратного корня, патент № 2438160 m
10,255362+0,8007265x 0,0568537=1,81932×2 -5
20,1870829+x(1,318958-0,523308x) 0,0174736=1,11831×2 -6
30,1546705+x(1,7246295-x(1,560644-0,688075)) 0,0067538=1,72897×2 -8
40,135283+х(2,060546-х(3,04426-х(2,972837-1,272738х))) 0,0028985=1,48403×2 -9

Если взять xmin=2-10=0,00098, то этому значению будет соответствовать приращение функции способ и устройство вычисления квадратного корня, патент № 2438160 - на фиг.2 приведены графики полинома и погрешности аппроксимации для интервала хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-12; 2-8]. Таким образом, погрешность дискретизации также будет равна способ и устройство вычисления квадратного корня, патент № 2438160 д=0,031 и составит 0,031/0,057=0,544 от погрешности метода.

При xmin=2-16=0,0000152 значение погрешности дискретизации будет равно 2-8 =0,0039 и составит 0,1258·способ и устройство вычисления квадратного корня, патент № 2438160 м. Поэтому последнее значение xmin =2-16 для способ и устройство вычисления квадратного корня, патент № 2438160 м=0,031 можно увеличить.

По значениям погрешностей метода и дискретизации, а также по значению x min определяется полный интервал изменения аргумента.

4. Определение интервала присутствия аргумента

Для проведения вычислений, например, во всем интервале хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-16; 1] при интервале аппроксимации полиномом хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-4; 1] необходимо проверить присутствие аргумента в одном из интервалов хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-16;2-12], хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-12; 2-8], хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-8; 2-4]. Диапазон хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-4; 1] может не проверяться, поскольку он определяется путем исключения. Следует также проверить условие х<2-16 и в случае его выполнения принять значение способ и устройство вычисления квадратного корня, патент № 2438160 . При нахождении аргумента, например, в диапазоне хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-16; 2-12] производится нормализация аргумента до диапазона хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-4; 1] путем умножения аргумента на 2 12. После этого производится вычисление значения функции на интервале хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-4; 1] и последующее нормирование результата вычислений путем деления полученного результата на 26 .

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

5. Сравнительная оценка эффективности алгоритмов вычисления квадратного корня

В соответствии с таблицей 1 для полинома второй степени в интервале xспособ и устройство вычисления квадратного корня, патент № 2438160 [0; 1] при четырех операциях реализации вычислений квадратного корня получим значение погрешности способ и устройство вычисления квадратного корня, патент № 2438160 м=0,07328; при шести операциях для полинома третьей степени значение погрешности составит способ и устройство вычисления квадратного корня, патент № 2438160 м=0,0546. Дальнейшее повышение степени полинома на интервале интерполяции хспособ и устройство вычисления квадратного корня, патент № 2438160 [0; 1] с целью уменьшения погрешности неэффективно.

Если использовать полином первой степени с интервалом интерполяции хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-4; 1] (таблица 3), то при осуществлении двух операций вычисления полинома, двух операций нормализации и трех операций проверки условия для интервала хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-16; 1] при значении погрешности метода способ и устройство вычисления квадратного корня, патент № 2438160 м=0,057 и погрешности дискретизации аргумента способ и устройство вычисления квадратного корня, патент № 2438160 д=2-8=0,0039 получим суммарную погрешность вычислений способ и устройство вычисления квадратного корня, патент № 2438160 =0,0609. Для вычисления квадратного корня требуется реализация семи операций.

При использовании полинома второй степени на интервале хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-4; 1] при значении погрешности метода способ и устройство вычисления квадратного корня, патент № 2438160 м=0,01747 и распространении интервала на хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-16; 1] с погрешностью дискретизации аргумента способ и устройство вычисления квадратного корня, патент № 2438160 д=2-8=0,0039 получим суммарную погрешность вычислений способ и устройство вычисления квадратного корня, патент № 2438160 =0,0214. Для проведения вычислений необходимо осуществить четыре операции вычисления полинома, две нормализации и три проверки условия - всего 9 операций. Это явно лучше, чем при применении полинома пятой степени на интервале хспособ и устройство вычисления квадратного корня, патент № 2438160 [0; 1] с десятью операциями вычисления квадратного корня и погрешностью метода способ и устройство вычисления квадратного корня, патент № 2438160 м=0,03314.

При применении полинома первой степени на меньшем интервале хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-2; 1] с погрешностью метода способ и устройство вычисления квадратного корня, патент № 2438160 м=0,021 (таблица 2а) и распространением его на интервал хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-16; 1] получим суммарные значения погрешностей способ и устройство вычисления квадратного корня, патент № 2438160 =способ и устройство вычисления квадратного корня, патент № 2438160 м+способ и устройство вычисления квадратного корня, патент № 2438160 д=0,021+0,0039=0,0249. Для вычисления квадратного корня необходимо выполнить две операции вычисления полинома, две нормализации и четыре проверки условия. Общее число операций будет равно восьми.

При применении полинома второй степени на интервале хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-2; 1] с погрешностью метода способ и устройство вычисления квадратного корня, патент № 2438160 м=3,5·10-3 и распространением его на интервал хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-16; 1] необходимо осуществить четыре операции вычисления полинома, две нормализации и четыре проверки условия - всего 10 операций.

При применении полинома четвертой степени на интервале хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-4; 1] (таблица 3) с погрешностью метода способ и устройство вычисления квадратного корня, патент № 2438160 м=0,289·10-3 необходимо осуществить восемь операций вычисления полинома, две нормализации и три проверки условия - всего 13 операций.

При использовании полиномов пятой степени на интервале хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-4; 1] и третьей степени на интервале хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-2; 1] получим для полинома с интервалом хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-4; 1] 15 операций реализации вычисления квадратного корня с погрешностью способ и устройство вычисления квадратного корня, патент № 2438160 м=1,31·10-3 и 10 операций для полинома с интервалом хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-2; 1] и погрешностью способ и устройство вычисления квадратного корня, патент № 2438160 м=0,7·10-3.

Таким образом, при значении погрешности способ и устройство вычисления квадратного корня, патент № 2438160 мспособ и устройство вычисления квадратного корня, патент № 2438160 [0,05; 0,02] можно использовать полином с интервалом аппроксимации хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-4; 1]. При меньших значениях погрешности метода целесообразно использовать полином с интервалом хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-2; 1].

На интервалах хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-4; 2-2]способ и устройство вычисления квадратного корня, патент № 2438160 хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-12; 2-10] (таблица 2) имеем для полиномов одинаковой степени меньшие значения погрешностей и больший диапазон разброса значений коэффициентов полинома по сравнению с интервалом хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-2; 1]. В то же время использовать полином, например, с интерполяцией способ и устройство вычисления квадратного корня, патент № 2438160 на интервале хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-12; 2-10] для всего интервала нецелесообразно, поскольку при нормировании значения квадратного корня на интервал хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-2; 1] абсолютное значение погрешности возрастает в 25 раз. Кроме того, следует учитывать и возможность переполнения разрядных сеток операндов.

Гораздо меньшие значения приращения функции на интервалах хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-12; 2-10], хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-10; 2-8], xспособ и устройство вычисления квадратного корня, патент № 2438160 [2-8; 2-6], хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-6; 2-4], хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-4; 2-2] по сравнению с интервалом хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-2; 1] позволяют при значениях х<2 -4 объединить несколько интервалов в один.

В связи с этим была проведена оптимизация подборки полиномов для двух интервалов интерполяции. Для полинома третьей степени на интервале хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-4; 1] было получено значение погрешности способ и устройство вычисления квадратного корня, патент № 2438160 м=6,75·10-3 (таблица 3). Примерно такое же значение погрешности способ и устройство вычисления квадратного корня, патент № 2438160 м=9,17·10-3 получено для полинома третьей степени у=0,016+х(10,542-x(231,726-2003,336x)) на интервале хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-14; 2-4]. Таким образом, после проверки условия хспособ и устройство вычисления квадратного корня, патент № 2438160 2-4 можно сразу производить вычисления квадратного корня одним из двух полиномов третьей степени.

В этом случае для вычисления полинома потребуется 6 операций и еще 2 операции - на проверку условия. Значение погрешности дискретизации будет равно способ и устройство вычисления квадратного корня, патент № 2438160 При суммарной погрешности способ и устройство вычисления квадратного корня, патент № 2438160 c=9,17·10-3+7,8·10 -3=0,0169 для вычисления квадратного корня необходимо реализовать 8 операций. Этот результат дает при одинаковом числе операций меньшее значение погрешности, чем применение полинома первой степени с интервалом хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-2; 1].

При вычислении квадратного корня с погрешностью способ и устройство вычисления квадратного корня, патент № 2438160 м<0,01% в соответствии с таблицей 2а необходимо использовать полином пятой степени в интервале хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-2; 1] с погрешностью метода способ и устройство вычисления квадратного корня, патент № 2438160 м=0,0043%.

При задании аргумента с дискретом способ и устройство вычисления квадратного корня, патент № 2438160 х=xmin=2-32 получим значение погрешности дискретизации способ и устройство вычисления квадратного корня, патент № 2438160 д=2-16=0,0015%.

Для реализации алгоритма в интервале хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-32; 1] необходимо обеспечить проверку пяти условий, осуществить 10 арифметических операций при вычислении полинома пятой степени и выполнить две операции нормализации аргумента (фиг.3) - всего 17 операций.

При использовании полинома второй степени с интервалом интерполяции хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-1; 1] значение погрешности метода способ и устройство вычисления квадратного корня, патент № 2438160 м=0,0054% (таблица 4), и необходимо для вычисления в интервале хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-32; 1] выполнить 4 операции вычисления полинома, две нормализации и проверку 6 условий - всего 12 операций.

Таблица 4
Полиномы для интервала хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-1; 1]
nПолином Максимальная погрешность способ и устройство вычисления квадратного корня, патент № 2438160 m
10,4203833+0,585867х 0,0063338=1,62145×2 -8
20,3151265+х(0,8857735-0,2014445х) 0,0005453=U1677×2 -11
30,262553+х(1,110217-х(0,5112578-0,138546)) 0,0000584=1,91365×2 -15
40,229768+х(1,296689-х(0,9009874-x(0,49344-0,118917x))) 0,0000070=1,83501×2 -18

Сокращение интервала интерполяции позволяет повысить точность вычисления квадратного корня при заданном числе операций. Но в этом случае увеличивается число констант, которые необходимо выбирать из памяти ЭВМ. Блок-схема алгоритма вычисления значений функции способ и устройство вычисления квадратного корня, патент № 2438160 при хспособ и устройство вычисления квадратного корня, патент № 2438160 [0; 1] изображена на фиг.3. В то же время в общем случае при оценке эффективности алгоритма число операций реализации вычислений следует считать более критичным параметром.

Для сравнения с предлагаемыми алгоритмами в диапазоне хспособ и устройство вычисления квадратного корня, патент № 2438160 [2-2; 1] вместо итерационного алгоритма [5]

способ и устройство вычисления квадратного корня, патент № 2438160

был использован улучшенный гибридный алгоритм с начальным приближением у0 в виде полинома первой степени

способ и устройство вычисления квадратного корня, патент № 2438160

Этот алгоритм обеспечил значение погрешности метода 0,71·2-10 при двух итерациях [3]. Для реализации (1) требуется пять операций умножения и сложения, в то время как применение полинома четвертой степени обеспечивает меньшее значение погрешности при восьми операциях.

Заключение

В соответствии с проведенным исследованием для самых разнообразных технических применений на интервале значений погрешностей порядка способ и устройство вычисления квадратного корня, патент № 2438160 мспособ и устройство вычисления квадратного корня, патент № 2438160 [5; 0,001%] предлагается проводить вычисления нормализованных значений функции путем интерполяции их при требуемом уменьшении значений погрешностей на меньших величинах интервалов изменения аргумента и (или) полиномами более высокой степени.

На фиг.4 изображена структурная схема устройства вычисления квадратного корня (прототипа), состоящего из блока нормализации аргумента 1, блока итерационного вычисления 2, блока нормализации функции 3.

На фиг.5 - структурная схема заявляемого устройства (сущность изобретения), состоящего из блока нормализации аргумента 1, блока вычисления полинома 4, блока нормализации функции 3.

Принцип работы заявляемого устройства в соответствии с ранее проведенными теоретическими исследованиями и полученными аналитическими выражениями кратко может быть показан следующим образом. На вход устройства, которым является вход блока нормализации аргумента 1, подается параллельный код аргумента х. Блок нормализации аргумента 1 содержит схему исключения значений аргумента x<x min. Это необходимо для избежания большой погрешности вычислений и для уменьшения интервала поиска аргумента при x<xmin и т.д.; исключены значения аргумента, меньшие чем xmin . Блок нормализации аргумента 1 производит поиск одного из интервалов нахождения аргумента в соответствии с блок-схемой алгоритма вычисления значений функции (фиг.3).

Нормализованное значение xн передается в блок вычисления полинома 4. Для интервала xспособ и устройство вычисления квадратного корня, патент № 2438160 [2-4; 1] и т.д. в таблице 3 приведены полиномы наилучшего воспроизведения функции способ и устройство вычисления квадратного корня, патент № 2438160 , коэффициенты которого вводятся в блок вычисления полинома 4 и записываются в его память. В блоке нормализации функции 3 производится масштабирование нормализованного значения в действительное.

Все элементы устройства реализуются по известным принципам. Вычисление полинома осуществляется на цифровом сигнальном процессоре типа TMS 320. Реализация операции определения значения x<xmin производится путем сравнения значения x со значением xmin. Исключение значений аргумента x<x min необходимо осуществлять для устранения больших возможных значений погрешностей и для повышения быстродействия.

В заявляемом устройстве более эффективный способ и алгоритм вычисления квадратного корня по сравнению с прототипом получен путем комплексного анализа и компьютерного моделирования выражения для значения погрешности в (1, 2). Это выражение состоит из четырех частей: факториал и значения 22n+1 с увеличением n уменьшают погрешность; сокращение интервала (b-a) также уменьшает погрешность, но рост порядка производных и их отношений представляет более сложную зависимость, поэтому оптимизация проведена путем компьютерного моделирования. Для меньших значений погрешности с целью повышения быстродействия оказалось целесообразным последовательно уменьшить интервал нормализованного изменения аргумента.

Выводы

Полиномиальные методы вычисления значений квадратного корня обеспечивают хорошую сходимость и быстродействие при значениях погрешности способ и устройство вычисления квадратного корня, патент № 2438160 м=5способ и устройство вычисления квадратного корня, патент № 2438160 0,001% и менее. Время вычислений при выполнении операции умножения за 0,1 мкс в заданном диапазоне представления погрешностей не превышает 0,5способ и устройство вычисления квадратного корня, патент № 2438160 10 мкс.

При значении способ и устройство вычисления квадратного корня, патент № 2438160 м=1способ и устройство вычисления квадратного корня, патент № 2438160 0,2% целесообразно использовать полином на интервале интерполяции xспособ и устройство вычисления квадратного корня, патент № 2438160 [2-4; 1] с распространением этого интервала до значений xспособ и устройство вычисления квадратного корня, патент № 2438160 [2-16; 1], xспособ и устройство вычисления квадратного корня, патент № 2438160 [2-32; 1].

При значениях способ и устройство вычисления квадратного корня, патент № 2438160 м=0,2способ и устройство вычисления квадратного корня, патент № 2438160 0,001% целесообразно использовать полиномы с интервалом аппроксимации xспособ и устройство вычисления квадратного корня, патент № 2438160 [2-2; 1] и xспособ и устройство вычисления квадратного корня, патент № 2438160 [2-1; 1] с распространением этого интервала до значений xспособ и устройство вычисления квадратного корня, патент № 2438160 [2-32; 1].

Литература

1. А.с. СССР № 842806. Устройство для вычисления квадратного корня / В.В.Чекушкин. - Опубл. 1981. Бюл. № 24.

2. Акчурин Э.А. Программная реализация взаимных преобразований алгебраического и экспоненциального представления комплексного сигнала на цифровых сигнальных процессорах / Э.А.Акчурин // Радиотехника. - 1995 - № № 1-2. - С.21-23.

3. Зельдович Я.Б., Яглом Н.М. Высшая математика для начинающих физиков и техников. - М.: Наука, 1982. - 512 с.

4. Каханер Д., Моцлер К., Нэш С. Численные методы и программное обеспечение: пер. с англ. - М.: Мир, 2001. - 575 с.

5. Чекушкин В.В., Ромашов В.В., Тарануха В.М. Автоматизированные системы контроля и управления радиоэлектронными средствами. - Муром: МИВлГУ, 2000. - 120 с.

6. Ercegovas, Milos Dand. Others. Reciprocation square root, inverse square root, and some elementary functions using small multipliers / Milos Dand. Ercegovas // IEEE Trans Comput. 2000/ 49. - № 7 - С.628-637.

7. A. Schulte, Michall J. A family of variable - precision interval arithmetic processors / Michall J. A. Schulte, Earl E. Swarz Lander (Jr) // IEEE Trans Comput 2000/ 49. - № 5- С.387-397.

Класс G06F7/552 для возведения в степень или извлечения корня

устройство деления и извлечения квадратного корня -  патент 2510072 (20.03.2014)
устройство для вычисления функции -  патент 2028661 (09.02.1995)
устройство для вычисления модуля вектора -  патент 2022340 (30.10.1994)
Наверх