Содержание к диссертации
Введение
ГЛАВА 1. Методы и средства организации высокоточных арифметических вычислений 13
1.1. Современные области применения высокоточных вычислений 14
1.1.1. Моделирование климата 18
1.1.2. Исследование орбитальной эволюции небесных тел 19
1.1.3. Экспериментальная математика 20
1.1.4. Изучение постоянной тонкой структуры (постоянной Зоммерфельда)... 21
1.1.5. Исследование электромагнитного рассеяния 21
1.1.6. Изучение n-тельных кулоновских атомных систем 22
1.1.7. Моделирование атмосферы сверхновых звезд 23
1.2. Методы и средства высокоточных вычислений 24
1.2.1. Арифметика длинных позиционных чисел 26
1.2.2. Интервальные вычисления 30
1.2.3. Символьные вычисления 31
1.2.4. Постбинарные вычисления 32
1.2.5. Модулярная арифметика 33
1.3. Исследование быстродействия современных программных средств высокоточных вычислений 36
1.4. Применение модулярной арифметики для решения задач целочисленной многоразрядной обработки 37
1.5. Выводы по главе 39
ГЛАВА 2. Быстродействующие методы и алгоритмы выполнения немодульных операций в системах остаточных классов 41
2.1. Основные принципы модулярной обработки чисел 42
2.2. Проблема выполнения немодульных операций 44
2.2.1. Способы интерпретации позиционного значения модулярного кода 46
2.2.2. Приближенное CRT-декодирование 47
2.3. Метод интервально-позиционных характеристик
2.3.1. Формализация оценки величинві модулярного представления в терминах интервалвнвгх ввічислений 52
2.3.2. Достаточнвіе признаки корректности немодулвнвгх операций 55
2.3.3. Арифметика интервалвно-позиционнвгх характеристик 59
2.3.4. Основнвіе алгоритмві выполнения немодулвнвіх операций 60
2.3.5. Оценка сложности алгоритмов 65
2.3.6. Результаты экспериментов 70
2.4. Высокоточное вычисление интервально-позиционной характеристики 72
2.4.1. Задача минимизации погрешности вычисления ИПХ 72
2.4.2. Алгоритм ISaC 73
2.4.3. Результаты экспериментов 84
2.5. Быстрое масштабирование чисел в СОК степенью двойки 86
2.5.1. Постановка задачи. Метод половинного деления 86
2.5.2. Метод модулярного масштабирования с увеличенным шагом 88
2.5.3. Результаты экспериментов 94
2.6. Выводы по главе 95
ГЛАВА 3. Применение модулярной арифметики для организации высокоточных вычислений 98
3.1. Арифметика с плавающей точкой стандарта IEEE-754 99
3.2. Модулярно-позиционный формат с плавающей точкой для представления чисел большой разрядности 102
3.3. Оценка погрешностей модулярно-позиционных вычислений 109
3.3.1. Расстояние, машинный эпсилон, функция шага, ошибки округления 109
3.3.2. Алгоритм генерации набора модулей для обеспечения заданной точности модулярно-позиционных вычислений 112
3.4. Алгоритмы высокоточной арифметики в модулярно-позиционном формате с плавающей точкой 114
3.4.1. Округление 114
3.4.2. Выравнивание порядков 119
3.4.3. Сложение, вычитание и сравнение 122
3.4.4. Умножение 128
3.4.5. Деление 130
3.5. Экспериментальное исследование быстродействия алгоритмов 132
3.6. Рекомендации по применению разработанных алгоритмов 136
3.7. Выводы по главе 137
ГЛАВА 4. Программная библиотека высокоточной арифметики в модулярно-позиционном формате с плавающей точкой 139
4.1. Типы данных и API 139
4.2. Структурная организация 141
4.3. Результаты экспериментальной апробации 144
4.4. Области практического применения разработанных программных решений 148
4.5. Выводы по главе 150
Заключение 151
Список сокращений и условных обозначений 153
Список терминов 158
Список литературы
- Экспериментальная математика
- Способы интерпретации позиционного значения модулярного кода
- Модулярно-позиционный формат с плавающей точкой для представления чисел большой разрядности
- Области практического применения разработанных программных решений
Экспериментальная математика
В основе представленной классификации лежат причины (ситуации), приводящие к необходимости использования высокоточных вычислений. Рассмотрим их более подробно.
Решение плохо обусловленных систем линейных алгебраических уравнений [СЛАУ) и сопряженных задач алгебры. Многие проблемы нехватки точности связаны с необходимостью решения плохо обусловленных систем большого порядка. При использовании 64-битной арифметики решение таких систем может сопровождаться получением существенных ошибок [86]. Вопросы анализа погрешностей при решении задач линейной алгебры рассматриваются в классических работах [13; 16; 52; 148]. Если задача имеет «некорректную постановку», то даже при небольшой ее размерности могут появляться значительные ошибки округления. Типичный пример — СЛАУ с матрицей Гильберта в качестве коэффициентов [46]. Задачи данного класса возникают в строительной механике [80], в вычислительной гидродинамике, при решении дифференциальных уравнений неявными методами, при изучении кулоновских атомных систем [85; 101], при исследовании электромагнитного рассеяния [87; 89] и т.д.
Решение задач численного анализа. Существенное накопление ошибок округления происходит при использовании формул приближенного дифференцирования для отыскания производных высоких порядков, а также при решении жестких систем дифференциальных уравнений (ДУ), требующих использования малого шага по временным и пространственным координатам для получения адекватного результата [6, с. 472-481; 70]. Примерами задач, требующих решения жестких систем ДУ, являются задачи химической кинетики с одновременным присутствием очень медленно и очень быстро протекающих химических реакций [74, с. 11], исследование суточных колебаний озона в атмосфере [52, с. 364], решение электрического уравнения Ван дер Поля, а также задачи расчета динамики многозвенных систем, имеющие важное значение таких областях, как робототехника и биомеханика [74, с. 579].
Вычисление рекуррентных формул и больших сумм. Аномальные результаты часто связаны с потерей ассоциативности при суммировании (см., например, [123, с. 229-230]), особенно при его выполнении на параллельной компьютерной системе, где порядок суммирования не может контролироваться [86; 140]. Необходимость вычисления больших сумм возникает, в частности, при использовании квадратурных формул для интегрирования полиномов высоких степеней на сетках с малым шагом. К практическим задачам, основанным на вычислении рекуррентных соотношений, чувствительных к ошибкам округления, относится реализация дискретного преобразования Фурье в форме рекурсивного фильтра — алгоритм Гёрцеля [57, с. 203], а также рекурсивное дискретное косинус-преобразование [150]. Эти задачи имеют важное значение в цифровой обработке сигналов. В теории приближений важную роль играют полиномы Чебышева, которые также вычисляются с помощью рекуррентных соотношений. 4. Крупномасштабное моделирование. Вычисления, устойчивые на небольших задачах, выполняемые на однопроцессорных системах, могут сопровождаться значительными численными ошибками при масштабировании до уровня массивно-параллельных систем. К крупномасштабным задачам относится моделирование климата [12, с. 17-20; 71; 86;87; 110], моделирование атмосферы сверхновых звезд [85; 109], моделирование процессов, протекающих в ядерных реакторах, расчет дозвукового обтекания летательного аппарата [12, с. 22].
Продолжительное моделирование физических процессов. Практически любой процесс физического моделирования, выполняемого в течение длительного времени, в конечном итоге отходит от реальности. Это связано с накоплением ошибок округления в дополнение к ошибкам, связанным с дискретизацией по времени и пространству. Показательным примером является задача численного исследования орбитальной эволюции небесных тел [8; 85; 125].
Исследование процессов и явлений микромира. Чтобы корректно исследовать рассматриваемое явление часто возникает необходимость в использовании мелкомасштабного разрешения, что приводит к накоплению ошибок округлений [86]. В частности, необходимость в использовании высокоточных вычислений возникает при решении уравнений Шредингера в процессе изучения постоянной тонкой структуры [85; 149].
Поиск соотношений в экспериментальной математике. Многие результаты в данной отрасли науки (например, формула Бэйли- Боруэйна-Плаффа для вычисления числа 7г) не могли быть получены без использования вычислений с очень высокой точностью [86].
В работе Ш. А. Оцокова [59] представлена другая классификация высокоточных задач, во многом схожая с приведенной выше. Далее подробнее рассматриваются некоторые из задач, требующих для корректного решения привлечения аппарата высокоточных вычислений.
Задача моделирования погоды (климата) [12, с. 17-20; 71] имеет хаотическую природу — при внесении микроскопических изменений в текущее состояние системы, будущее ее состояние может оказаться совершенно иным. Это связано с необходимостью выполнения сложных расчетов над большими массивами данных для получения статистической достоверности прогноза. Поэтому ученые, занимающиеся моделированием климата, давно смирились с тем, что результаты работы их приложений существенно отклоняются от базовых расчетов уже при самой незначительной модификации среды выполнения, например, при изменении количества процессоров, используемых для вычислений. Это приводит к сложностям сопоставления результатов различных исследований и даже, зачастую, не позволяет однозначно определить корректность работы отдельно взятого приложения в конкретной вычислительной системе [87]. Данная проблема исследована Крисом Дингом (Chris H.Q. Ding) и Еленой Хи (Yun Helen Не) из Национальной Лаборатории Орландо Лоуренса в Беркли (Lawrence Berkeley National Laboratory, LBNL), которые обнаружили, что практически все погрешности в результатах моделирования обуславливаются одним циклом вычислений, на шаге расчета ассимиляции атмосферных данных с сопутствующими вычислениями сопряженного градиента [ПО]. Хи и Динг предложили простое решение проблемы, состоящее в использовании для выполнения этих циклов 128-битной арифметики с плавающей точкой (мантисса состоит из 113 бит), обеспечиваемой пакетом DDFUN. Это решение существенно сократило численную изменчивость результатов работы всего приложения и позволило вычислительной системе работать без остановок для выверки данных гораздо дольше, чем прежде1 [86].
Способы интерпретации позиционного значения модулярного кода
Анализ интервально-позиционных характеристик, как показано в предыдущем параграфе, решает проблему обеспечения достоверности вычислений при выполнении немодульных операций, однако для его наибольшей результативности необходимо выполнение двух условий.
Во-первых, вычисление ИПХ должно быть быстрым, поэтому разрядность их границ должна быть много меньше разрядности произведения модулей СОК. Предпочтительно, чтобы границы ИПХ были представлены в стандартных числовых форматах и не возникало необходимости использования длинной арифметики для их вычисления.
Во-вторых, точность ИПХ должна быть достаточной для однозначного определения результата немодульной операции для большей части модулярных чисел (необходимо минимизировать вероятность ртгс) Легко видеть, однако, что эти требования являются взаимно противоречивыми. Действительно, относительная погрешность ИПХ (для X ф 0) — это величина
Если зафиксировать X, то Е(Х/Р) — 0 при Р — оо. Из-за ошибок округления, возникающих при вычислении границ ИПХ в арифметике с фиксированным количеством цифр, величина ее диаметра (2.14) остается неизменной, что приводит к росту ошибки (2.21). Таким образом, если разрядность произведения модулей существенно больше разрядности границ ИПХ, а число лежит вблизи нижней грани полного диапазона СОК, то вычисление формул (2.11) и (2.12) приводит к значительным относительным погрешностям, что вызывает снижение информативности ИПХ и затрудняет использование таких «неточных» характеристик при выполнении немодульных операций (возрастает вероятность нарушения второго формального условия корректности результата). Более того, могут возникать ситуации антипереполнения нижней границы, следствием чего является нарушение первого формального условия.
И напротив, весь смысл использования ИПХ теряется, если разрядность их границ не многим меньше разрядности произведения модулей, поскольку при этом время вычисления формул (2.11) и (2.12) сравнимо со временем преобразования числа из представления в остаточных классах к позиционному представлению с использованием системы ортогональных базисов, и целесообразнее использовать менее сложный MRC-метод.
Из сказанного следует вывод о важности задачи минимизации относительной погрешности вычисления интервально-позиционной характеристики в условиях ограниченной разрядности ее границ. Анализ предметной области показывает, что данная задача не разрешима в рамках использования формул (2.11) и (2.12), поэтому необходима разработка других более эффективных алгоритмических решений. Одно из таких решений рассматривается далее. где mum — двоичные /с-разрядные мантиссы, е — порядок (экспонента), обычно одинаковый для верхней и нижней границ. Зафиксируем є — верхний предел допустимой относительной ошибки ИПХ. В соответствии с выражением (2.21), число X, для которого относительная ошибка ИПХ 81(Х/Р) не превышает є, должно удовлетворять неравенству
Таким образом, формулы (2.11) и (2.12) обеспечивают вычисление ИПХ с ошибкой, не превышающей допустимого предела є, не для всех чисел из полного диапазона СОК, а лишь для их подмножества1 Х фР X Р — 1, и не пригодны для вычислений, если число лежит в промежутке [1, фР — 1]. Пусть, например, Р = 2128, п = 8 и к = 53. Тогда ИПХ для числа X = 1.5-286 будет вычислена с погрешностью (в худшем случае) 51(Х/Р) « 0.0026 2-8. Взяв меньшее число, например X = 1.5 285, получим 51(Х/Р) « 0.0052 2-8. Следовательно, для заданного разряда точности є = 2 8 необходимо, чтобы X было не меньше 286.
Повысить точность позволяет смещенная схема вычисления интервально-позиционной характеристики, представленная на рисунке 2.9. В основе схемы лежит свойство быстрой безошибочной делимости чисел с плавающей точкой на натуральные степени двойки, даже если эти степени превышают размер машинного слова процессора. причем если v определяет такую натуральную степень двойки, что X v удовлетворяет условию (2.22), то его ИПХ будет вычислена с требуемой точностью. На этапе (З) выполняется безошибочная корректировка — обратный переход от смещенной ИПХ к искомой, не сопровождаемый возникновением погрешностей (при условии, что он выполняется в пределах нормализованного диапазона целевого формата с плавающей точкой). Для реализации смещенной схемы непосредственное вычисление числа X v не требуется. Достаточно, если ХИ только при условии, что не произойдет антипереполнения нижней или переполнения верхней границы. X Є [1, фР — 1], вместо (2.11) и (2.12) использовать модифицированные выражения: где v выбрано так, чтобы произведение (X 2V) удовлетворяло условию (2.22), то есть лежало в диапазоне [фР, Р — 1]. Основной смысл соотношений (2.23) и (2.24) состоит в уменьшении относительной ошибки не за счет уменьшения ее числителя — абсолютной опіибки, а за счет увеличения знаменателя — относительной величины модулярного числа, с последующим делением результата на 2V, которое выполняется совсем просто и без потери точности, далее если 2 " больше машинного слова.
Модулярно-позиционный формат с плавающей точкой для представления чисел большой разрядности
Способ определения значения функции rsh(M) зависит от арифметической операции, которая будет выполнена. Рассмотрим для примера определение необходимости округления при умножении. Пусть дано число х — {s, М, А, 1(М/Р)}, где М = (mi, гаг,... , тп) — модулярная мантисса, значения которой лежат в диапазоне Т = [О, Р — 1]. Обозначим Р = \\/ Р — 11. Разобьем диапазон D на два интервала: T work = [О, Р \ и T)crit = [Р1 + 1, Р — 1]. Интервал T work назовем рабочим диапазоном, и если М Є T work, то округление числа х не требуется. Интервал Т сгц — это критический диапазон и если М Є Т сгц, то необходимо выполнить округление, иначе при выполнении умножения на второе такое же число мантисса результата окажется за пределами D. Возникает необходимость нахождения значения целочисленной функции rsh(M), определяющей коэффициент, которым необходимо промасштабировать мантиссу М для того, чтобы вернуть ее в пределы рабочего диапазона T work- Значение rsh(M) определяется равенством 2r,s/l(M) = М/Р . Логарифмируя обе его части с учетом целочисленное показателя степени имеем: rsh(M) = log2 (М/Р1)]. Таким образом, проверка необходимости округления МП-числа формализуется в виде следующего алгоритма.
В результате работы представленного алгоритма определяется целое число rsh(M) — такой показатель коэффициента масштабирования модулярной мантиссы, что если М Р , то [M/2rsh(M \ Р . Блок-схема алгоритма приведена на рисунке П8.1 приложения 8. Там же рассмотрен численный пример. Необходимость округления при выполнении операций выравнивания порядков и сложения чисел определяется аналогичным образом.
Особенности. В отдельных случаях алгоритм может приводить к получению незначительно завышенного результата, поскольку на последнем шаге значение функции rsh(M) принимается по неотрицательному максимуму. Это означает, что при округлении возможна потеря дополнительных разрядов двоичного представления мантиссы. И хотя эмпирические данные показывают, что эти потери несущественны (при изменении значения мантиссы в 512-битном диапазоне при округлении может теряться дополнительно лишь 1-2 бит), говорить о совместимости алгоритма округления со стандартом IEEE-754 не вполне правомерно.
Анализ временной сложности. Поскольку необходимость преобразования модулярных мантисс в двоичную систему счисления или систему со смешанным основанием полностью исключается, алгоритм имеет низкую вычислительную сложность — 0(1), инвариантную по отношению к числу модулей СОК (при условии, что ИПХ мантиссы известна на входе).
Выполнен численный эксперимент, в ходе которого определялась необходимость округления модулярных мантисс, представленных в СОК с базисом {7, 9,11,13} для которого Р = 94. Результаты эксперимента представлены на рисунке 3.5.
Развернутая схема представленного алгоритма, раскрывающая основные этапы модулярного масштабирования мантиссы, приведена на рисунке П8.2 приложения 8.
Анализ временной сложности. Сложность всех шагов, кроме R2 и R5 составляет 0(1). Шаг R5 требует 0(п) операций (здесь как и везде п — размер базиса СОК в котором представляется мантисса). На шаге R2 требуется a = rsh(M)/h итераций [h — шаг масштабирования), каждая из которых требует около 7п операций. В лучшем из нетривиальных случаев округление выполнится за одну итерацию (а = 1). Таким образом, общая сложность алгоритма округления имеет оценки снизу и сверху соответственно П(п) и О (an). Благодаря эффективному методу масштабирования, в процессе округления не требуется преобразования модулярных мантисс в позиционную систему счисления.
Анализ пространственной сложности. Основные затраты памяти приходятся на хранение матрицы (2.42) корректировочных кодов формального частного. Ее размерность составляет (2h — 1) х п. Каждый элемент представляет собой целое неотрицательное число, разрядность которого не превышает разрядности соответствующего модуля СОК. Полагая log2Pi + 1] = к для всех г = 1,2,...,п, общий объем требуемой памяти в битах будет определяться значением к (2" — 1) п. Объем матрицы мультипликативных инверсий степеней двойки (2.37) оценивается значением
При вычислениях в позиционных форматах выравнивание чисел выполняется до большего порядка. Так, если х — {sx,mx,ex} и у — {sy,my,ey} — два двоичных числа, то их выравнивание до большего порядка состоит в сдвиге мантиссы меньшего из них вправо на Де = \ех — еу\ бит и выборе в качестве результатного порядка е = тах{еж, еу}. При этом в худшем случае теряется Де значимых бит мантиссы меньшего из чисел.
Пусть в модулярно-позиционном формате заданы два числа хну, представленные кортежами {sx, МХ,ХХ,1(МХ/Р)} и {sy, Му, ХУ,1(МУ/Р)}. Тогда их порядки целесообразно выравнивать до меньшего, что равносильно умножению модулярной мантиссы, соответствующей операнду с большим порядком, на ДА-ю степень двойки. Это позволит избежать потери точности в процессе выравнивания и ускорит его, поскольку умножение в СОК выполняется значительно проще деления. При выравнивании порядков до меньшего возникает задача контроля переполнения при умножении модулярной мантиссы на степень двойки. Эта задача решается с использованием ИПХ: если ИПХ модулярной мантиссы больше 2 лл , то произведение М 2 выйдет за допустимые пределы . Для предотвращения этого необходимо выполнить предвычислительное округление, промасштабировав мантиссу числа с меньшим порядком. Возникает необходимость быстрого определения коэффициента масштабирования. Данная задача формализуется следующим образом. Пусть дано число х — {s, М, X, 1(М/Р)} с мантиссой, представленной в базисе Р\,Р2, Рп- Для заданного показателя степени ДА необходимо найти целое положительное значение rsh(M), удовлетворяющее неравенству (здесь необходимо вычислить два значения, соответствующих верхней и нижней границам ИПХ, и выбрать максимальное). При работе с разномасштабными числами разность АЛ может быть большой, что приводит к необходимости использования длинной арифметики для преобразования 2 в модулярную систему. Указанный недостаток устраняется выбором необходимого модулярного кода из предварительно вычисленной матрицы N, элементами которой являются все вычеты натуральных степеней двойки от 1 до [log2 Р\ по всем модулям:
Анализ временной сложности. Все шаги, кроме Е4 и Е5 имеют низкую сложность 0(1). Шаг Е5 требует 0(п) операций (напомним, для анализа сложности было принято предположение, что вычисления выполняются последовательно по всем модулям СОК, хотя вполне естественна их параллельная реализация). В худшем случае (при большой разности порядков) на шаге Е4 требуется вычислить значения интервально-позиционных характеристик (ветвь Е4.2 — Е4.2.3) и масштабировать мантиссу Мх степенью двойки от rsh(My) (шаг Е4.2.2). Для масштабирования потребуется в среднем a = rsh(My)/h итераций. В лучшем из нетривиальных случаев ни вычисления ИПХ ни округления не требуется (ветвь Е4.1). Таким образом, сложность алгоритма выравнивания порядков имеет оценки О (an) и Q(n). Здесь стоит отметить результаты одного эмпирического исследования, обсуждаемые в работе [123, с. 254]. Данное исследование показывает, что при решении «типовых» численных задач в двоичной арифметике порядки операндов отличаются в среднем на 3.1 двоичных разряда. Если учесть при этом, что rsh(My) равняется АА лишь в исключительных случаях (обычно rsh(My) « АА), то при шаге масштабирования h = 20-1-25 бит вполне оправданно полагать, что округление на шаге Е4.2.2 выполнится за одну итерацию либо вообще не потребуется.
Области практического применения разработанных программных решений
Алгоритмы высокоточных вычислений в базисе модулярно-позиционного формата с плавающей точкой, воплощенные в разработанной программной библиотеке, применимы для решения широкого перечня научных и технических задач, критичных к ошибкам округления. Классификация таких задач приведена в 1.1 (см. стр. 16). На основании специфики алгоритмов, сформулированных рекомендаций по их практическому применению (см. 3.6 на стр. 136) и результатов проведенных численных экспериментов (см. 3.5 на стр. 132 и 4.3 на стр. 144) молено выделить следующие прикладные области высокоточных вычислений, в которых применение разработанных алгоритмических и программных решений позволит добиться наиболее значительного повышения быстродействия.
Говоря о решении плохо обусловленных линейных систем в целом, безотносительно задач строительной механики, следует отметить метод сопряженных градиентов [146]. Данный численный метод является представителем класса итерационных методов Крыловского типа. Как и другие представители данного класса, он оперирует матрицами и векторами большой размерности, причем в процессе вычислений выполняется большое количество арифметических умножений и сложений и минимальное количество делений. Это дает основания полагать, что его реализация в базисе модулярно-позиционной арифметики с плавающей точкой окажется быстродействующей, по сравнению с позиционной многоразрядной реализацией.
Высокоточное вычисление рядов Тейлора. Разложение функции в бесконечную сумму степенных функций (ряд Тейлора) — актуальная задача, востребованная как в научных, так и в инженерных расчетах. С использованием рядов Тейлора вычисляются экспоненциальные, тригонометрические, гиперболические и многие другие математические функции. Однако, в зависимости от значений аргумента, процесс суммирования зачастую оказывается чувствительным к ошибкам округления (например, при вычислении функции ех для отрицательных аргументов х ряд становится знакочередующимся и слагаемые на несколько порядков превосходят конечный результат). Анализ аргументов для выбора численно устойчивого алгоритма часто затруднен, поэтому для получения результата с требуемой точностью возникает необходимость использования длинной арифметики. Следует ожидать, что использование разработанной программной библиотеки позволит повысить скорость вычисления суммы ряда. Поскольку знаменатели в представлении членов ряда не зависят от значений аргумента, операции деления легко сводятся к операциям умножения на обратные коэффициенты (например, при вычислении функций sin(x) и cos(x) вместо делений на факториалы к\ могут быть выполнены умножения на коэффициенты 1/к\, которые заранее вычислены с высокой точностью и записаны в подстановочную таблицу в модулярно-позиционном формате).
Дискретное преобразование Фурье и цифровая фильтрация. Дискретные преобразования Фурье (ДПФ) получили широкое практическое применение в таких областях, как сжатие звука, сжатие изображений, декодирование тональных сигналов в телефонии, тригонометрическая интерполяция и пр. ДПФ определяется равенством где N — количество компонент разложения сигнала, к — индекс частоты, хп — измеренное значение сигнала. Несмотря на то, что в общем случае (4.4) вычисляется на основе одного из алгоритмов, в ряде случаев наиболее рациональным подходом является прямое вычисление произведений и их суммирование. При вычислениях с ограниченной разрядностью каждое умножение и сложение в (4.4) вносит ошибку округления [57, с. 322], и при попытке получить точное квантование полученный результат сопровождается значительной погрешностью (шумом). Для устранения этого недостатка может быть использована разработанная библиотека высокоточных вычислений. Наличие в формуле (4.4) лишь операций сложения и умножения позволяет рассчитывать на высокую скорость выполнения преобразования.
Задачи, аналогичные (4.4), возникают также при построении цифровых фильтров с конечной импульсной характеристикой, поэтому все приведенные положения в полной мере распространяются и на них.
Представленный перечень прикладных областей и задач, в которых применение программной реализации алгоритмов высокоточной арифметики в модулярно-позиционном формате с плавающей точкой является эффективным, разумеется, не является исчерпывающим. К таким областям следует отнести, по меньшей мере, решение краевых задач для дифференциальных уравнений явными разностными методами, высокоточную интерполяцию полиномов высоких степеней, решение жестких систем дифференциальных уравнений, возникающих в задачах гидродинамики, химической кинетики, теории ядерных реакторов, теории автоматического управления и пр. (для их решения, как правило, применяются неявные методы, требующие решения СЛАУ больших порядков), а также широкий спектр задач из области научных вычислений, некоторые из которых рассмотрены в 1.1.
