Разработка и исследование алгоритмов и процессоров вычисления значений элементарных функций тема диссертации и автореферата по ВАК РФ 05.13.05, кандидат технических наук Кошарновский, Александр Николаевич

• Кошарновский, Александр Николаевич
• кандидат технических наук
• 2000

Оглавление диссертации кандидат технических наук Кошарновский, Александр Николаевич

Введение

Глава 1. АНАЛИЗ МЕТОДОВ И СТРУКТУР ПРОЦЕССОРОВ 16 ВЫЧИСЛЕНИЯ ЭЛЕМЕНТАРНЫХ ФУНКЦИЙ В СЦВМ

1.1. Основные способы представления функций

1.1.1. Степенные ряды

1.1.2. Полиномы наилучшего приближения

1.1.3. Цепные дроби

1.1.4. Итерационные процессы

1.1.5. Аппроксимация Паде

1.1.6. Метод "цифра за цифрой"

1.1.7. Мультипликативный метод

1.2. Погрешности при вычислении элементарных функций

1.2.1. Методическая ошибка

1.2.2. Форма представления чисел и точность вычислений

1.2.3. Погрешности вычисления элементарных функций с помощью полино- 31 мов

1.2.4. Погрешности вычисления элементарных функций с использованием 33 сдвига и сложения

1.3. Таблично-алгоритмические процессоры элементарных функций

1.4. Процессоры элементарных функций на основе метода "цифра за цифрой"

1.5. Выводы

Глава 2. ИССЛЕДОВАНИЕ СТРУКТУР ПРОЦЕССОРОВ И 48 АЛГОРИТМОВ ВЫЧИСЛЕНИЯ ЭЛЕМЕНТАРНЫХ ФУНКЦИЙ НА ОСНОВЕ СТЕПЕННЫХ РЯДОВ (на основе полиномиального разложения)

2.1. Вычисление элементарных функций на основе разложения в ряд Тейлора

2.1.1. Исследование и выбор параметров аппроксимации и структуры процес- 51 сора для таблично-алгоритмического метода вычисления элементарных функций, представленных в виде ряда Тейлора

2.1.2. Сокращение аппаратных затрат

2.2. Разработка структуры процессора и алгоритма вычисления элементарных 56 функций с равномерной погрешностью на основе смешанной полиномиальной аппроксимации

2.3. Улучшение аппроксимации на основе разложения в степенной ряд

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

2.4.1. Вычисление полинома на одном процессоре

2.4.2. Процессор элементарных функций с распараллеливанием вычислений

2.4.3. Обоснование наилучшего варианта процессора элементарных функций

2.5. Выводы

Глава 3. ИССЛЕДОВАНИЕ И РАЗРАБОТКА АЛГОРИТМОВ 76 ВЫЧИСЛЕНИЯ ЭЛЕМЕНТАРНЫХ ФУНКЦИЙ НА ОСНОВЕ МУЛЬТИПЛИКАТИВНОГО МЕТОДА

3.1. Введение в мультипликативный метод

3.2. Алгоритмы перевода чисел в мультипликативный код

3.3. Мультипликативные алгоритмы деления

3.4. Мультипликативные алгоритмы вычисления логарифмов

3.5. Мультипликативные алгоритмы вычисления экспоненты

3.6. Мультипликативные алгоритмы извлечения квадратного корня и выполне- 87 ния операции нормирования в случае действительных аргументов

3.6.1. Погрешность вычисления квадратного корня

3.6.2. Быстродействие алгоритмов вычисления квадратного корня

3.7. Выводы

Глава 4. РАЗРАБОТКА СТРУКТУРЫ И АЛГОРИТМОВ ПРОЦЕССОРА 106 ВЫЧИСЛЕНИЯ ЭЛЕМЕНТАРНЫХ ФУНКЦИЙ

4.1. Анализ методов вычисления элементарных функций на спецпроцессорах

4.2. Разработка алгоритмов функционирования сопроцессора для вычисления 112 элементарных функций

4.2.1. Вычисление функции экспоненты у = ех

4.2.2. Вычисление функции натурального логарифма у = In х

4.2.3. Вычисление функции квадратного корня у = л/х ^

4.2.4. Вычисление функции синуса у = sinx

4.2.5. Вычисление функции косинуса у = cos х

4.2.6. Вычисление функции тангенса у - tgx

4.2.7. Вычисление функции y = arctgx

4.3. Мультипликативные алгоритмы вычисления элементарных функций

4.3.1. Вычисление экспоненты

4.3.2. Вычисление натурального логарифма

4.3.3. Вычисление квадратного корня

4.3.4. Вычисление частного

4.3.5. Вычисление арктангенса

4.3.6. Вычисление гиперболического арктангенса

4.3.7. Вычисление синуса, косинуса, тангенса и котангенса

4.3.8. Вычисление гиперболических синуса, косинуса, тангенса и котангенса

4.4. Разработка структуры процессора элементарных функций, реализующего 131 мультипликативные алгоритмы

4.4.1. Выбор прототипа процессора элементарных функций

4.4.2. Структура универсального процессора элементарных функций, реали- 134 зующих мультипликативные алгоритмы

4.5. Синтез сопроцессора элементарных функций, реализующего мультиплика- 137 тивные алгоритмы, на основе базовых матричных кристаллов

4.6. Выводы

Введение диссертации (часть автореферата) на тему «Разработка и исследование алгоритмов и процессоров вычисления значений элементарных функций»

Вычисление значений элементарных функций является одной из самых распространенных математических операций в современных СЦВМ и БЦВМ, т.к. составляют основу алгоритмов, реализуемых в этих ЦВМ.

Так, современные БЦВМ, устанавливаемые на борту различного рода летательных аппаратов, в большинстве своем в качестве одной из основных решают задачу о встрече с другими летательными аппаратами, т.е. траекторную задачу, и определения местоположения летательного аппарата в земной или иной системе координат.

Например, известная задача преобразования координат (нахождение новых координат при повороте системы координат на угол ср) обычно выполняется по формулам [1] : fx' = X-COS(p-y-ÚVL<p у = у • cos(р + х • sin^, требующих вычисления двух функций (sin и cos), четырех операций умножения и двух сложений/вычитаний.

Метод Голуба [2] использует соотношения х'= (х + у) • (cos^ - sin<p) + х • sin<p - у • cos(р = у • COS^ + X • sin (р, вычисление которых требует трех умножений и пяти сложений/вычитаний.

Метод Бьюмена [2] позволяет выполнить данное преобразование за три умножения и четыре сложения/вычитания:

Преобразование же координат из декартовой системы в полярную выполняется по формулам [1]:

R = Jx2 +y2 <p = arctg^/.

Другим примером может служить задача определения дальности 8 и пеленга П на объект при известных географических координатах своего места (фс, Хс) и места объекта (ср0, А,0).

Для небольших расстояний задача решается по формулам [2]:

Ас-А0)-соз((<рс+<р0)/2)

П — arctg

Рс-Ро)

Б = <Рс-<Ро)2 +(ЛС-Л0)2 ■С082 (<рс+<ро)/2) .

В более общем случае курсовой угол и и дистанция Э до объекта вычисляются с учетом радиуса Земли Яз (обратная геодезическая задача на сфере) [2]:

D = R3 ■ arctg —

Рс~<Ро) cos(p0-sm(Ác-Á0) sin{7-(sin^0 -sin^ + cos<p„ -cos(pc -cos(Ac - A0))

Как видно, для решения этих задач помимо операций сложения и вычитания требуется выполнить вычисления функций sin х, cos х, х2, х/у, Vx и arctg х.

В задачах моделирования переходных процессов (электроники, теплотехники) широко используются функции экспоненты ех и натурального логарифма In х.

Алгоритмы решения перечисленных задач в качестве основных включают операции по вычислению значений элементарных функций, количество которых с учетом их взаимных преобразований может быть сведено к шести: sin х, cos х, ехр х, In х, arctg х, Vx .

В задачах расчета напряжений и деформаций в стержнях и оболочках ис-пользуюся так называемые функции Крылова К0 . К3 [2]:

Ко(х) = ch х ■ cos х ,

К\{х) = ^--(chx-sinx + shx-cosx),

Кг(х) = sh х • sin х ,

Кз(х) = ^ ■ (ch х • sin х - sh х • cos х), которые в свою очередь требуют вычисления гиперболических функций синуса и косинуса (sh х и ch х).

Поэтому в некоторых случаях количество вычисляемых спецпроцессором функций увеличивают до 10-13, включая в упомянутый перечень гиперболические функции и расширяя его за счет других тригонометрических функций.

Таким образом, наиболее полный перечень элементарных функций, потребность вычисления которых возникает при решении задач на СЦВМ, может быть следующим: sin х, cos х, tg х, ctg х, arctg х, sh х, ch х, th х, cth х, exp х, In х, Vx, х/у.

Поскольку основными требованиями к СЦВМ, помимо массы, габаритов и потребляемой мощности, являются требование точности и обработка данных в реальном масштабе времени, то возникает проблема выбора и разработки таких методов вычисления элементарных функций, которые обеспечивают получение результатов с требуемой точностью за приемлемое время.

Предметом исследования в диссертационной работе являются процессоры специализированных ЦВМ для вычисления значений элементарных функций, методы и алгоритмы их вычисления.

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

Большой вклад в разработку методов вычисления элементарных функций на ЦВМ внесли И.Я.Акушский [3], В.С.Линский [4], Л.А.Люстерник [5], Ю.В.Антропов[6], В.Д. Байков, В.Б.Смолов, С.А.Селютин, С.Н.Вашкевич [2,7. 12], А.Д.Благовещенский, Г.С.Теслер [13], Д.Волдер [14], Д.Меджит[15], А.Д.Марковский [16] и многие другие авторы. Вопросы вычисления значений функций на ЦВМ рассматриваются также в [17 . 27].

Существует большое количество алгоритмов приближенного вычисления элементарных функций, выбор которых определяется как параметрами СЦВМ (разрядная сетка, система команд, быстродействие), так и требованиями решаемой задачи (максимально допустимая погрешность, время вычисления, состав операций).

Как известно [23], погрешность численного решения задачи обуславливается следующими причинами:

- математическое описание задачи является неточным, в частности, неточно заданы исходные данные описания;

- применяемый для решения метод часто не является точным: получение точного решения возникающей математической задачи требует неограниченного или неприемлемо большого числа арифметических операций, и поэтому вместо получения точного решения задачи приходится прибегать к приближенному;

- при вводе данных в ЦВМ, при выполнении математических операций и при выводе данных производятся округления.

Погрешности, соответствующие этим причинам, называют:

- неустранимая погрешность гн (погрешность исходных данных, неточные зависимости между параметрами);

- погрешность метода гм\

- вычислительная погрешность гв.

Очевидно, оптимальным решением будет разработка такой структуры СЦВМ и алгоритма вычисления, чтобы суммарная погрешность г0 = гн + гм + гв не превышала допустимую.

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

Методы вычисления элементарных функций, пригодные для вычисления на СЦВМ, подразделяются на следующие:

- разложение функции в степенной ряд Тейлора:

- представление функции в виде цепной дроби;

- аппроксимация функции полиномами наилучшего приближения (полиномами Чебышева);

- аппроксимация дробно-рациональной функцией (аппроксимация Паде);

- итерационные методы (метод Ньютона, метод хорд);

- метод "цифра за цифрой";

- мультипликативный метод.

Все эти методы сводятся к такому представлению функции, чтобы вычислить её значение для заданного значения аргумента с приемлемой точностью за допустимое время. Минимизация времени вычисления осуществляется за счёт использования наиболее быстрых операций ЦВМ: сложение и сдвиг(умножение или деление на 2). А выполнение «медленных» операций умножения и деления на произвольное число используется лишь на подготовительном (приведение аргумента к интервалу улучшенной сходимости функции) и заключительном этапах вычисления (восстановление функции для исходного значения аргумента).

Наличие быстрых и медленных операций, выполняемых процессорами, имеет место для большинства существующих ЭВМ, в том числе и для современных микропроцессоров. Однако, с появлением микропроцессоров, в которых все основные операции (в том числе умножение на произвольное число) выполняются за одинаковое время (за один машинный такт) и к тому же возможно одновременное выполнение нескольких операций упрощает решбние поставленной задачи. В табл. В.1. приведено время выполнения основных операций универсальным микропроцессором Intel 486 и цифровым сигнальным процессором ADSP2100.

Для ускорения обработки данных в современные процессоры встраивают команды вычисления некоторых элементарных функций. Например, в табл. В.2 приведен список встроенных функций для процессора Intel 486 и время их вычисления (количество машинных тактов) [28].

Таблица В.1. Время выполнения основных операций современными микропроцессорами (количество машинных тактов)

Операция Intel 486 ADSP2100

Сложение, вычитание : целочисленное 1 . 3 1 с плавающей запятой 8 .20 11

Сдвиг 2. 4 1 .4

Умножение целочисленное:

16 бит 13 .26 1

32 бит 13 .42 14

Умножение с ПЗ 11 . 16 9 . 13

Деление целочисленное:

16 бит 27 17

32 бит 43 485

Деление с ПЗ 73 . 89 33 .

Таблица В.2. Время вычисления элементарных функций на разных процессорах

Функция Intel 486 ADSP2100 л/х 83 . . 87 75 ху 30 . .32 sin X, COS X 193 . .279 25 tgx 200 . .273 arctg x 218 . . 303 58

Для процессора АББР известны рекомендованные фирмой-изготовителем алгоритмы вычисления ряда элементарных функций [29], время вычисления которых (количество системных тактов) также приведено в табл.В.2. Программная реализация некоторых из этих алгоритмов приведена в приложении 1.

Однако, в силу ряда причин в специализированных ЦВМ продолжают применяться процессоры, построенные на заказных или полузаказных (матричных) БИС.

В настоящее время существует множество различных методов реализации алгоритмов вычисления элементарных функций в ЭВМ [2,3,7,8,30 . 35].

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

Микропрограммный метод характерен для современных микропроцессорных систем и обеспечивает более высокое быстродействие по сравнению с программным методом.

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

Аппаратный метод заключается в табличной организации процессора вычисления элементарных функций на основе ПЗУ, адресная часть которого является аргументом функции, а числовая - значением самой функции. Очевидно этот метод пригоден для вычисления значений функции с невысокой точностью. Достижения современной микроэлектроники позволяют построить табличные процессоры элементарных функций на основе ПЗУ с разрядностью аргумента не превышающей 12-16 двоичных разрядов.

Поэтому актуальной является задача выбора и разработки таких алгоритмов вычисления элементарных функций и такой структуры процессора, которые учитывают структуру и особенности современных МаБИС.

Разработка специализированного процессора на основе МаБИС является достаточно трудоемким и продолжительным процессом, а начало макетных испытаний связано с достаточно длительным процессом изготовления полузаказных БИС. В случае же ошибки в структуре процессора изготовление БИС приходится повторять заново.

Значительное ускорение в процессе создания СЦВМ дает использование программируемых логических интегральных схем (ПЛИС) [36], которые позволяют быстро отладить структуру разрабатываемого процессора и, затем, приступить к созданию безошибочного процессора на МаБИС.

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

Для достижения указанной цели решаются следующие задачи:

- создание новых и модификация существующих методов вычисления элементарных функций на специализированных процессорах;

- разработка новых и модификация существующих структур специализированных процессоров с использованием современных БИС и ПЛИС;

- реализация полученных алгоритмов и структур в конкретных разработках специализированных процессоров.

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

- численные методы;

- машинная арифметика.

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

В практической части работы использовались методы автоматизации проектирования цифровых устройств, в том числе на базе МаБИС и ПЛИС.

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

Основные положения диссертации, выносимые на защиту:

1. Метод смешанной полиномиальной аппроксимации для вычисления восьми элементарных функций (sinx, cos х, tgx, arcsin х, arctg х, In х, ex,Vx). Метод основан на разбиении диапазона изменения аргумента на сегменты и аппроксимации на них полиномами разных степеней; причем для получения высокого быстродействия степень полинома выбирается минимальной, но обеспечивающей требуемую точность вычисления.

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

3. Алгоритмы вычисления квадратного корня на основе мультипликативного метода вычисления элементарных функций. Алгоритмы используют лишь самые быстрые операции (сложение/вычитание и сдвиг) и требуют наименьшего количества итераций из всех известных алгоритмов.

4. Структура процессора элементарных функций, обеспечивающего вычисление 14 элементарных функций на основе мультипликативных алгоритмов. Данная структура обеспечивает наилучшие характеристики при ее реализации на современной элементной базе.

Работа состоит из введения, четырех глав, заключения, пяти приложений и списка литературы из 66 наименований.

Объем работы составляет 187 страниц, включая 16 таблиц, 14 рисунков и 39 страниц приложений.

В первой главе даётся анализ методов и структур процессоров для вычисления элементарных функций в СЦВМ. Рассматриваются основные способы представления функций ( степенные ряды, цепные дроби, полиномы наилучшего приближения, итерационные процессы, аппроксимация Паде, метод "цифра за цифрой", мультипликативный метод), погрешности при вычислении элементарных функций и структуры процессоров, используемых для вычисления элементарных функций. Обосновывается необходимость Обосновывается необходимость исследования и разработки новых алгоритмов и структур процессоров для вычисления элементарных функций на основе степенных рядов и мультипликативного метода.

Вторая глава посвящена способам и структурам процессоров для вычисления элементарных функций на основе разложения в ряд Тейлора: проводится анализ способов вычисления элементарных функций, исследование и выбор параметров аппроксимации и структуры процессора для таблично-алгоритмического метода вычисления элементарных функций, , анализ способов сокращения аппаратурных затрат, разработка структуры процессора и алгоритма вычисления элементарных функций с равномерной погрешностью на основе смешанной полиномиальной аппроксимации, предлагается улучшение аппроксимации на основе разложения в степенной ряд, проводится исследование и разработка специализированных процессоров для вычисления элементарных функций на основе разложения в степенной ряд (вычисление полинома на одном процессоре, процессор элементарных функций с распараллеливанием вычислений, обоснование наилучшего варианта процессора элементарных функций).

В третьей главе подробно рассматривается мультипликативный метод вычисления элементарных функций (введение в мультипликативный метод, алгоритмы перевода чисел в мультипликативный код, мультипликативные алгоритмы деления, мультипликативные алгоритмы вычисления логарифмов, мультипликативные алгоритмы вычисления экспонент). Разрабатываются мультипликативные алгоритмы извлечения квадратного корня и выполнения операции нормирования в случае действительных аргументов.

В четвёртой главе разрабатывается сопроцессор элементарных функций. Проводится разработка алгоритмов функционирования сопроцессора для вычисления 14-ти элементарных функций (разрабатываются алгоритмы приведения аргумента к интервалу аппроксимации и мультипликативные алгоритмы вычисления на интервалах аппроксимации). Разрабатывается структура универсального процессора элементарных функций, реализующих мультипликативные алгоритмы. Проводится синтез сопроцессора элементарных функций, реализующего мультипликативные алгоритмы, на основе базовых матричных кристаллов.

В заключении сформулированы основные результаты диссертационной работы.

В приложениях приведены программы вычисления некоторых элементарных функций на цифровых сигнальных процессорах серии АОБР 2100, пример работы алгоритмов перевода двоичного кода в мультипликативный, пример вычисления функции экспоненты на основе мультипликативного метода, примеры работы мультипликативного алгоритма извлечения квадратного корня.

Заключение диссертации по теме «Элементы и устройства вычислительной техники и систем управления», Кошарновский, Александр Николаевич

4.6. Выводы

1. Разработаны алгоритмы приведения аргумента к интервалам аппроксимации для 14 элементарных функций и проведена оценка их временной сложности, которая показала, что наибольшую сложность имеет алгоритм приведения для функции тангенса, наименьшую - квадратного корня.

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

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

4. Реализация сопроцессора на БМК Такт-6000 показала эффективность принятых решений и обеспечила обработку данных в реальном масштабе времени.

ЗАКЛЮЧЕНИЕ

1. Анализ методов и структур процессоров для вычисления элементарных функций в СЦВМ показал, что с целью обеспечения высокой точности и высокого быстродействия необходимо провести исследование и разработку алгоритмов работы и структур процессоров элементарных функций на основе полиномиального разложения и на основе мультипликативного метода.

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

3. Проведенное исследование сегментного метода вычисления элементарных функций показало возможность аппроксимации отдельных сегментов рядами Тейлора с различным количеством членов, то есть сводящихся к полиномам разных степеней, что позволяет уменьшить на 15-25 % объем памяти для хранения коэффициентов.

4. Проведенное исследование возможности вычисления элементарных функций на основе сегментно-полиномиальной аппроксимации показало, что с точки зрения объёма аппаратных затрат, быстродействия и погрешности при заданной разрядности аргумента и функции оптимальными для вычисления элементарных функций являются полиномы третьей и четвёртой степени.

5. Разработан ряд структур процессоров элементарных функций на современной элементной базе, проведена их сравнительная оценка и показано, что наилучшими параметрами обладают:

- структура конвейерного типа с использованием ускорителей умножения;

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

Данные технические решения защищены авторским свидетельством.

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

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

7. На основе мультипликативного метода разработаны пять алгоритмов вычисления квадратного корня и выполнения операции нормирования в случае действительного аргумента, обладающие друг перед другом разными достоинствами. Один из них позволяет достичь минимума объема оборудования за счет применения только операций суммирования и упрощения анализа на каждом шаге итерации, другой - максимального быстродействия за счет более сложного анализа и применением не только операций суммирования, но и вычитания.

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

8. Разработаны алгоритмы приведения аргумента к интервалам аппроксимации для 14 элементарных функций и проведена оценка их временной сложности, которая показала, что наибольшую сложность имеет алгоритм приведения для функции тангенса, наименьшую - квадратного корня.

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

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

148

11. Реализация сопроцессора на БМК Такт-6000 показала эффективность принятых решений и обеспечила обработку данных в реальном масштабе вре мени.

Список литературы диссертационного исследования кандидат технических наук Кошарновский, Александр Николаевич, 2000 год

1. Выгодский М.Я. Справочник по высшей математике. -М: Наука, 1965-872 с.

2. Байков В.Д., Смолов В.Б. Специализированные процессоры: итерационные алгоритмы и структуры. -М.:Радио и связь, 1985-288 с.

3. Акушский И.Я. Многорегистровые схемы выполнения арифметических операций. // Вопросы теории математических машин 1958- Вып.1- с. 192-218.

4. Линский B.C. Вычисление элементарных функций в автоматических цифровыхмашинах. // Вычислительная математика. 1957- №2- с.90-119.

5. Люстерник Л.А., Червоненко О.А., Янпольский А.Р. Вычисление элементарных функций -М.: Физматгиз-1963-247 с.

6. Антропов Ю.В. Метод "приведения" как метод вычисления функций в ЭЦВМ.// Изв. ЛЭТИ-1962- Вып.52- с. 159 170.

7. Специализированные ЦВМ. Учебник для вузов./ Под ред. Смолова В.Б. М.:1. Высш.школа-1981-279 с.

8. Байков В.Д., Смолов В.Б. Аппаратурная реализация элементарных функций.

9. Л.: Изд-во Ленинградского университета-1975-96 с.

10. Байков В.Д., Вашкевич С.Н. Решение траекторных задач в микропроцессорныхсистемах ЧПУ. -Л.: Машиностроение-1986-106 с.

11. Байков В.Д., Селютин С.А. Анализ методов вычисления элементарных функций в микропроцессорах и микро-ЭВМ // Известия вузов. Приборостроение-1981-Вып.1-с. 54-56.

12. Байков В.Д., Селютин С.А. Вычисление элементарных функций в ЭКВМ-М.:Радио и связь-1982-с.28-33.

13. Смолов В.Б., Байков В.Д. Принципы и перспективы применения метода вы-численияй "цифра за цифрой". // Электроника и методы гибридных вычислений. Киев: АН УССР-1978-c.l 19-130.

14. Благовещенский А.Д.,Теслер Г.С. Вычисление элементарных функций на ЭВМ.-М.:Техника-1977-208 с.

15. Voider J.E. The CORDIC Trtigometric computing techique. // Computer design development.-N.-Y- 1976-p. 301-307.

16. Meggitt J.E. Pseudo division and pseudo multiplication process. //- IBM of Res. and Dev.- 1962-vol. 6-№2-p. 210-226.

17. Марковский А.Д. Мультипликативные алгоритмы и специализированные устройства для деления и вычисления некоторых классов функций//Научн.тр. Моск. лесотехн. ин-та.-1989-Вып.217-с. 57-69.

18. Демидович Б.П., Марон И.А. Основы вычислительной математики.-М.: Нау-ка-1966-664 с.

19. Копченова Н.В., Марон И.А. Вычислительная математика в примерах и зада-чах.-М.: Наука-1972-368 с.

20. Попов Б.А., Теслер Г.С. Вычисление функций на ЭВМ. Справочник-Киев: Наукова думка-1984-600 с.

21. Ахо А., Хопкрофр Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.-М.:Мир-1979-353 с.

22. Кнут Д. Искусство программирования для ЭВМ. В 3 т.—Т. 1: Основные алгоритмы. -М.:Мир,1976-73 5с.

23. Кнут Д. Искусство программирования для ЭВМ. В 3 т-Т.2: Получисленные алгоритмы.-М. :Мир, 1977-720с.

24. Бахвалов Н.С. Численные методы.-М.: Наука-1973-632 с.

25. Ремез Е.Я. Общие вычислительные методы Чебышевских приближений-Киев: АН УССР, Институт математики- 454 с.

26. Информационные системы. Табличная обработка информации. /Под ред. Балашова Е.П. и СмоловаВ.Б- JL: Энергоатомиздат-1985-180 с.

27. Скоробогатько В.Я. Теория ветвящихся цепных дробей и ее применение в вычислительной математике.-М.: Наука-1983-311 с.

28. Бейкер Дж., Грейвс-Моррис П. Аппроксимации Паде.-М.: Мир-1986-502 с.

29. Microprocessors. Handbook, vol.2.-Intel Corp.-l991-720 p.

30. Digital Signal Processing Applications Using The ADSP-2100 Family-Vol.1.-Englewood Cliffs, NJ: Prentice Hall-1992-320 p.

31. Карцев M.A., Брик B.A. Вычислительные системы и синхронная арифметика.-М.:Радио и связь-1981-360 с.

32. Функционально ориентированные процессоры. / Водяхо А.И., СмоловВ.Б., Плюснин В.У., Пузанков Д.В. -JL: Машиностроение-1988-224 с.

33. Мячев A.A., Степанков В.Н. Персональные ЭВМ и микроЭВМ. Основы организации. Справочник.-М.: Радио и связь-1991-320 с.

34. Лиждвой Г.Л., Шилейко A.B. Принципы построения вычислительного модуля, реализующего укрупненные операции.// Вычислительные системы и сре-ды.-Таганрог-1972-c. 170-172.

35. A.c. 1314337 СССР, МКИ3 G06F7/38. Устройство для вычисления функций. /Байков В.Д., Баканов А.Е., Рахматулин O.A. (СССР).-4с.:ил.

36. Gene L. Heviland and Al A. Tuszinski. A CORDIC Arithmetic Proceccor Chip.// IEEE Trans, on Comp.-Vol. C-29- No2, February 1980- p. 68-78.

37. Программируемые логические микросхемы на КМОП-структурах и их применение / Мальцев П.П., Гарбузов Н.И., Шарапов А.П., Кнышев Д.А. М.: Энергоатомиздат-1998. - 160 с.

38. Пашковский С. Вычислительные применения многочленов и рядов Чебыше-ва.-М.:Наука-1983-384 с.

39. Виноградов И.М. Основы теории чисел.-М.: Наука-1965-172 с.

40. Плотников A.B., Степашкин Г.И. Оценка инструментальной точности специализированного вычислителя. //Вычислительная техника, вып.1. / Под ред. Смолова В.Б. Л., Изд-во ЛГУ-1970-c. 187 - 194.

41. Поспелов Д.А. Арифметические основы вычислительных машин дискретного действия М.: Высшая школа-1970-380 с.

42. Карцев М.А. Арифметика цифровых машин.-М.: Наука-1969-575 с.

43. Марковский А.Д. Структура вычислительных систем с точки зрения точности и алгебраических критериев качества вычислений.//Дис. канд. физ.-мат. на-ук.-М.-1980-205 с.

44. A.c. 1383337 СССР, МКИ3 G06F7/38. Устройство для вычисления элементарных функций табличным методом. / Кошарновский А.Н. и др. (СССР).

45. Марковский А.Д., Меликов Г.Г. Мультипликативные алгоритмы типовых вычислений и организация устройств на их основе.//Научн. тр. /Моск. лесотехн. ин-т-1989-Вып.217-с.9-21.

46. Марковский А.Д., Полянский В.В. Временная сложность и сравнительная характеристика мультипликативных алгоритмов параллельного делениям/Вопросы авиационной науки и техники. Сер. Пилотажно-навигационные системы и приборы.-1988-Вып. 1.-е. 14-29.

47. Марковский А.Д., Пустовойтов О.И. Об одном мультипликативном алгоритме параллельного деления чисел.//Научн. тр. /Моск. лесотехн. ин-т.-1986-Вып. 183-е.37-42.

48. Марковский А.Д., Полянский В.В., Пустовойтов О.И. Мультипликативные алгоритмы параллельного деления чисел.//Вопросы авиационной науки и техники. Сер. Пилотажно-навигационные системы и приборы.-1988-Вып. 1-с.3-13.

49. A.c. 1417644 СССР. Устройство для параллельного деления чисел. / А.Д. Марковский (СССР).- 10 с.:ил.

50. A.c. 1618165 СССР. Устройство для параллельного деления чисел/ Марковский А.Д., Кошарновский А.Н. (СССР)-5 с.:ил.

51. A.c. 1505262 СССР. Цифровое логарифмическое устройство/А.Д. Марковский (СССР).-8 с.:ил.

52. Марковский А.Д., Пустовойтов О.И. Быстрый машинный алгоритм вычисления натурального логарифма//Научн. тр. /Моск. лесотехн. ин-т.-1987-Вып. 195-е.69-74.

53. Марковский А.Д., Евстигнеева О.В. Мультипликативные алгоритмы вычисления экспоненты в системе с фиксированной запятой.// Научн. тр. /Моск. лесотехн. ин-т.-1988-Вып.205-е.78-89.

54. A.c. 1381497 СССР. Устройство для извлечения квадратного корня/ Кошарновский А.Н., Марковский А.Д., Пустовойтов О.И. и др. (СССР). 10 е.: ил.

55. Марковский А.Д., Меликов Г.Г. Мультипликативный метод вычисления тригонометрических функций.//Сб. научн. тр. / МЛТИ -1987-Вып.№ 195- с.57-65.

56. Гаврилов Ю.В., Пучко А.Н. Арифметические устройства быстродействующих ЭВМ.-М.: Сов. Радио-1970-280 с.

57. Евстигнеев В.Г. Недвоичная машинная арифметика и специализированные процессоры /Под. ред. И.Я. Акушского.-М.: МИФИ СЕРВИС-1992-266 с.

58. Кошарновский А.Н., Маркин A.B., Евстигнеев В.Г. и др. Методы ускорения выполнения арифметических операций на современных ЭВМ//Научно-технический сборник Сер.8, вып.2(38), 1983.152

59. Кошарновский А.Н., Толстых М.М. Анализ исследований методом машинной обработки оптической информации в реальном масштабе времени: Аналитический обзор./М., 1984., № 3964. 2 с.

60. ПРОГРАММЫ ВЫЧИСЛЕНИЯ НЕКОТОРЫХ ЭЛЕМЕНТАРНЫХ

61. ФУНКЦИЙ на цифровых сигнальных процессорах серии ADSP2100 фирмы Analog Device

62. П1.1. Вычисление квадратного корня1. MODULE Squareroot; {1. Square Root Y = sqrt(x)

63. Calling Parameters MR1 = MSW of x MRO = LSW of x M3 = 1 L3 = 01. Return Values

64. SR1 = y in 8.8 UNSIGNED format1. Altered Registers

65. AXO,AYO,AY1,AR,MYO,MY1,MXO,MF,MR,SE,SR,I31. Computation Time75 cycles (maximum)

66. CONST base=H#0D49, sqrt2=H#5A82; .VAR/DM sqrtcoeff5.;

67. IT sqrtcoeff : H#5D1D, H#A9ED, H#46D6, H#DDAA, H#072D; .ENTRY sqrt;sqrt: l3=Asqrtcoeff; {Pointer to coeff. buffer}

68. SE=EXP MR1 (HI); {Check for redundant bits}1. SE=EXP MRO (LO);

69. AX0=SE, SR=NORM MR1 (HI); {Remove redundant bits}1. SR=SR OR NORM MRO (LO);1. MY0=SR1, AR=PASS SR1;1. EQ RTS;1. MR=0;

70. MR1=base; {Load constant value}

71. MF=AR*MY0 (RND), MX0=DM(I3,M3); {MF = x**2} MR=MR+MX0*MY0 (SS), MX0=DM(I3,M3); {MR = base + C1*x} CNTR=4;1. DO approx UNTIL CE;

72. MR=MR+MX0*MF (SS), MX0=DM(I3,M3); approx:MF=AR*MF (RND); AY0=15;

73. MY0=MR1, AR=AX0+AY0; {SE + 15 = 0?}

74. NE JUMP scale; {No, compute sqrt(s)}

75. SR=ASHIFT MR1 BY-6 (HI); RTS; scale: MR=0;

76. AR=AR AND AYO; {Remove sign bit}1. MY1=AR;

77. MF=AR*MY1 (RND), MX1=DM((3,M3); {MF = x**2} MR=MX1*MY1 (SS), MX1=DM(I3,M3); {MR = C1*x} CNTR=3;1. DO approx UNTIL CE;

78. MR=MR+MX1*MF (SS); approx: MF=AR*MF (RND), MX1=DM(I3,M3); MR=MR+MX1*MF (SS); SR=ASHIFT MR1 BY 3 (HI);

79. SR=SR OR LSHIFT MRO BY 3 (LO); {Convert to 1.15 format} AR=PASS SR1;

80. LT AR=PASS AYO; {Saturate if needed}1. AF=PASS AXO'

81. LT AR=-AR; ' {Negate output if needed}1. RTS' .ENDMOD;

82. П1.3. Вычисление логарифма1. MODULE Logarithms;1.garithm Approximations y=log10(x) y=ln(x)1. Calling Parameters

83. MR1 = Integer Portion of x in 16.0 twos complement MRO = Fractional Portion of x in 0.16 unsigned M3 = 1 L3 = 01. Return Values

84. SR1 = Y (4.12 format for log; 5.11 format for In)1. Altered Registers

85. AX0,AY0,AR,MY1 ,MX1 ,MF,MR,SE,SR,l31. Computation Time33 cycles (maximum)

86. CONST log2=H#2688,ln2=H#2C5D;1. VAR/DM lncoeffs5.;1. VAR/DM logcoeffs5.;

87. IT In coeffs : H#7FE3, H#C149, H#2491, H#EEF8, H#0404;

88. EQ JUMP noinv; {If input < 1, no need to invert}

89. SE=EXP MR1 (HI); {Invert input}1. SR=NORM MR1 (HI);1. SR=SR OR NORM MRO (LO);1. AX0=SR1;1. SI=H#0001;1. SR=NORM SI (HI);1. AY1=SR1;1. AY0=SR0;1. DIVS AY1 ,AX0;

90. DIVQ AXO; DIVQ AXO; DIVQ AXO; DIVQ AXO; DIVQ AXO; DIVQ AXO; DIVQ AXO; DIVQ AXO; DIVQ AXO; DIVQ AXO; DIVQ AXO; DIVQ AXO; DIVQ AXO; DIVQ AXO; DIVQ AXO; AR=AY0; noinv: MY0=AR;

91. MF=AR*MY0 (RND), MY1=DM(I3,M3); MR=AR*MY1 (SS), MX1=DM(13,M3); CNTR=3;1. DO approx UNTIL CE;

92. MR=MR+MX1*MF (SS), MX1=DM(I3,M3); approx: MF=AR*MF (RND); MR=MR+MX1*MF (SS); AR=MR1; AY0=H#4000; AF=PASS AY1; IF NE AR=AY0-MR1; AF=PASS AX1; IF LT AR=-AR; RTS; .ENDMOD;

93. АЛГОРИТМЫ ПЕРЕВОДА ДВОИЧНОГО КОДА В МУЛЬТИПЛИКАТИВНЫЙ И ПРИМЕРЫ ИХ РАБОТЫ

94. Соответствующее ему число х = -—1 VI + 2 ,

95. Шо:- <Зо {Знаки одинаковые}т^01 1 < 1 <п-1 {Обнуление мантиссы мультипликативного кода} § := 0 . с! 1 с12. с!п.1 { g := | ¿/1 модуль й)

96. Для к от 1 до п-1 делать цикл2"к {Сложить g со значением g, сдвинутым на кразрядов вправо } Если f < 1 то {А если / >=/, то g не изменяется§ := Г и к-тый разряд мультипликативного кода

97. С+Ог= 0.1111001 <1, следовательно т2.:=1 и 0:= в+вг к= 3 .1111001 Ог= .00011110+0г= 1.0001000 >1, следовательно гп 3.:=0 и в не меняется к= 4 .1111001 вг= .00001110+0г= 1.0000000 >1, следовательно ш 4. :=0 и й не меняется к= 5 .1111001 Сг= .0000011

98. С+Сг= 0.1111100 <1, следовательно ш5.:=1 и С:=С+Сг к= 6 .1111100 вг= .00000010+Сг= 0.1111101 <1, следовательно т 6.:=1 и 0:= О+йг к= 7 .1111101 йг= .0000000

99. С+Ог= 0.1111101 <1, следовательно ш 7.:=1 . Конец.1. Таким образом:х =0.1000001 =0.5078 т=0.1100111 = 0.5053 Погрешность 0.0025 < 0.0156х = .1000011к= 1 .10000111. Сг= .0100001

100. С+Ог= 0.1100100 <1, следовательно т 1.:=1 и С:= в+йгк= 2 .1100100вг= .0011001

101. С+Сг= 0.1111101 <1, следовательно т2.:=1 ив" в+Ог к= 3 .1111101 вг= .0001111

102. С+Ог= 1.0001100 >1, следовательно гп 3.:=0 и й не меняется к= 4 .1111101 Ог= .0000111

103. С+Ог= 1.0000100 >1, следовательно гп 4.:=0 и б не меняется к= 5 .1111101 Сг= .00000110+Сг= 1.0000000 >1, следовательно ш 5.:=0 и в не меняется к= 6 .1111101 Сг= .0000001

104. С+Ог= 0.1111110 <1, следовательно ш 6.:= 1 и 0:= в+вг к= 7 .1111110 Ог= .0000000

105. С+Сг= 0.1111110 <1, следовательно ш 7.:=1 . Конец.1. Таким образом:х =0.1000011 = 0.5234 т=0.1100011 =0.5211 Погрешность 0.0024 < 0.0156п=16. Формат 1.15 (Знак +15 разрядов мантиссы)

106. Погрешность перевода не более 2"13 = 0.00012207 (2"14 =0.0000610352) х = .100000000000000 ;к= 1 G = .100000000000000 1. Gr= .010000000000000

107. G+Gr= 0.110000000000000 <1, следовательно m 1.:= =1 иО:= С+вгк= 2 G = .110000000000000 1. Gr= .001100000000000

108. G+Gr= 0.111100000000000 <1, следовательно m 2.:= =1 иС:= О+Сгк= о G = .111100000000000 1. Gr= .000111100000000

109. G+Gr= 1.000011100000000 >1, следовательно m 3.: =0 и С не меняетсяк= 4 G = .111100000000000 1. Gr= .000011110000000

110. G+Gr= 0.1111111 10000000 <1, следовательно m 4.:= Ч иО:=С+Сгк= 5 G = .111111110000000 1. Gr= .000001111111100

111. G+Gr= 1.000001101111100 >1, следовательно m 5.:= =0 и О не меняетсяк= 6 G = .111111110000000 1. Gr= .000000111111110

112. G+Gr= 1.000000101111110 >1, следовательно m 6.:= =0 и О не меняетсяк= 7 G = .111111110000000 1. Gr= .000000011111111

113. G+Gr= 1.000000001111111 >1, следовательно m 7.: =0 и С не меняетсяк= 8 G = .111111110000000 1. Gr= .00000000111111!

114. G+Gr= 0.111111111111111 <1, следовательно m 8.:= = 1 и 0:= й+Сгк= 9 G = .111111111111111 1. Gr= .000000000111111

115. G+Gr= 1.0000000001 111 10 >1, следовательно m 9.: =0 и О не меняетсяк= 10 G = .111111111111111 1. Gr= .000000000011111

116. G+Gr= 1.000000000011110 >1, следовательно m10. :=0 и О не меняетсяк= 11 G = .111111111111111 1. Gr= .0000000000011 11

117. G+Gr= 1.000000000001110 >1, следовательно ml 1.: =0 и й не меняетсяк= 12 G = .111111111111111 1. Gr= .000000000000111

118. G+Gr= 1.000000000000110 >1, следовательно m12.: =0 и й не меняетсяк= 13 G = .111111111111111 1. Gr= .000000000000011

119. G+Gr= 1.000000000000010 >1, следовательно m13.: =0 и й не меняетсяк= 14 G = .111111111111111 1. Gr= .000000000000001

120. G+Gr= 1.000000000000000 >1, следовательно m14.: =0 и О не меняетсяк= 15 G = .111111111111111 1. Gr= .000000000000000

121. G+Gr= 0.111111111111111 <1, следовательно m15.:=l . Конец.1. Таким образом:х =0.100000000000000 = 0.5000000000 т=0.110100010000001 = 0.4999923710

122. Погрешность 0.0000076290 < 0.0000610352х = . 110000000000000 к= 1 G = .1100000000000001. Gr= .011000000000000

123. G+Gr= 1.001000000000000 >1, следовательно m 1.:=0 и G не меняется к= 2 G = .1100000000000001. Gr= .001100000000000

124. G+Gr= 0.111100000000000 <1, следовательно m 2.:= =1 и в- С+йгк= 3 G = .111100000000000 1. Gr= .000111100000000

125. G+Gr= 1.000011100000000 >1, следовательно m 3.:: =0 и в не меняетсяк= 4 G = .111100000000000 1. Gr= .000011110000000

126. G+Gr= 0.111111110000000 <1, следовательно m 4.:= =1 и С:= О+йгк= 5 G = .111111110000000 1. Gr= .000001111111100

127. G+Gr= 1.000001101111100 >1, следовательно m 5.:= :0 и й не меняетсяк= 6 G = .111111110000000 1. Gr= .000000111111110

128. G+Gr= 1.000000101111110 >1, следовательно m 6.:= =0 и С не меняетсяк= 7 G = .111111110000000 1. Gr= .000000011111111

129. G+Gr= 1.000000001111111 >1, следовательно m 7.:= :0 и О не меняетсяк= 8 G = .111111110000000 1. Gr= .000000001111111

130. G+Gr= 0.111111111111111 <1, следовательно m 8.:: =1 и С+Сгк= 9 G = .111111111111111 1. Gr= .000000000111111

131. G+Gr= 1.000000000111110 >1, следовательно m 9.:: =0 и О не меняетсяк= 10 G = .111111111111111 1. Gr= .000000000011111

132. G+Gr= 1.000000000011110 >1, следовательно m10.:: =0 и О не меняетсяк= 11 G = .111111111111111 1. Gr= .000000000001111

133. G+Gr= 1.000000000001110 >1, следовательно ml 1 .: :=0 и О не меняетсяк= 12 G = .111111111111111 1. Gr= .000000000000111

134. G+Gr 1.000000000000110 >1, следовательно m12.:: =0 и 0 не меняетсяк= 13 G = .111111111111111 1. Gr= .000000000000011

135. G+Gr= 1.000000000000010 >1, следовательно m13.:: =0 и в не меняетсяк= 14 G = .111111111111111 1. Gr= .000000000000001

136. G+Gr= 1.000000000000000 >1, следовательно m14. :=0 ийне меняетсяк= 15 G = .111111111111111 1. Gr= .000000000000000

137. G+Gr= 0.111111111111111 <1, следовательно m15. :=1 . Конец.1. Таким образом:х =0.110000000000000 = 0.7500000000 m=0.0101 ООО 10000001 = 0.7499885564

138. Погрешность 0.0000114436 < 0.0000610352х = . 111000000000000к= 1 G = .111000000000000 1. Gr= .011100000000000

139. G+Gr= 1.010100000000000 >1, следовательно m 1.:= =0 и G не меняетсяк= 2 G = .111000000000000 1. Gr= .001110000000000

140. G+Gr= 1.000110000000000 >1, следовательно m 2.:: =0 и G не меняетсяк= 3 G = .111000000000000 1. Gr= .000111000000000

141. G+Gr= 0.111111000000000 <1, следовательно m 3.:= = 1 и G:= G+Grк= 4 G = .111111000000000 1. Gr= .000011111100000

142. G+Gr= 1.000010111100000 >1, следовательно m 4.:= =0 и G не меняетсяк= 5 G = .111111000000000 1. Gr= .000001111110000

143. G+Gr= 1.000000111110000 >1, следовательно m 5.:= :0 и О не меняетсяк= 6 G = .111111000000000 1. Gr= .000000111111000

144. G+Gr= 0.111111111111000 <1, следовательно m 6.:= :1 иС:=С+Огк= 7 G = .111111111111000 1. Gr= .000000011111111

145. G+Gr= 1.000000011110111 >1, следовательно m 7.:= :0 и С не меняетсяк= 8 G = .111111111111000 1. Gr= .000000001111111

146. G+Gr= 1.000000001110111 >1, следовательно m 8.:= :0 и О не меняетсяк= 9 G = .111111111111000 1. Gr= .000000000111111

147. G+Gr= 1.000000000110111 >1, следовательно m 9.:= =0 и О не меняетсяк= 10 G = .111111111111000 1. Gr= .000000000011111

148. G+Gr= 1.000000000010111 >1, следовательно m10.: =0 и О не меняетсяк= 11 G = .111111111111000 1. Gr= .000000000001111

149. G+Gr= 1.000000000000111 >1, следовательно ml 1.: :=0 и О не меняетсяк= 12 G = .111111111111000 1. Gr= .000000000000111

150. G+Gr= 0.111111111111111 <1, следовательно m12.:: =1 и С:= О+Огк= 13 G = .111111111111111 1. Gr= .000000000000011

151. G+Gr= 1.000000000000010 >1, следовательно m13.: ;=0 и О не меняетсяк= 14 G = .111111111111111 1. Gr= .000000000000001

152. G+Gr= 1.000000000000000 >1, следовательно m14. :=0 и С не меняетсяк= 15 G = .111111111111111 1. Gr= .000000000000000

153. G+Gr= 0.111111111111111 <1, следовательно m15.:: =1 . Конец.1. Таким образом:х =0.111000000000000 = 0.8750000000 m=0.001001000001001 = 0.8749733501

154. Погрешность 0.0000266499 < 0.0000610352х = . 100000000000001к= 1 G = .1000000000000011. Gr= .010000000000000

155. G+Gr= 0.110000000000001 <1, следовательно гп 1.:=1 и С:= С+йгк= 2 G = .1100000000000011. Gr= .001100000000000

156. G+Gr= 0.111100000000001 <1, следовательно т 2.:=1 и 0:= О+Огк= j G = .1111000000000011. Gr= .000111100000000

157. G+Gr= 1.000011100000001 >1, следовательно ш 3.:=0 и О не меняетсяк= 4 G = .1111000000000011. Gr= .000011110000000

158. G+Gr= 0.111111110000001 <1, следовательно т 4.:=1 и 0:= й+Огк= 5 G = .1111111100000011. Gr= .000001111111100

159. G+Gr= 1.000001101111101 >1, следовательно т 5.:=0 и й не меняетсяк= 6 G = .1111111100000011. Gr= .000000111111110

160. G+Gr= 1.000000101111111 >1, следовательно ш 6.:=0 и С не меняетсяк= 7 G = .1111111100000011. Gr= .000000011111111

161. G+Gr= 1.000000010000000 >1, следовательно m 7.:=0 и G не меняетсяк= 8 G = .1111111100000011. Gr= .000000001111111 •

162. G+Gr= 1.000000000000000 >1, следовательно m 8.:=0 и G не меняетсяк= 9 G = .1111111100000011. Gr= .000000000111111

163. G+Gr= 0.111111111000000 <1, следовательно m 9.:=1 и G:= G+Grк= 10 G = .1111111110000001. Gr= .000000000011111

164. G+Gr= 0.111111111011111 <1, следовательно m10.:=l и G:= G+Grк= 11 G = .1111111110111111. Gr= .000000000001111

165. G+Gr= 0.111111111101110 <1, следовательно ml 1.:=1 и G:= G+Grк= 12 G = .1111111111011101. Gr= .000000000000111

166. G+Gr= 0.111111111110101 <1, следовательно m12.:=l и G:= G+Grк= 13 G = .1111111111101011. Gr= .000000000000011

167. G+Gr= 0.111111111111000 <1, следовательно m13.:=l и G:= G+Grк= 14 G = .1111111111110001. Gr= .000000000000001

168. G+Gr= 0.111111111111001 <1, следовательно m14.:=l и G:= G+Grк= 15 G = .1111111111110011. Gr= .000000000000000

169. G+Gr= 0.111111111111001 <1, следовательно m15.:=l . Конец.1. Таким образом:х =0.100000000000001 = 0.5000305176 m=0.110100001111111 = 0.5000203539

170. Погрешность 0.0000101636 < 0.0000610352х = . 100000000000011k= 1 G = .100000000000011 1. Gr= .010000000000001

171. G+Gr= 0.110000000000100 <1, следовательно т 1.:= Л и G:= G+Grk= 2 G = .110000000000100 1. Gr= .001100000000001

172. G+Gr= 0.111100000000101 <1, следовательно ш 2.:= и G:= G+Grk= j G = .111100000000101 1. Gr= .000111100000000

173. G+Gr= 1.000011100000101 >1, следовательно гп 3.:: =0 и G не меняетсяk= 4 G = .111100000000101 1. Gr= .000011110000000

174. G+Gr= 0.111111110000101 <1, следовательно ш 4.:= =1 и G:= G+Grk= 5 G = .111111110000101 1. Gr= .000001111111100

175. G+Gr= 1.000001110000001 >1, следовательно ш 5.:: =0 и G не меняетсяk= 6 G = .111111110000101 1. Gr= .000000111111110

176. G+Gr= 1.000000110000011 >1, следовательно т 6.:: =0 и G не меняетсяk= 7 G = .111111110000101 1. Gr= .000000011111111

177. G+Gr= 1.000000010000100 >1, следовательно гп 1\: =0 и G не меняетсяk= 8 G = .111111110000101 1. Gr= .000000001111111

178. G+Gr= 1.000000000000100 >1, следовательно т 8.:= =0 и G не меняетсяk= 9 G = .111111110000101 1. Gr= .000000000111111

179. G+Gr= 0.111111111000100 <1, следовательно т 9.:: =1 и G:= G+Grk= 10 G = .111111111000100 1651. Gr= .000000000011111

180. G+Gr= 0.111111111100011 <1, следовательно m10.:=l и G:= G+Gr k= 11 G= .111111111100011 Gr= .000000000001111

181. G+Gr= 0.111111111110010 <1, следовательно mll.:=l и G:= G+Gr k= 12 G= .111111111110010 Gr= .000000000000111

182. G+Gr= 0.111111111111001 <1, следовательно ш12.:=1 и G:= G+Gr k= 13 G= .111111111111001 Gr= .000000000000011

183. G+Gr= 0.111111111111100 <1, следовательно m13.:=l и G:= G+Gr k= 14 G= .111111111111100 Gr= .000000000000001

184. G+Gr= 0.111111111111101 <1, следовательно m14.:=l и G:= G+Gr k= 15 G = .111111111111101 Gr= .000000000000000

185. G+Gr= 0.111111111111101 <1, следовательно m15.:=l . Конец.1. Таким образом:x =0.100000000000011 0.5000915527 m=0.110100001111111 = 0.5000203539

186. Погрешность 0.0000711988 < 0.00012207

187. Соответствующее ему число х

188. Конец если Повторять цикл до тех пор, пока к < п-1.1. Пример работы Алгоритма 2

189. Погрешность перевода не более 2"13 = 0.00012207 (2"14 =0.0000610352)х = .100000000000000

190. Шаг= 1 G = .100000000000000 к= 21. Gr= .001000000000000

191. G+Gr= 0.101000000000000 было: т 2.=0 стало: ш[ 2]:=1

192. Шаг= 2 G = .101000000000000 к= 21. Gr= .001010000000000

193. G+Gr= 0.110010000000000 было: т2.='. 1 стало: ш[ 2]:=2

194. И1аг= 3 G = .110010000000000 к= 31. Gr= .000110010000000

195. G+Gr= 0.111000010000000 было: т 3.=0 стало: гп[ 3]:=1

196. Шаг= 4 G = .111000010000000 к= 41. Gr= .000011100001000

197. G+Gr= 0.111011110001000 было: ш4.=0 стало: т[ 4]:=1

198. Шаг= 5 G = .111011110001000 к= 41. Gr= .000011101111000

199. G+Gr= 0.111111100000000 было: т4.=1 стало: т[ 4]:=2

200. Шаг= 6 G = .111111100000000 к= 81. Gr= .000000001111111

201. G+Gr= 0.111111101111111 было: т 8.=0 стало: ш[ 8]:=1

202. Шаг= 7 G = .111111101111111 к= 81. Gr= .000000001111111

203. G+Gr= 0.111111111111110 было: т8.=: 1 стало: т[ 8]:=2

204. Шаг= 8 G = .111111111111110 к= 15. к>= п-1. Конец.1. Таким образом:х =0.100000000000000 = 0.5000000000 ш=0.021200020000000 = 0.5000152591

205. Погрешность 0.0000152591 < 0.0000610352х = .110000000000000

206. Шаг= 1 G = Gr= .110000000000000 .000110000000000 к= 3

207. G+Gr= 0.110110000000000 было: т 3.=0 стало: т[ 3]:=1

208. Шаг= 2 G = Gr= .110110000000000 .000110110000000 к= 3

209. G+Gr= 0.111100110000000 было: т3.=1 стало: ш[ 3]:=2

210. Шаг= 3 G = Gr= .111100110000000 .000001111001100 к= 5

211. G+Gr= 0.1 111 10101001100 было: т 5.=0 стало: т[ 5]:=1

212. Шаг= 4 G = Gr= .111110101001100 .000000111110101 к= 6

213. G+Gr= 0.111111101000001 было: т 6.=0 стало: т[ 6]:=1

214. Шаг= 5 G = Gr= .111111101000001 .000000001111111 к= 8

215. G+Gr= 0.111111111000000 было: т 8.=0 стало: гп[ 8]:=1

216. Шаг= 6 G = Gr= .111111111000000 .000000000011111 к=10

217. G-Gr= 0.11111 П 11011111 было: ш10.=0 стало: т[10]:=1

218. Шаг= 7 G = Gr= .111111111011111 .000000000011111 к=10

219. G+Gr= 0.111111111111110 было : т10.=1 стало: гп[10]:=

220. Шаг= 8 G = .111111111111110 к=15. к>= п-1. Конец.1. Таким образом:х =0.110000000000000 = 0.7500000000 т=0.002011010200000 = 0.7499920077

221. Погрешность 0.0000079923 < 0.0000610352х =.1111111000000001. Шаг= 11. Шаг= 2111111100000000 к= 800000000111 111

222. С+Ог= 0.11111110111 111 было: ш 8.=011111110111 111 к= 800000000111 111

223. С+Ог= 0.11111111111 110 было. гп 8.=111111111111 110 к=15. к >= п-1стало: ш 8.:=11. Шаг= 3 Таким образом:х =0.111111100000000 = 0.9921875000 т=0.000000020000000 = 0.9922330391

224. Погрешность 0.0000112512 < 0.0000610352х1. Шаг= 11. Шаг= 21. Шаг= 31. Шаг= 41. Шаг= 51. Шаг= 61. Шаг= 71. Шаг= 81. Шаг= 91000000000000010 = .100000000000001 к= 20010000000000000+Сг= 0.101000000000001 было:о = .101000000000001 к=21. Сг= .001010000000000

225. С+Ог= 0.110010000000001 было:й = .110010000000001 к= 31. Сг= .000110010000000

226. С+Сг= 0.111000010000001 было:111000010000001 к= 41. Сг= .0000111000010000+бг= 0.111011110001001 было:в = .111011110001001 к= 4000011101111000

227. С+Ог= 0.111111100000001 было:111111100000001 к= 8000000001111111

228. С+Ог= 0.11111 1110000000 было:в = .111111110000000 к= 9000000000111111

229. С+Ог= 0.111111110111111 было:б = .111111110111111 к= 91. Сг= .000000000111111

230. С+Ог= 0.111111111111110 было:111111111111110. к=15. к1. Таким образом:х =0.100000000000001 = 0.5000305176 m=0.021200012000000 = 0.5000133592

231. Погрешность 0.0000171584 < 0.0000610352х = . 1000000000000111. Шаг= 11. Шаг= 21. Шаг= 31. Шаг= 41. Шаг= 51. Шаг= 61. Шаг= 71. Шаг= 81. Шаг= 91. Шаг=101. Шаг=11

232. G = Gr= G+Gr= G = Gr= G+Gr= G = Gr= G+Gr= G = Gr= G+Gr= G = Gr= G+Gr= G = Gr= G+Gr= G = Gr= G+Gr= G = Gr= G+Gr= G = Gr= G+Gr= G = Gr= G+Gr= G =0