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

• Автор: Исупов, Константин Сергеевич
• Шифр специальности: 05.13.15
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Киров
• Количество страниц: 256 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ

ГЛАВА 1. МЕТОДЫ И СРЕДСТВА ОРГАНИЗАЦИИ ВЫСОКОТОЧНЫХ АРИФМЕТИЧЕСКИХ ВЫЧИСЛЕНИЙ

§ 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. Символьные вычисления
1.2.4. Постбинарные вычисления
1.2.5. Модулярная арифметика
§ 1.3. Исследование быстродействия современных программных средств высокоточных вычислений
§ 1.4. Применение модулярной арифметики для решения задач целочисленной многоразрядной обработки
§ 1.5. Выводы по главе
ГЛАВА 2. БЫСТРОДЕЙСТВУЮЩИЕ МЕТОДЫ И АЛГОРИТМЫ ВЫПОЛНЕНИЯ
НЕМОДУЛЬНЫХ ОПЕРАЦИЙ В СИСТЕМАХ ОСТАТОЧНЫХ КЛАССОВ
§ 2.1. Основные принципы модулярной обработки чисел
§ 2.2. Проблема выполнения немодульных операций
2.2.1. Способы интерпретации позиционного значения модулярного кода
2.2.2. Приближенное СЛТ-декодирование
§ 2.3. Метод интервально-позиционных характеристик
2.3.1. Формализация оценки величины модулярного представления в терминах интервальных вычислений
2.3.2. Достаточные признаки корректности немодульных операций
2.3.3. Арифметика интервально-позиционных характеристик
2.3.4. Основные алгоритмы выполнения немодульных операций
2.3.5. Оценка сложности алгоритмов
2.3.6. Результаты экспериментов
§ 2.4. Высокоточное вычисление интервально-позиционной характеристики
2.4.1. Задача минимизации погрешности вычисления ИПХ
2.4.2. Алгоритм КаС
2.4.3. Результаты экспериментов
§ 2.5. Быстрое масштабирование чисел в СОК степенью двойки
2.5.1. Постановка задачи. Метод половинного деления
2.5.2. Метод модулярного масштабирования с увеличенным шагом
2.5.3. Результаты экспериментов
§ 2.6. Выводы по главе
ГЛАВА 3. ПРИМЕНЕНИЕ МОДУЛЯРНОЙ АРИФМЕТИКИ ДЛЯ ОРГАНИЗАЦИИ
ВЫСОКОТОЧНЫХ ВЫЧИСЛЕНИЙ
§ 3.1. Арифметика с плавающей точкой стандарта ІЕЕЕ-
§ 3.2. Модулярно-позиционный формат с плавающей точкой для представления чисел
большой разрядности
§ 3.3. Оценка погрешностей модулярно-позиционных вычислений
3.3.1. Расстояние, машинный эпсилон, функция шага, ошибки округления—
3.3.2. Алгоритм генерации набора модулей для обеспечения заданной точности модулярно-позиционных вычислений
§ 3.4. Алгоритмы высокоточной арифметики в модулярно-позиционном формате с
плавающей точкой
3.4.1. Округление
3.4.2. Выравнивание порядков
3.4.3. Сложение, вычитание и сравнение
3.4.4. Умножение
3.4.5. Деление
§ 3.5. Экспериментальное исследование быстродействия алгоритмов

§ 3.6. Рекомендации по применению разработанных алгоритмов
§ 3.7. Выводы по главе
ГЛАВА 4. ПРОГРАММНАЯ БИБЛИОТЕКА ВЫСОКОТОЧНОЙ АРИФМЕТИКИ В
МОДУЛЯРНО-ПОЗИЦИОННОМ ФОРМАТЕ С ПЛАВАЮЩЕЙ ТОЧКОЙ
§ 4.1. Типы данных и API
§ 4.2. Структурная организация
§ 4.3. Результаты экспериментальной апробации
§ 4.4. Области практического применения разработанных программных решений
§ 4.5. Выводы по главе
ЗАКЛЮЧЕНИЕ
СПИСОК СОКРАЩЕНИЙ И УСЛОВНЫХ ОБОЗНАЧЕНИЙ
СПИСОК ТЕРМИНОВ
СПИСОК ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЯ
Приложение 1. Программное обеспечение высокоточных вычислений
Приложение 2. Оценка быстродействия высокоточных программных библиотек
Приложение 3. Комплекс для целочисленных многоразрядных вычислений в СОК —
Приложение 4. Устройства для выполнения немодульных операций в СОК
Приложение 5. Анализ сложности методов выполнения немодульных операций
Приложение 6. Вероятность коллизии интервально-позиционных характеристик.
Приложение 7. Генерация векторного смещения для высокоточного вычисления интервально-позиционной характеристики
Приложение 8. Алгоритмы вычислений в МП-формате с плавающей точкой
Приложение 9. Исходные коды основных алгоритмов
Приложение 10. Акты о внедрении результатов диссертационной работы

реализации всех алгоритмов требуется 20 различных подстановочных таблиц, общий объем которых зависит от количества модулей СОК и может быть весьма большим.
Российским ученым Ш. А. Оцоковым в работе [59] был предложен способ представления в системе остаточных классов рациональных чисел с фиксированной точкой. Согласно нему число х — хг, Х2, ■. ■, хп/ . У, у2,..., Ук!, где все хг — разряды целой части, а уд — разряды дробной части, преобразуется в модулярный формат с перемещаемой точкой:
х= [<01,02,..., а„>,<], (1.3)
где (ах, я2,... ,ап) — мантисса, представленная в СОК с основаниями {рг,Р2, ■ ■ • ,Рп}, а
порядок. Значение каждой знакопозиции мантиссы вычисляется в соответствии с выражением
сц = К • 2_‘|р., где К = х • 2к! — целое число такое, что К < 2пг+к/ — 1, а п/ и к/ — количество разрядов целой и дробной частей исходного рационального числа х. Для введения операции деления в работе [59] помимо модулярного представления с перемещаемой точкой предлагается использовать двойное представление чисел: в модулярном формате (1-3) и в позиционном вложенном формате с плавающей точкой. Таким образом, получается единый модулярно-позиционный формат (МПФ) представления чисел:
х = [{а1,а2,...,ап),*,т/,р/], (1.4)
где mf — позиционная мантисса числа, р/ — порядок. Числа вида (1.3) и (1.4) равномерно распределены на числовой оси, т.е. пределы изменения значения абсолютной ошибки постоянны на всем диапазоне допустимых значений. Основные ограничения форматов (1.3) и (1.4) обусловлены следующими положениями:
— сложность выполнения немодульных операций, требующих знания позиционного значения мантиссы (ах, а2,..., а„); автор предлагает использовать для выполнения этих операций преобразование в систему счисления со смешанными основаниями;
— представление числа в форме с фиксированной точкой требует при работе с разномасштабными величинами задания большого количества модулей СОК, что приводит к увеличению объема производимых вычислений. Вещественные и рациональные числа представляются в электронной вычислительной машине (ЭВМ) в форме с плавающей точкой.
В результате этого предложенный в работе [59] подход эффективен, главным образом, при решении задач, которые требуют выполнения малого количества немодульных операций и большого количества модульных, таких как дискретное преобразование Фурье и пр.