СПОСОБ И УСТРОЙСТВО ВЫЧИСЛЕНИЯ КВАДРАТНОГО КОРНЯ Российский патент 2011 года по МПК G06F7/552 

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

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

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

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

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

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

В то же время при использовании разработанного авторами более быстродействующего оптимизированного алгоритма с начальным приближением y₀=0,2936+0,8378·х на интервале х∈[2^-2; 1], что также соответствует отношению x_max/x_min=4, получено при двух итерациях (10 алгебраических операций) значение максимальной погрешности метода δ_м=1,42·2^-11.

Еще более убедительной является реализация приближения функции полиномом четвертой степени. На таком же интервале х∈[2^-2; 1] (8 алгебраических операций) получено значительно меньшее значение максимальной погрешности метода δ_м=1,43·2^-13. Более эффективные результаты повышения быстродействия (это показано ниже, в статье, принятой к публикации) получены и для всего диапазона погрешностей δ_м∈[5; 0,001%] путем компьютерного моделирования. В связи с этим проведем исследование улучшения полиномиальных методов и алгоритмов вычисления квадратного корня. Эти исследования не являются очевидными и не следуют из уровня техники. Например, предлагается «хорошая» формула для вычисления квадратного корня на основе биномиального ряда Ньютона [3]. Но погрешность вычисления по данной формуле в 2²ⁿ⁺¹ раз; выше, чем при использовании полинома Чебышева степени n. В то же время и применение обычных полиномов Чебышева также неэффективно, поскольку при х→0 производная f′(x)→∞. Поэтому при поиске полиномов наилучшего приближения путем моделирования необходимо учитывать и соразмерную погрешности метода δ_м погрешность дискретизации δ_д, соответствующую интервалу дискретизации Δх=x_min. За счет этого рациональным является уменьшение интервала изменения аргумента до х∈[x_min; 1]. Следует вместо минимального значения х=0 (как в прототипе) взять значение x_min и за счет сокращения интервала интерполяции на величину х∈[0; x_min], особенно при х→0, существенно уменьшить погрешность вычисления квадратного корня. При этом целесообразно брать На далеко не очевидные и не простые вопросы инженерного решения задач извлечения квадратного корня обращено внимание в основополагающей работе [4] (с.16-17, с.117-118 и т.д.). Исследованию методов оптимизации приближения функциональных зависимостей посвящен и ряд статей авторов, прошедших рецензирование и принятых в печать.

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

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

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

Дополнительно при значении погрешности метода δ_м∈[1; 0,2%] интерполяция нормализованного значения функции обеспечивается полиномом наилучшего приближения на интервале x_н∈[2^-4; 1].

Дополнительно при значении погрешности метода δ_м∈[0,2; 0,01%] интерполяция нормализованного значения функции обеспечивается полиномом наилучшего приближения на интервале x_н∈[2^-2; 1].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 1 Полиномы для интервала х∈[0; 1] n Полином Максимальная погрешность δ_m Число арифметических операций 1 0,125+х 0,125 2 2 0,07328224+х(1,94208432-1,088328635х) 0,07328 4 3 0,0500693+х(2,799725119-х(4,1291223-2,333423442х)) 0,05458 6 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 при значении погрешности δ_м<5% в технических приложениях является практически нецелесообразным, поскольку не обеспечивает уменьшение погрешности вычислений.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

При задании аргумента с дискретом Δх=x_min=2^-32 получим значение погрешности дискретизации δ_д=2^-16=0,0015%.

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

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

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

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

Для сравнения с предлагаемыми алгоритмами в диапазоне х∈[2^-2; 1] вместо итерационного алгоритма [5]

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

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

Заключение

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

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

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

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

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

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

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

Выводы

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

При значении δ_м=1…0,2% целесообразно использовать полином на интервале интерполяции x∈[2^-4; 1] с распространением этого интервала до значений x∈[2^-16; 1], x∈[2^-32; 1].

При значениях δ_м=0,2…0,001% целесообразно использовать полиномы с интервалом аппроксимации x∈[2^-2; 1] и x∈[2^-1; 1] с распространением этого интервала до значений x∈[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.

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

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