Комплекс программ для безошибочных дробно-рациональных вычислений и его применение для решения систем линейных алгебраических уравнений Германенко Максим Игоревич

Содержание к диссертации

Введение

1. Алгоритмы и программное обеспечение безошибочных дробно рациональных операций 15

1.1. Целочисленные вычисления 17

1.1.1. Сложение неотрицательных чисел '. 18

1.1.2. Вычитание неотрицательных чисел 20

1.1.3. Сложение и вычитание целых чисел 20

1.1.4. Умножение целых чисел 22

1.1.5. Деление и остаток от деления целых чисел 25

1.1.6. Наибольший общий делитель 28

1.1.7. Класс overlong 32

1.1.8. Выводы и результаты 35

1.2. Дробно-рациональные вычисления 35

1.2.1. Оценка вычислительной и пространственной сложностей арифметических операций с рациональными числами 35

1.2.2. Класс rational 39

1.2.3. Арифметические операции с дробно-рациональными числами..41

1.2.4. Выводы и результаты 45

1.3. Матричные вычисления 46

1.3.1. Оценка вычислительной и пространственной сложностей арифметических операций с матрицами 46

1.4. Выводы 49

2. Применение безошибочных вычислений для решения линейных систем 50

2.1. Определение гарантированной оценки погрешностирешения систем линейных алгебраических уравнений, при приближенных исходных данных 52

2.2. Использование метода Жордана-Гаусса 54

2.2.1. Использование алгоритма Жордана-Гаусса для нахождения гарантированных оценок решения приближенно заданной системы линейных алгебраических уравнений 55

2.2.2. Оценка сложности определения гарантированной оценки решения приближенно заданной системы линейных алгебраических уравнений методом Жордана-Гаусса 56

2.3. Безошибочное решение систем с трехдиагональными матрицам 61

2.3.1. Метод прогонки 62

2.3.2. Оценка сложности безошибочного решения систем линейных алгебраических уравнений с трехдиагональной матрицей методом прогонки 63

2.4. Недоопределенные и переопределенные системы. Обобщенная обратная матрица 69

2.4.1. Обобщенная обратная матрица 69

2.4.2. Приложение -обратных матриц для решения систем линейных уравнений 70

2.4.3. Свойства -обратных матриц 71

2.4.4. Метод Гревилла 73

2.4.5. Оценка сложности нахождения обобщенной обратной матрицы методом Гревилла 74

2.4.6. Метод Эрмита 76

2.4.7. Оценка сложности нахождения обобщенной обратной матрицы методом Эрмита 78

2.5. Практические эксперименты 81

2.5.1. Эксперимент 1 81

2.5.2. Эксперимент 2. 81

2.6. Выводы 83

3. Программное обеспечение параллельных вычислений при решении линейных систем 85

3.1. Адаптация классов overlong и rational к MPI 86

3.2. Метод Жордана-Гаусса 90

3.2:1. Параллельный алгоритм 91

3.2.2. Ускорение параллельной реализации алгоритма Жордана-Еаусса при использовании параллельный вычислений. 94

3.2.3; Вычислительный эксперимент 95

3.3. Обобщенная обратная матрица. 98

3.3.1. Параллельный алгоритм 99

3.3.2. Коэффициент ускорения параллельной реализации алгоритма Эрмита 101

3.3.3. Вычислительный эксперимент ...103

3.4. Интернет приложения для решения линейных систем. ...103

3.5. Выводы 104

Заключение 105

Литература 107

Приложение 115

• Оценка вычислительной и пространственной сложностей арифметических операций с рациональными числами
• Оценка вычислительной и пространственной сложностей арифметических операций с матрицами
• Оценка сложности безошибочного решения систем линейных алгебраических уравнений с трехдиагональной матрицей методом прогонки
• Коэффициент ускорения параллельной реализации алгоритма Эрмита

Введение к работе

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

Некоторые методы решения данной задачи, такие как метод Гаусса, метод Жордана-Гаусса, метод прогонки, прямое использование формул Крамера и др., определены в терминах точных вычислений. Но использование стандартных типов данных известных языков программирования, существенно сужает множество рациональных чисел, представимых без погрешности. Таким образом, арифметические операции приходится выполнять приближенно, что часто дает неудовлетворительные результаты решения задач.

Интересно заметить, что в последнее время теория и практика решения плохо обусловленных линейных систем развивается в направлении разработки алгоритмов, устойчивых к погрешностям округления промежуточных результатов [5, 21, 22, 25, 31, 38, 46, 50, 74, 75]. Примерами таких методов являются: метод вращений, метод отражений и, др. Они содержат операции извлечения квадратного корня, вычисление синуса, косинуса и прочих иррациональных .функций, т.е. ориентированы на вычисления с приближенными числами. Методы, не ориентированные на безошибочные вычисления, как правило, не распознают случаи, когда система имеет бесконечное множество решений или не имеет их вообще, выдавая ошибочные ответы. При вычислениях с округлениями, возможно, что 1) не будет найдено ни одного подходящего решения, даже если оно имеется; 2) найдены корни при их отсутствии; 3) найдено только одно решение, при их бесконечном множестве. При безошибочных вычислениях все три случая легко идентифицировать.

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

Использование популярных программ, таких как MS Excel и MathCAD, приводит к получению неверного результата даже при решении систем линейных уравнений порядка 15. Кроме того, программы даже не выдают сообщения, что полученный результат может быть неверным [36, 37].

По-видимому, первый комплекс программ для безошибочных дробно- рациональных вычислений реализован в 1986 г. в Пермском государственном университете под руководством А.Н. Румянцева-[20, 28]. Однако факты массового использования данного комплекса программ для реальных вычислений не известны.

Развитие объектно-ориентированного программирования позволило пользователям, дополнить стандартные числовые типы, данных. Используя символьное программирование, японские программисты" К.Ш.Тан, В.Х.Стиб, Й.Харди [43] разработали класс, позволяющий выполнять операции со сверхдлинными числами. Данный класс основан на символьном программировании с использованием десятичной системы счисления. Для 32-битных операционных систем более рациональным является использование систем счисления с основанием 2 .

Указанного недостатка не имеет библиотека GMP [33]. Данная библиотека разработана под операционные системы Unix, Linux и подобные малопопулярные в нашей стране операционные системы, ее использование требует компиляции и дополнительных знаний, что затрудняет использование данной библиотеки для рядового программиста. Стоит также отметить, что для объектов GMP не предоставляется возможность их использования в параллельных вычислениях.

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

1. Разработка классов, обеспечивающих безошибочные дробно- рациональные и матричные вычисления.

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

3. Анализ сложности безошибочного решения систем линейных алгебраических уравнений и нахождения обобщенной* обратной: матрицы и эффективности распараллеливания.

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

Наиболее существенные результаты, полученные автором в результате исследования и выносимые на защиту, состоят в следующем:

2. Доказано, что при безошибочном решении систем линейных алгебраических уравнений методом Жордана-Гаусса пространственная битовая сложность не превышает о(/²), а вычислительная битовая сложность при использовании алгоритма умножения столбиком и быстрого алгоритма не превышает Ф⁵) ф⁵) соответственно, где I - число бит требуемых для представления исходных данных.

3. Доказано, что при безошибочном решении систем линейных алгебраических уравнений с трехдиагональной матрицей методом прогонки пространственная битовая сложность не превышает о(/^1,5), а вычислительная битовая сложность при использовании алгоритма умножения столбиком и быстрого алгоритма не превышает о(/³) и о(/^1,5) соответственно.

-83. Доказано, что при безошибочном нахождении обобщенной обратной матрицы Мура-Пенроуза методом Эрмита пространственная битовая сложность не превышает о(/⁴), а вычислительная битовая сложность при использовании алгоритма умножения столбиком* и быстрого алгоритма не превышает о(/⁷) и о(/⁵). Результаты теоретического исследования показывают возможность практического использования программы, как при анализе, так и при безошибочном решении систем линейных алгебраических уравнений.

4. Разработана библиотека классов ExactComp, в состав которой включены классы overlong, rational и matrix, расширяющие возможности безошибочных вычислений и позволяющие использовать безошибочные матричные вычисления при решении плохо обусловленных и некорректных систем линейных алгебраических уравнений в программах пользователя. Разработанные классы адаптированы для параллельных вычислений. Проведен анализ ускорения использования параллельных вычислений для решения данных задач.

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

Практическая значимость. К вычислению обобщенной обратной матрицы сводятся реальные задачи экономики, математики, физики. Представленные в работе библиотеки (свид. РОСПАТЕНТ об официальной регистрации программы для ЭВМ № 2009612777, № 990607) позволяют реализовать безошибочное решение данной задачи.

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

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

Апробация работы. Основные положения диссертации докладывались и обсуждались на следующих конференциях:

1. Международная научная конференция «Параллельные вычислительные технологии ПАВТ'2009», г. Нижний Новгород, март - апрель 2009 г.

2. Международная- научная конференция' «Параллельные вычислительные технологии ПАВТ'2008», г. Санкт-Петербург, январь - февраль 2008 г.

3'. Международная научная конференция «Параллельные вычислительные технологии ПАВТ'2007», г. Челябинск, январь - февраль 2007 г.'

1. «Третья российско-германская школа по параллельным* вычислениям на высокопроизводительных системах», г. Новосибирск, август- сентябрь 2006 г.

2. «Всероссийский конкурс студенческих работ в области естественных наук», г. Москва, декабрь 2004 г.

3. Российская молодежная научная и инженерная выставка «Шаг в будущее», г. Москва, МГТУ им. Н. Э. Баумана, апрель 2002 г.

4. Российская молодежная научная и инженерная выставка «Шаг в будущее», г. Москва, МГТУ им. Н. Э. Баумана, февраль 2001 г.

5. Седьмая научная конференция молодых исследователей «Шаг в будущее», г. Москва, МГТУ им. Н. Э. Баумана, февраль 2000 г.

9. Российская молодежная научная^и инженерная выставка «Шаг в будущее», г. Москва, МГТУ им. Н. Э. Баумана, апрель 2000 г. Кроме того, результаты работы были представлены на ежегодных научно- практических конференциях Южно-Уральского государственного? университета. Работа награждена дипломами лауреата Российских научных мероприятий:

> Диплом 1; степени по итогам 2 тура Всероссийского конкурса студенче

ских работ в области естественных наук, Саратов 2004 год.

Диплом министерства промышленности, науки; и технологий РФ за первый приз в номинации «Абсолютное первенство - лучшаяфабота в области естественных наук», Москва, МЕТУ им. Н.Э.Баумана, 2001 год.

Диплом комитета общественных и межрегиональных связей! Правительства Москвы за первый приз в номинации «Лучшая работа- в.области Естественных наук», МГТУ им. Н.Э;Баумана,.2001 год.

Основания для? выполнения работы: Гранд губернатора! Челябинской области 2004 г.

Публикации. Основные результаты диссертации опубликованы в 14 печатных работах, получены свидетельства РосАПО об официальной регистрации программы- для ЭВМ № 990607 «Класс rational» и № 2009612777 Библиотека классов «Exact Computational».

Во введении- обоснована актуальность темы диссертационной работы, проведен обзор аналогов<и описаны их недостатки, сформулирована цель работы, кратко охарактеризована научная новизна, возможности научного - и практического применения; отмечена связь проблемы с планами научных исследований. Кроме того, приведено краткое изложение материала работы по главам и параграфам.

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

Описан класс оverlong [40], который существенно расширяет логические возможности целочисленных вычислений: диапазон пред ставимых чисел расширяется до (-(2¹⁶)⁶⁵⁵³⁶, +(2¹⁶)⁶⁵⁵³⁶). Таким образом, имеется возможность представлять целые числа, имеющие более 600 ООО десятичных разрядов.

Описан класс rational [41], который дает потенциальную возможность использовать в программах пользователя безошибочное выполнение основных арифметических операций над полем рациональных чисел. По определению, тип данных rational представляет собой пару . Здесь птг - целочисленная переменная типа overlong, обозначающая числитель, a dmr - целочисленная переменная типа overlong, обозначающая знаменатель. Минимальный шаг дискретизации представляемых чисел существенно лучше, чем у стандартных типов данных и равен 2"^1048575.

Для использования классов overlong и rational достаточно подключить заголовочный файл ExactComp.h [39] в свою программу, после этого можно пользоваться объектами данных классов как объектами стандартных типов данных. Над объектами классов определены все основные арифметические операции, бинарные отношения, операторы ввода/вывода. Объем памяти, требуемый для представления объекта, зависит от значения представляемого чис-

ла. Найдены битовая пространственная и вычислительная сложности сложения и умножения матриц.

Разработанный класс matrix [37], предназначен для облегчения программирования, а также улучшений визуального восприятия программ, использующих матричные вычисления. В данный класс встроены методы решения систем линейных уравнений с заданной матрицей, нахождения обратной матрицы и нахождения обобщенной обратной матрицы. Добавлена возможность использования параллельных вычислений.

Во второй главе рассмотрен метод определения гарантированной оценки погрешности решения систем линейных алгебраических уравнений, при приближенно заданных исходных данных [27, 28].

Для безошибочного вычисления, как обратной матрицы А'¹, так и решения х можно использовать метод Жордана-Гаусса, а при использовании разработанного класса rational возможно исключить все методические погрешности.

Известно, что алгоритм Жордана-Гаусса имеет алгебраическую пространствен-

'2\ 3

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

В работе доказано, что битовая, пространственная »сложность безошибоч- *

ного решения систем линейных алгебраических уравнений' методом Жордана- Гаусса не превосходит величины о(/²), а битовая вычислительная сложность не превосходит ф⁵) , где I - число бит, требуемых,для представления исходных данных. Также доказано; что битовая- пространственная^ сложность безошибочного решения систем линейных алгебраических уравнений, методом прогонки

не превосходит величины- а битовая вычислительная-сложность не пре

восходит оН.

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

Известно множество методов нахождения »-обратной матрицы Мура- Пенроуза. Теоретический расчет битовой сложности алгоритмов- и практические эксперименты показали, что наиболее оптимальным методом для вычисления обобщенной обратной матрицы является метод Эрмита. Битовая пространственная сложность вычисления обобщенной обратной матрицы Мура-

Пенроуза методом Эрмита не превосходит величины а битовая, вычисли

тельная сложность не превосходит

Также в второй главе представлены результаты вычислительных экспериментов. Целью первого эксперимента испытать популярные программы MS Excel и MathCAD. Проведенный эксперимент показал, что использование этих программ, которыми, кстати, многие пользуются, может привести к получению неверного результата.

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

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

В третьей главе предлагается адаптация разработанных классов overlong, rational и matrix к параллельным вычислениям. При организации параллельных вычислений было принято использовать MPICH, которая поддерживает стандарт MPI и имеет GNU лицензию [40].

Теоретические исследования показали, что параллельные реализации алгоритмов Эрмита и Жордана-Гаусса при решении задач с большими матрицами позволяют увеличить скорость нахождения решения в N раз, где N - число компьютеров, а которых решается задача.

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

1. Алгоритмы и программное обеспечение безошибочных дробно рациональных операций

Обеспечение безошибочных дробно-рациональных вычислений в программах пользователя является актуальной проблемой, решением которой долгое время занимались лишь в теории. Многие реальные задачи при безошибочных вычислениях имеют простой алгоритм. В частности, для решения систем линейных алгебраических уравнений (к которым сводятся многие реальные задачи [28] экономики, физики, и других наук) можно использовать. общеизвестный алгоритм Жордана-Гаусса. Однако, при использовании стандартных типов данных число бит, используемых для? представления переменных, ограничено, следовательно,- операции придется, выполнять приближенно. Алгоритмы, определенные в терминах точных вычислений не устойчивы, к погрешностям округлений, поэтому возможны следующие пути решения:

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

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

Наиболее рациональным и наиболее перспективным является разработка программного обеспечения безошибочных вычислений. .Работу было принято начать с выбора используемой системы счисления. Системы счислений делятся на позиционные и непозиционные. Непозиционные системы [2], в свою очередь, делятся на модульные и /?-адичные. При использовании этих систем упрощается реализация арифметических операций, однако мы столкнемся с рядом проблем:

5. при изменении*длинны.числа, придется-выполнять трудоемкую операцию реконструкции;

6. сложная операция перехода к десятичной системе.

Системой счисления для реализации класса overlong [40],. обеспечивающего операции со сверхдлинными числами, была выбрана позиционная система счислениях основанием 2¹⁶. Такой выбор был сделан, потому что данная система хорошо изучена, проста для понимания, существуют алгоритмы основных арифметических операций. Для реализации этих операций будем использовать общеизвестные алгоритмы.

Для реализации безошибочных дробно-рациональных вычислений был разработан класс rational [41]. Объектами данного«класса являются*дроби, числитель и знаменатель которых — объекты класса overlong:

Аналогами классов overlong и rational являются классы very long и fraction [43], разработанными японскими программистами К. Щ. Тан, В.-Х. Сгиб, Й. Харди. Они использовали символьное программирование, т.е. позиционную систему с основанием 10, что увеличивает память,, требуемую для хранения переменных, следовательно, увеличивает времявыполнений-операций;

Возможность обеспечения безошибочных вычислений в программах пользователя; дает библиотека GMP [33]. Разработка данной библиотеки началась еще в 91-м году. Она разработана под операционные системы Unix, Linux к другие системы малопопулярные в нашей стране, Ее использование требует компиляции и дополнительных знаний, что затрудняет применение данной библиотеки для рядового программиста.

При разработке классов overlongn rational упор ставился на.простоту их использования. Для их применения достаточно подключить заголовочные файлы к программе, после этого можно пользоваться объектами данных классов как стандартными типами данных. Язык С++, который использовался для создания данных классов дает возможность переопределить арифметические операции. Таким образом использование данных классов не отличается от использования стандартных типов данных.

-171.1. Целочисленные вычисления

В этом разделе будут рассмотрены классические алгоритмы и их программные реализации следующих операций:

4. сложение и вычитание «-разрядных целых чисел с получением п- разрядного результата и разряда переноса;

5. умножение га-разрядного целого числа на /2-разрядное целое число с получением (п + га)-разрядного результата;

6. деление (« + га)-разрядного целого числа на «-разрядное целое число с получением (т + 1)-разрядного частного и «-разрядного остатка.

Эти алгоритмы можно назвать классическими, так как само слово "алгоритм" на протяжении столетий использовалось в связи с реализацией вычислительных процессов. Термин "«-разрядное целое число" означает любое неотрицательное целое число, меньшее и>", где м? есть основание обычной позиционной системы счисления, в которой представляются числа; такие числа в этой системе записываются с использованием не более чем « "разрядов".

Будем рассматривать следующие элементарные операции: 1₀) сложение и вычитание одноразрядных целых чисел с получением одноразрядного результата и разряда переноса;

2о) умножение одноразрядного целого числа на одноразрядное с получением двухразрядного результата;

Зо) деление двухразрядного целого числа на одноразрядное, которое обеспечивает получение частного как одноразрядного целого числа и одноразрядного остатка.

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


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

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

1.1.1. Сложение неотрицательных чисел

Алгоритм А (Сложение неотрицательных целых чисел) [26]. По заданным неотрицательным я-разрядным целым числам по основанию Ь (и_п_₁,...и₁,и₀)_ь и этот алгоритм формирует их сумму

(м>„, ,... м?_х, и>₀ )_ь, Здесь XV_п - разряд переноса, всегда равный 0 или 1.

А1 [Начальная установка]. Присвоить у ОД 0. (Переменная / будет пробегать позиции различных разрядов, а переменная к будет следить за переносами на каждом шаге).

А2 [Сложение разрядов]. Присвоить <г-{и_]+у_]+к}то&Ь и

АЗ [Цикл по у]. Увеличить ] на единицу. Если теперь у < п, то вернуться к шагу А2, иначе — присвоить \\>_п+— к и завершить выполнение алгоритма.

к <— + Vj + к^/к. (По индукции, распространяемой на вычисления, всегда выполняется неравенство

и_]+У;+к<(Ь-1) + (Ь-1) + 1<2Ь,

следовательно, к: присваивается значение 0 или 1 в зависимости от того, произошел (1) или не произошел (0) перенос, т. е. выполняется присвоение

С++ программа, реализующая данный алгоритм для выполнения операции сложения с объектами класса overlong, приведена на рис. 1.1.

void overlong::add(overlong а) { short unsigned *р;

int i,l,ln,lx; [=leng;

long unsigned temp;

//делаем так, чтобы первое слагаемое было больше второго слагаемого if(abs(leng) < abs(a.leng) ) { p=a.d; a.d=d; d=p; ln=abs(leng); lx=abs(a.leng); }else {

lx=abs(leng); lri=abs(a.leng);

}

temp=0; //цифра для переноса //алгоритм сложения столбиком for (i=0; icln; i++) { temp+=d[i]; temp+=a.d[i]; d[ i j=temp%UP; temp/=UP;

}

//если цифра переноса <> О if(temp) {

for( ; (i== 0); i++);

//если нужно - выделяем дополнительную память под число if(i==lx) {

p=new short unsigned[lx+1]; p[lx]=1 ;

for(int i=0;i delete[] d; d=p; Ix++;

}

}

//учитываем знак leng=(l>0)? Ix : -Ix;

}

Рис. 1.1. Программная реализация сложения неотрицательных целых чисел Время выполнения этой программы не превосходит 7 (N + 2) тактов. Задача вычитания аналогична задаче сложения, но есть и заслуживающие внимания отличия.

-201.1.2. Вычитание неотрицательных чисел

Алгоритм 8 (Вычитание неотрицательных целых чисел) [26]. По заданным неотрицательным и-разрядным целым числам по основанию Ь ,...и₁,и₀)_ь>(у_п_!,... у,, у₀ этот алгоритм находит неотрицательную разность

(Пп'Пп-Ц—Щ'ПоХ,

[Начальная установка]. Присвоить у 0, к 0.

1994. [Вычитание разрядов]. Присвоить <^(u_J-v_]+k}m.oд.b и

к 4г-(u_J-v_]+k}|k . (Другими словами, к присваивается -1 или 0 в зависимости от того, происходит ли заимствование, т.е. оказывается ли, что (м, - + А: < 0). Что

касается вычисления Wj, примем во внимание тот,факт, что должно выполняться неравенство

-Ь = 0-(Ь-1) + (-1) следовательно, 0<и_;-у^к + Ь<2Ь и это полагается в описываемой ниже

программной реализации на рис. 1.2).

1995. [Цикл по у]. Увеличить _/ на единицу. Если теперь ] < п, то вернуться к шагу 82; в противном случае завершить выполнение алгоритма. (Когда выполнение алгоритма завершается, должно получиться к = 0; условие к = -1 соответствует единственному случаю, когда (и_п__{,... м,, м₀ )_; < (у_п_, ,... V,, у₀ что противоречит сделанному раньше предположению).

С++ программа, реализующая данный алгоритм для выполнения операции вычитания с объектами класса оуег1ощ, приведена на рис. 1.2. Время выполнения этой программы также не превосходит 7 {И + 2) тактов.

1.1.3. Сложение и вычитание целых чисел

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

это возможно. Выявление используемой программы (add или sub) производится по предварительному анализу операндов. Фрагмент программы, содержащей определение операций алгебраического сложения/вычитания, приведен на рис. 1.3.

void overlong::sub(overlong а) { int I, In, j; unsigned long k; short unsigned *p;

//делаем так, чтобы из большего вычиталось меньше (знак корректируем ниже) if((*this>=a)==(*this>=-a)){ ln=abs(a.leng); Meng; } else{ p=a.d; a.d=d; d=p; l=a.leng; a.leng=leng;

" lri=abs(leng); }

//алгоритм вычитания столбиком for(int i=0;i{ if(d[i]

-221.1.4. Умножение целых чисел

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

в случае если число знаков слагаемого имеет небольшое количество знаков, около 500, тогда используем алгоритм столбиком;

если число знаков слагаемого превышает 500 знаков, тогда для умножения используем быстрый алгоритм умножения Тоома-Кука [47]. Алгоритм М (Умножение, неотрицательных целых чисел) [26]. По заданным неотрицательным т и «-разрядным целым числам по основанию Ь

(м_т_₁,...м,,м₀)_ь и (у„_₁,...у₁,у₀)_й этот алгоритм строит их произведение

(Общепринятый метод умножения при помощи карандаша и бумаги основан на нахождении сначала частичных произведений ^..и^и^хУ], 0 < у < п, а затем — суммы этих произведений, сдвинутых

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

М1 [Начальная установка]. Присвоить всем разрядам (м_п+т_₁,...м?₁,и>₀)_ь значения "нуль". Присвоить] <— 0.

М2 [Начальная установка г]. Присвоить / <— 0., к <— 0.

МЗ [Умножить и сложить]. Присвоить сначала t _ixVj + w₊j+k, а

затем - -tmodb, (Здесь разряд переноса к всегда будет

принадлежать интервалу 0 < к < Ь).

М4 [Цикл по г]. Увеличить г на единицу. Если после этого г < т, то

вернуться к шагу МЗ; в противном случае присвоить к.

М5 [Цикл по у]. Увеличить ] на единицу. Если после этого _/ < п, то вернуться к шагу М2; в. противном случае завершить выполнение алгоритма.

Два неравенства,

О <г<Ъ^г, О <к<Ь, являются 1фитическими для эффективной реализации этого алгоритма, так как они накладывают ограничения на размер регистра, необходимый для вычислений. Их можно доказать по индукции, так как если в начале шага МЗ справедливо неравенство к < Ъ, то

overlong overlong::operator+=(overlong а) {

// если 2-е слагаемое пустое - ничего не делаем if (!a.d) return *this;

//если 1-е слагаемое пустое, 1-му присваиваем 2-е if (!d) { d=a.d; leng=a.leng; a.d=0;

return *this;

}

//выполняем соответствующие действия, в зависимости от знаков операндов if((a.leng>0)==(leng>0)) add(a); else sub(a);

return *this;

overlong over)ong::operator-=(overlong a) {

//если 2-й операнд пустой - ничего не делаем

if (!a.d) return *this;

a.leng=-a.leng;

//если 1-й операнд пустой, 1-му присваиваем 2-й if (!d){ d=a.d; leng=a.leng; a.d=0;

return *this;

}

//выполняем соответствующие действия, в зависимости от знаков операндов if((a.leng>0)==(leng>0)) add(a); else sub(a);

return *this;

Рис. 1.3. Программы алгебраического сложения и вычитания

overlong overlong::operator*=(overlong a) {

//если один из операндов нулевой - результат = О if(leng==0) return *this; if(a.leng==0){ if(d) deleted; d=0; leng=0; return *this;

}

int sgn=((leng>0)==(a.leng>0));

int l=abs(leng);

int la=abs(a.leng);

int lp=l+la;

short unsigned *p;

p=new short unsigned[lp]; //выделяем память под результат for(int i=0; i]=0; //зануляем результат

for (int i=0; i{

if(a.d[i]){

long unsigned r=0, aq; //выполняем умножение for(int j=0; j{ aq=d[j]*a.d[i]+r+p[i+j]; r=aq/UP; aq%=UP; p[i+j]=(short unsigned)aq;

}

//если есть цифра переноса

if(r) {

r+=p[i+l];

p[i+l]=(short unsigned)(r%UP);

}

}

}

if(d) { delete d;

leng=0;

}

for(l=lp-1 ;(l>=0)&&(!p[l]);l--); //считаем количество цифр в результате //результат переносим в текущий объект if(l>=0) { d=new short unsigned[ 1+1 ]; for(int i=0;i<=l ;i++) d[ i ]=p[ i ]; if(p) delete[] p; leng=(sgn)?(l+1):-(l+1);

}

return *this;

Рис. 1.4. Программа умножения целых чисел

Данный алгоритм использован для реализации операции умножения объектов класса overlong. Текст программы приведен на рис. 1.4. Время выполнения программы не превосходит 30тп тактов (операций). Известно, что алгоритм М- не самый быстрый способ умножения, если множители тип велики, хотя он имеет преимущество - простоту. Существуют более быстрые алгоритмы умножения и деления [45, 49, 52, 54, 59, 61, 62, 63, 64, 69], но в данной работе они не рассматриваются.

1.1.5. Деление и остаток от деления целых чисел

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

Самый беглый анализ обычного процесса деления в столбик показывает, что вся задача разбивается на более простые шаги, каждый из которых состоит в делении (п + 1)-разрядного числа и на «-разрядное число v, где 0 < u/v < b. Остаток г после выполнения каждого шага меньше v, поэтому величину rb+ (следующий разряд делителя) можно использовать как новое число и на следующем шаге. Таким образом, поиски подходящего алгоритма деления сводятся к следующей задаче:

Пусть (м_т+л-1>---^и1>^мо)г> ^и (^vi-i' * ^vi' ^vo\ ~ представленные по основанию b неотрицательные целые числа, такие, что u/v < b. Найти алгоритм для определения числа q = [и/vJ .

Можно заметить, что условие u/v < b равносильно условию u/b < v. Так что u/v < v - это просто условие (и_п,и_п__v...u_x)_b <(v„_₁,v„_₂,...v₁,v₀)_i). Далее, если

записать г = и - qv, искомое число q будет единственным целым числом, таким, что 0 < г < V.

Наиболее простой подход к решению поставленной задачи состоит в том, чтобы высказать какую-нибудь догадку относительно величины q, основываясь на наиболее значимых разрядах и и v. Введем новый параметр

Согласно этой- формуле q получается делением двух первых значащих разрядов числа и на первый значащий разряд числа-v. Если результат равен b или больше Ь, заменяем его на >-1.

Примечательно, что q всегда оказывается очень хорошим приближением к искомому ответу q, если только v„-l относительно велико. В частности имеет место следующая теорема.

Теорема [26]. Если v„_, >|J?/2J,to q-2.

Наиболее важным моментом этой теоремы является то, что постулируемое в теореме выражение не зависит от Ъ. Не важно, насколько велико Ь, пробное частное q никогда не отличается от истинного более чем на 2.

Условие v„_, >[ЬИ\ очень похоже на условие*нормализации; действительно, оно в точности совпадает с условием нормализации для двоичных компьютеров. Один из простых способов обеспечения достаточно большого значения* v_n_j умножить оба числа и и v на [_Z?/(v„_! + 1)J. Это не изменит значения u/v, не увеличит количество разрядов в и и v, и всегда приведет к достаточно большому новому значению v_n-1.

Данные результаты используются в приведенном ниже алгоритме D. В нем на шаге D3 используется несколько усовершенствованный способ выбора числа q, гарантирующий, что q = q или q-1. На практике этот улучшенный метод выбора числа q почти всегда дает точное решение

Алгоритм D (Деление неотрицательных целых чисел) [26]. По данным неотрицательным целым числам (u_m+n__l,...u_l,u₀)_b и (v_{n l},... v,, v₀ , представленным по основанию^, в предположении, что v„_, и п > 1, находим в системе счисления по основанию Ь частное [и / V ] = (д_п__г, , , и остаток ишоду = (г„_₁,г„_₂,.-.,г₀)_й.

Б1 [Нормализация]. Присвоить й <г-[Ь1^_п__х+1)\. Затем присвоить (^ии+_и»^ит+_л-р—»^и1»^иоХ значение , умноженное на ± Точно

так присвоить ,---,у,,у₀)_й значение , ,у,,у₀, умноженное на с1. Т)2 [Начальная установка Д. Присвоить 7 <- га.

ЮЗ [Вычислить д]. Присвоить ч ^{{и^Ь+и^^)Iи пусть г - остаток, т.е. г = (и_]+пЬ + и_]+п_₁)тод.у_п_₁. Проверить выполнение отношений д=Ь, и 2 ^>Ь-г + и^_п_₂. Если оно удовлетворяется, то уменьшить д на 1, увеличить г на у„_! и повторить эту проверку при г<Ь.

04 [Умножить и вычесть]. Заменить (и^_п,и_]+п_₁,---,и_]}_ь на

Этот шаг (аналогичный шагам МЗ-М5 алгоритма М) состоит из простой операции умножения на одноразрядное число, скомбинированной с вычитанием. Значения разрядов ("_,+„>«,+„_!>"'»и.,^ всегда должны быть положительными; если на этом шаге получен отрицательный результат, то в качестве истинного результата должно остаться («,+„>«,+„_!>плюс Ь^п+Х , а именно представление истинного значения в виде дополнения до Ь, причем следует запомнить "заимствование" слева, из старшего разряда.

Б5 [Проверка остатка]. Присвоить Если результат шага был

отрицательным, перейти к шагу Б6; в противном случае перейти к шагу Б7. Б6 [Компенсировать сложение]. Уменьшить на 1 и добавить

(у^-.-УрУо^ к {и_]+п,и ,и^ (При этом произойдет перенос в разряд, находящийся слева от и_]+п, но им следует пренебречь, так как перенос погашается "заимствованием" из того же разряда, произведенным на шаге 04.)

D7 [Цикл по/]. Уменьшить/на единицу. Если теперь./ > О, то вернуться к шагу D3.

D8 [Денормализация]. Теперь (q„-i,q_n-₂>"'>4о)_ь есть искомое частное, а для получения искомого остатка достаточно («„_!»»разделить на d.

Данный алгоритм использован для реализации операции деления объектов классаoverlong. Текст программы приведен на рис. 1.5;

Обратите внимание, как легко реализуются в машине казавшиеся довольно сложными вычисления и выбор вариантов на шаге D3. Отметим также, что программа для выполнения шага D4 аналогичная программе М с той лишь оговоркой; что здесь применяются еще и идеи программы S.

Для оценки времени выполнения программы D следует рассмотреть значения параметров М, N, Е, К и К', представленных в программе. Здесь М + 1 - количество слов в частном, iV — количество слов в делителе, Е — число, показывающее, сколько раз ^ уменьшается на шаге D3, iК + К' приблизительно равно (N+l) (М+1) и что Е приблизительно равно М, можно получить, что общее время выполнения программы приблизительно равно 37МДГ+ 3(W + 89М+ 111 тактов плюс дополнительно 67iV + 235М + 4 тактов, если d > 1. При больших Ми N это время практически равно времени, которое потребуется программе М, чтобы перемножить частное и делитель.

1.1.6. Наибольший общий делитель

Если числа м и v.целые, такие, что одно из них не равно нулю, то говорят, что их наибольший общий; делитель, gcd(w,v), есть наибольшее целое число, на которое числа и и v делятся без остатка. Данное определение имеет смысл, так как если и Ф 0 , то самым большим числом, на которое число и делится без остатка, является |и|. Но числа и и v делятся также на целое число 1, следовательно, должно существовать самое большое число, на которое делятся оба эти числа. Когда оба числа и и v равны нулю, то нуль делится


нацело на любое .целре число, так что выше определение к этому случаю неприменимо.

overlong overlong::div(overlong а) {

int j.sign;

short unsigned *p, b; long unsigned k, qq; overlong q;

// Нормализация sign=((a.leng>=0)!=(leng>=0)); a=abs(a); leng=abs(leng); k=1+a.d[a.leng-1]; b=(short unsigned)(UP/k); a*=b; k=0; p=d;

d=new short unsigned[leng+1];

for(int i=0; i

}

if (p) delete p;

d[leng++]=(short unsigned)k; q.leng=leng-a.leng; q.d=new short unsigned [q.leng]; int m;

for =q.leng-1, m=Ieng-1; j>=0; j~, m--){

//Находим приближение q[j] if (d[m]==a.d[a.leng-1 ]) qq=UP-1; else {

qq=UP; qq*=d[m]; qq+=d[m-1]; qq/=a.d[a.leng-1]; qq++; long unsigned I, r;

do {

qq--;

l=qq*a.d[a.leng-2]; r=(d[m]*UP+d[m-1] -

qq*a.d[a.leng-1]); if (r>=UP) break; r*=UP; r+=d[m-2]; } while (l>r);

}

} //else

// Найдем-j-ю цифру q[j] long unsigned r=0, aq;

for (int i=0; ka.leng; i++) {

aq=qq*a.d[i]+r; r=aq/UP; aq%=UP;

if (d[j+i]<(short unsigned)aq){ int n=j+i+1;

whilef (d[n]==0)&&(n

d[n++]=UP-1; d[n]--;

long unsigned k=UP+d[j+i]; k-= aq;

d[j+i]=(short unsigned)k;

}

else d[j+i]-=aq;

} //fori

d[m]-=r; if (d[m]) {

qq--;

r=0;

for (int i=0; ka.leng; i++) {. aq=r+a.d[i]+d[i+j]; if(aqelse {d[i+j]=aq-UP; r=1;};

}

d[m]=0; } //if q.dQ]=qq;

if (sign) q.leng=-q.leng; //вычисляем кол-о цифр результата for(j=abs(leng)-1; j>=0; j-) if(d[j]) break;

IfO=-1) {

leng=0; delete[] d; d=NULL; } else div(b);

return q;

Рис. 1.5. Программа деления целых чисел

Условимся считать

gcd(0,0) = 0.

Из введенных выше определений очевидным образом следует, что

gcd(w, v) = gcd(v, и). (l.l)

gcd (и, v) = gcd(- и, v). (1.2)

gcd(w,0) = |и|.

Понятие наибольшего общего делителя gcd(«, v) имеет важное значение и заслуживает тщательного изучения, поскольку к ней сводится задача представления рационального числа с минимальными членами.

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

1сш(м, v). Оно определяется как наименьшее положительное целое число, кратное как и, так и v. 1cm (и, 0)= lcm(0,v)= 0 . Классический метод обучения

детей сложению дробей -т ^{+ _}т состоит в том, чтобы научить их находить

"наименьший общий знаменатель", т. е. lcm^w^v¹).

Легко получить ряд основных тождеств, относящихся к наибольшему общему делителю и наименьшему общему кратному:

gcd (и, v)w = gcd(ww, vw) при w > 0; 1ст(и,у) w = 1cm(mw, vw) npuw> 0;

M-v = gcd(M,v)-lcm(i/,v) npuw> 0; (1.3)

gcd(l cm (и, v), 1cm (u,w)) = lcm (и, gcd (v, w)); (1.4)

lern (gcd (и, v), gcd (и, w)) = gcd (и, lcm (v, w)). (1.5)

Два последних равенства (1.3) и (1.4) являются аналогами "дистрибутивного закона" uv + uw = u(v + w). Соотношение (1.5) сводит вычисление gcd(w,v) к вычислению lcm(w,v) и наоборот. Наибольший общий делитель двух целых чисел может быть эффективно найден без разложения чисел на простые множители. Такой метод был открыт более 2 250 лет тому назад - это алгоритм Евклида.

Алгоритм Е (Алгоритм Евклида в современной редакции). По данным неотрицательным целым числам и и v: и этот алгоритм находит их наибольший общий делитель. (Замечание. Наибольший общий делитель произвольных целых чисел и к v можно получить с учетом соотношений (1.1) и (1.2), применив алгоритм к |m|,|v|.)

El. [v = 0?]. Если V = 0, то выполнение алгоритма заканчивается, а в качестве результата возвращается число и.

Е2. [Взять и mod v]. Присвоить г <— и mod v; и <— v; v <- г и вернуться к шагу AI. (В результате выполняемых на этом шаге операций значение v уменьшается, значение gcd(w,v) остается неизменным).

Данный алгоритм использован для реализации основных арифметических операций с объектами класса rational. Текст программы приведен на рис. 1.6.

Сложность вычисления значения gcd(u,v) не превосходит величины (MN). Здесь M,N- количества слов в переменных и и v.

Бинарный метод. После стольких столетий применения почтенного алгоритма Евклида несколько неожиданным оказалось то, что он не всегда является лучшим способом определения наибольшего общего делителя. В 1961 году Джозеф Стейн (Josef Stein) предложил совершенно другой алгоритм нахождения наибольшего общего делителя, ориентированный, прежде всего, на двоичную арифметику. Этому новому алгоритму совершенно не нужны команды, выполняющие операции деления. Основанный исключительно на операциях вычитания, он проверяет, четно ли число, и делит пополам четные числа (что соответствует в двоичной арифметике сдвигу вправо). При реализации бинарного алгоритма нахождения наибольшего общего делителя для сверхдлинных чисел мы столкнемся со следующими проблемами:

overlong nod(overlong с, overlong d) { overlong f,zero; c=abs(c); d=abs(d);

if (c else { f=d; d=c;

}

while (f!=zero){ d%=f;

c=d; d=f; f=c;

}

return d;

Рис. 1.6. Программы нахождения gcd

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

большое количество бит, следовательно, большое число повторений основного цикла алгоритма.

Поэтому было принято решение для нахождения наибольшего общего делителя использовать алгоритм Эвклида.

1.1.7. Класс overlong

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

В работе предлагается тип данных overlong [40] для языка С++. Возможности разработанного типа данных показаны в таблице 1.1.

Как видно из таблицы, разработанный тип данных существенно расширяет логические возможности целочисленных вычислений: диапазон представи- мых чисел расширяется до (_(2¹⁶)⁶⁵⁵³⁶, +(2¹⁶)⁶⁵⁵³⁶). Таким образом, имеется возможность представлять целые числа, имеющие более 600 ООО десятичных разрядов.

Таблица 1.1. Возможности класса overlong

По определению, тип данных огег1оп представляет пару <1,й>, где I - целочисленная переменная, (I - переменная типа указатель на машинное слово. Знак переменной / определяет знак переменной типа оуег1ощ. Абсолютная величина переменной I определяет число машинных слов, выделенных под указатель <1 для представления переменной типа о\ег1оп%. Важно отметить, что объекты типа оуеНощ являются динамическими. Значения переменных / и й в ходе выполнения программы автоматически переопределяются конструктором копирования в соответствии с условием минимизации используемой объектом памяти. Фрагмент текста программы, содержащий определение данного класса, приведен на рис. 1.7.

Членами класса являются конструктор по умолчанию, конструктор копирования, деструктор и операторы присваивания, а также некоторые скрытые члены. Друзьями класса являются арифметические операции, бинарные отношения, операторы работы с потоками ввода/вывода. Это позволяет операторам, не являясь членами класса, использовать скрытые поля класса.

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

#define UP 0x1 OOOOul //основание системы счисления #define MAXSTR 1024 #define ERR_SMALLBUFF -1 class overlong {

short unsigned * d; //указатель на массив

int leng; //дилна массива

void add(const overlong&);

void sub(const overlong&);

short unsigned div(short unsigned );

void div(overlong);

void mod(overlong a);

short nsd(void) const; //кол-во значимых цифр

public:

//упаковка и распаковка для MPI

int packed_size() {return abs(leng) * sizeof(unsigned short) + sizeof(int);} int pack(void *buff, int sizeofbuff); int unpack(void *buff);

//конструкторы и деструкторы

overlong(); //конструктор по умолчанию

~overlong(); //деструктор

overlong(const overlong & b); //конструктор копирования

overlong(long);

overlong(long unsigned);

overlong(char *);

//операторы преобразования operator long(); operator long unsigned (); operator double();

//унарные операторы

const overlong& operator=(long);

//бинарные сравнения

friend int operator >(const overlong& a,const overlong& b);

//бинарные операторы //бинарное сравнение

friend overlong operator+(const overlong& Jong unsigned );

//операторы вывода

friend ostream& operator«(ostream&, overlong ); friend istream& operator»(istream&, overlong&);

friend overlong nod(overlong, overlong);

Рис. 1.7. Определение класса overlong

Все операции при использовании класса overlong остаются полиморфными и допускают смешивание типов. В частности, возможны следующие случаи:

оба операнда имеют тип overlong',

один из операндов имеет тип long, а другой overlong;

один из операндов имеет тип unsigned long, а другой overlong',

один из операндов имеет тип int, а другой overlong',

один из операндов имеет тип unsigned int, а другой overlong.

Над объектами класса также определены бинарные отношения >, с, >=, <=, !=, = =, возвращающие в качестве результата сравнения 1 в случае ИСТИНЫ и 0 в противном случае. Этот механизм был разработан для обеспечения совместимости с ранними версиями языка С++.

1.1.8. Выводы и результаты

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

1.2. Дробно-рациональные вычисления

Оценка вычислительной и пространственной сложностей арифметических операций с рациональными числами

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

Практическая значимость. К вычислению обобщенной обратной матрицы сводятся реальные задачи экономики, математики, физики. Представленные в работе библиотеки (свид. РОСПАТЕНТ об официальной регистрации программы для ЭВМ № 2009612777, № 990607) позволяют реализовать безошибочное решение данной задачи.

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

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

Апробация работы. Основные положения диссертации докладывались и обсуждались на следующих конференциях: 1. Международная научная конференция «Параллельные вычислительные технологии ПАВТ 2009», г. Нижний Новгород, март - апрель 2009 г. 2. Международная- научная конференция «Параллельные вычислительные технологии ПАВТ 2008», г. Санкт-Петербург, январь - февраль 2008 г. 3 . Международная научная конференция «Параллельные вычислительные технологии ПАВТ 2007», г. Челябинск, январь - февраль 2007 г. 4. «Третья российско-германская школа по параллельным вычислениям на высокопроизводительных системах», г. Новосибирск, август- сентябрь 2006 г. 5. «Всероссийский конкурс студенческих работ в области естественных наук», г. Москва, декабрь 2004 г. 6. Российская молодежная научная и инженерная выставка «Шаг в будущее», г. Москва, МГТУ им. Н. Э. Баумана, апрель 2002 г. 7. Российская молодежная научная и инженерная выставка «Шаг в будущее», г. Москва, МГТУ им. Н. Э. Баумана, февраль 2001 г. 8. Седьмая научная конференция молодых исследователей «Шаг в будущее», г. Москва, МГТУ им. Н. Э. Баумана, февраль 2000 г. 9. Российская молодежная научная и инженерная выставка «Шаг в будущее», г. Москва, МГТУ им. Н. Э. Баумана, апрель 2000 г. Кроме того, результаты работы были представлены на ежегодных научно- практических конференциях Южно-Уральского государственного? университета. Работа награждена дипломами лауреата Российских научных мероприятий: Диплом 1; степени по итогам 2 тура Всероссийского конкурса студенче ских работ в области естественных наук, Саратов 2004 год. Диплом министерства промышленности, науки; и технологий РФ за первый приз в номинации «Абсолютное первенство - лучшаяфабота в области естественных наук», Москва, МЕТУ им. Н.Э.Баумана, 2001 год. Диплом комитета общественных и межрегиональных связей! Правительства Москвы за первый приз в номинации «Лучшая работа- в.области Естественных наук», МГТУ им. Н.Э;Баумана,.2001 год. Основания для? выполнения работы: Гранд губернатора! Челябинской области 2004 г. Публикации. Основные результаты диссертации опубликованы в 14 печатных работах, получены свидетельства РосАПО об официальной регистрации программы- для ЭВМ № 990607 «Класс rational» и № 2009612777 Библиотека классов «Exact Computational». Во введении- обоснована актуальность темы диссертационной работы, проведен обзор аналогов и описаны их недостатки, сформулирована цель работы, кратко охарактеризована научная новизна, возможности научного - и практического применения; отмечена связь проблемы с планами научных исследований. Кроме того, приведено краткое изложение материала работы по главам и параграфам. В первой главе произведен обзор алгоритмов основных арифметических операций для целочисленных вычислений. Описан класс оverlong [40], который существенно расширяет логические возможности целочисленных вычислений: диапазон пред ставимых чисел расширяется до (-(216)65536, +(216)65536). Таким образом, имеется возможность представлять целые числа, имеющие более 600 ООО десятичных разрядов. Описан класс rational [41], который дает потенциальную возможность использовать в программах пользователя безошибочное выполнение основных арифметических операций над полем рациональных чисел. По определению, тип данных rational представляет собой пару nmr, dmr . Здесь птг - целочисленная переменная типа overlong, обозначающая числитель, a dmr - целочисленная переменная типа overlong, обозначающая знаменатель. Минимальный шаг дискретизации представляемых чисел существенно лучше, чем у стандартных типов данных и равен 2"1048575. Для использования классов overlong и rational достаточно подключить заголовочный файл ExactComp.h [39] в свою программу, после этого можно пользоваться объектами данных классов как объектами стандартных типов данных. Над объектами классов определены все основные арифметические операции, бинарные отношения, операторы ввода/вывода. Объем памяти, требуемый для представления объекта, зависит от значения представляемого числа. Найдены битовая пространственная и вычислительная сложности сложения и умножения матриц. Разработанный класс matrix [37], предназначен для облегчения программирования, а также улучшений визуального восприятия программ, использующих матричные вычисления. В данный класс встроены методы решения систем линейных уравнений с заданной матрицей, нахождения обратной матрицы и нахождения обобщенной обратной матрицы. Добавлена возможность использования параллельных вычислений. Во второй главе рассмотрен метод определения гарантированной оценки погрешности решения систем линейных алгебраических уравнений, при приближенно заданных исходных данных [27, 28].

Оценка вычислительной и пространственной сложностей арифметических операций с матрицами

Аналогами классов overlong и rational являются классы verylong и fraction, разработанными японскими программистами К. Ш. Тан, В.-Х. Стиб, Й. Харди. Они использовали позиционную систему счислений с основанием 10, что увеличивает память, требуемую для хранения переменных, следовательно, увеличивает время выполнений операций.

Использование программ, таких как MathCAD, которая ориентированна не безошибочные вычисления, возможно только при решении небольших задач, так как их разрядность очень ограничена. Кроме того, программы даже не выдают сообщения, что полученный результат может быть неверным.

Возможность обеспечения безошибочных вычислений в программах пользователя дает библиотека GMP [33]. Разработка данной библиотеки началась еще в 91-м году. Она разработана под операционные системы Unix, Linux и другие системы малопопулярные в нашей стране, Ее использование требует компиляции и дополнительных знаний, что затрудняет применение данной библиотеки для рядового программиста. При разработке классов overlong и rational упор ставился на простоту их использования. Для их применения достаточно подключить заголовочные файлы к программе. Объекты данных классов представляют числа, как цифры в системе счисления с основанием 216.

Применение безошибочных вычислений для решения линейных систем Задача решения систем линейных алгебраических уравнений возникает при решении краевых задач для дифференциальных и интегральных уравнений, к которым сводятся реальные проблемы экономики, физики, техники, математики [5, 6, 17, 28] и др. Матрицы системы, полученные в этом случае, как правило, являются плохообусловленными, поэтому даже незначительное изменение исходных или промежуточных данных приведет к сильному росту погрешности результата.

Методы, устойчивые к погрешностям округления промежуточных результатов содержат иррациональные функции [56, 68, 73], то есть, ориентированы на вычисления с промежуточными числами. Методы не ориентированные - на безошибочные вычисления, как правило, не распознают случаи, когда система не имеет решений или имеет их бесконечное множество, выдавая ошибочные ответы.

Известно, что алгоритм Жордана-Гаусса имеет алгебраическую пространственную сложность 0{п2) и алгебраическую вычислительную сложность о0(п ). Не трудно заметить, что данные оценки алгебраической сложности позволяют оценить требуемые для решения вычислительные ресурсы лишь при использовании переменных с фиксированным числом разрядов. Но именно это и приводит к необходимости округлений, т.е. к приближенным вычислениям.

Разработанные классы overlong и rational дают возможность использовать в программах пользователя безошибочное выполнение основных арифметических операций над полем рациональных чисел. Заметим, что общеизвестные алгоритм Жордана-Гаусса для преобразования данных использует только основные арифметические операции, следовательно, при использовании в нем разработанных типов данных будут исключены все возможные методические погрешности решения (так как все промежуточные операции будут выполняться точно, без округлений), останутся только погрешности, обусловленные неточностью исходных данных. При решении практических задач элементы матрицы системы, как правило, получаются в результате измерений или вычислений иррациональных функций, то есть, заданы с некоторым известным приближением. Используя теорему об обратном операторе [27], возможно выяснить, имеет ли система с приближенно заданной матрицей единственное решение и найти оценку существующего решения.

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

При работе со статистическими данными, как правило, возникают системы, которые не имеют решения, в обычном смысле слова (количество строк исходной матрицы больше количества переменных или количество переменных больше количества строк исходной матрицы). В этом случае нужно искать нормальное псевдорешение системы т.е. Известно, что решение задачи (2.1) может быть представлено в виде — обобщенная обратная матрица, называемая также матрицей Мура-Пенроуза. Для нахождения обобщенной обратной матрицы в диссертации реализован алгоритм Эрмита. Для его корректной работы так же необходимо использовать безошибочные вычисления.

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

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

Узкими местами в используемом кластере является плохое сетевое оборудование (сетевые карты и коммутатор), а также малое количество оперативной памяти. В качестве операционной системы кластера используется Gentoo GNU/Linux, т.к. данный дистрибутив характеризуется максимальной гибкостью, конфигурируемостью и возможностью оптимизации. Все программные средства компилировались из исходных текстов с максимальной безопасной оптимизацией. Набор установленного программного обеспечения продиктован выбранным стандартом для организации распределенных вычислений MPI (Message Passing Interface). Данный стандарт является основным для большинства существующих кластеров, т.к. предоставляет программисту удобный набор функций (с помощью которых можно осуществлять контроль передачи на низком уровне) и позволяет добиваться высокой производительности программ. В связи с большим разнообразием типов компьютеров в области параллельных вычислений и обилием специфического программного обеспечения стандарт MPI вводит собственную синхронизирующую переменную, позволяющую одновременно работать различным библиотекам интерфейса. Для Linux существует свободно распространяемый пакет MPICH, в котором содержится реализация библиотеки MPI, а также утилиты необходимые для компиляции и запуска программ. Для функционирования среды MPI также был настроен механизм совместного использования дискового пространства NFS (network file system) и механизм удаленного взаимодействия {OPENSSU). В качестве компилятора можно использовать стандартный GNU компилятор GCC 4.1.1 или ICC 9.1.43 (Intel c++ compiler). В качестве отладчика установлены VALGRIND и GDB.

На узлах кластера присутствуют только средства необходимые для функционирования среды MPI. На основном узле установлены оконные менеджеры XFCE4 и GNOME, а также другие пакеты необходимые для написания, отладки и запуска программ.

Для апробации разработанного программного обеспечения и анализа практической достижимости полученных оценок вычислительной сложности был проведен вычислительный эксперимент. Эксперимент состоял в решении систем линейных алгебраических уравнений Ах = Ь, где А = [l/(z + j + 1)]" 0 — матрица Гильберта, Ъ = [l].=Q. Результаты вычислительного эксперимента приведены в таблицах 3.4 и 3.5, а также на рис. 3.7. Прочерки в таблицах соответствуют задачам, для которых вычислительный эксперимент не проводился.

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

Построить квадратную матрицу М = (аА f. Построение матрицы М сводится к двум умножениям матриц, эта задача является стандартной при линейном программировании, а при использовании модифицированных классов overlong (рис. 3.1) и rational (рис. 3.2), реализация данного пункта не составит особого труда. 2. Методом Жордана-Гаусса провести диагональную редукцию, в результате матрица ME после выполнения метода Жордана-Гаусса будет ЕХЕ2. Реализация безошибочного решения систем линейных уравнений методом Жордана-Гаусса описана выше. 3. Найти матрицу перестановок столбцов методом Жордана-Гаусса (матрица Е[Е после выполнения алгоритма Жордана-Гаусса будет ЕЕ3; Еъ - матрица перестановок столбцов). Реализация безошибочного решения систем линейных уравнений методом Жордана-Гаусса описана выше. 4. Вычислить обобщенную обратную матрицу по формуле А = А Е3 Е2АА . При умножении Еъ Е2 нам понадобятся только первые п столбцов матрицы Еъ и первые га строк в матрице Е2, где т - ранг матрицы Ех. Выполнение этого пункта сводится к реализации четырех умножений, а, как говорилось выше, с учетом изменений, внесенных в классы, это не составит особого труда. Известны реализации параллельных алгоритмов умножения матриц и метода Жордана-Гаусса. Используя разработанные классы overlong и rational в этих реализациях можно выполнять все операции точно, не задумываясь о длине передаваемых операндов. Метод Эрмита использует умножение матриц и диагональную редукцию, которая выполняется методом Жордана-Гаусса. Следовательно, не составит труда написать его программную реализацию.

Коэффициент ускорения параллельной реализации алгоритма Эрмита

Описан класс rational [41], который дает потенциальную возможность использовать в программах пользователя безошибочное выполнение основных арифметических операций над полем рациональных чисел. По определению, тип данных rational представляет собой пару nmr, dmr . Здесь птг - целочисленная переменная типа overlong, обозначающая числитель, a dmr - целочисленная переменная типа overlong, обозначающая знаменатель. Минимальный шаг дискретизации представляемых чисел существенно лучше, чем у стандартных типов данных и равен 2"1048575.

Для использования классов overlong и rational достаточно подключить заголовочный файл ExactComp.h [39] в свою программу, после этого можно пользоваться объектами данных классов как объектами стандартных типов данных. Над объектами классов определены все основные арифметические операции, бинарные отношения, операторы ввода/вывода. Объем памяти, требуемый для представления объекта, зависит от значения представляемого числа. Найдены битовая пространственная и вычислительная сложности сложения и умножения матриц.

Разработанный класс matrix [37], предназначен для облегчения программирования, а также улучшений визуального восприятия программ, использующих матричные вычисления. В данный класс встроены методы решения систем линейных уравнений с заданной матрицей, нахождения обратной матрицы и нахождения обобщенной обратной матрицы. Добавлена возможность использования параллельных вычислений.

Во второй главе рассмотрен метод определения гарантированной оценки погрешности решения систем линейных алгебраических уравнений, при приближенно заданных исходных данных [27, 28].

Для безошибочного вычисления, как обратной матрицы А 1, так и решения х можно использовать метод Жордана-Гаусса, а при использовании разработанного класса rational возможно исключить все методические погрешности. Известно, что алгоритм Жордана-Гаусса имеет алгебраическую пространственную сложность 0(п ) и алгебраическую вычислительную сложность 0(п ). Данные оценки позволяют определить количество переменных, требуемых для решения задачи и количество арифметических операций с этими переменными. При использовании безошибочных вычислений длина переменной зависит от представляемого ей значения, следовательно, количество переменных не позволяет оценить ресурсы, необходимые для нахождения, результата. Для практического использования алгоритма требуется определить количество бит, требуемых для нахождения результата, а также количество, операций с битами. В работе доказано, что битовая, пространственная »сложность безошибоч- ного решения систем линейных алгебраических уравнений методом Жордана- Гаусса не превосходит величины о(/2), а битовая вычислительная сложность не превосходит ф5) , где I - число бит, требуемых,для представления исходных данных. Также доказано; что битовая- пространственная сложность безошибочного решения систем линейных алгебраических уравнений, методом прогонки не превосходит величины- а битовая вычислительная-сложность не пре восходит оН. При решении практических задач бывают случаи, когда система уравнений бывает недоопределенной- или переопределенной. При решении таких некорректно поставленных задач используется понятие нормального псевдорешения. Для его нахождения можно использовать обобщенную обратную» матрицу, называемую также »-обратной. Известно множество методов нахождения »-обратной матрицы Мура- Пенроуза. Теоретический расчет битовой сложности алгоритмов- и практические эксперименты показали, что наиболее оптимальным методом для вычисления обобщенной обратной матрицы является метод Эрмита. Битовая пространственная сложность вычисления обобщенной обратной матрицы Мура-Пенроуза методом Эрмита не превосходит величины а битовая, вычисли тельная сложность не превосходит Также в второй главе представлены результаты вычислительных экспериментов. Целью первого эксперимента испытать популярные программы MS Excel и MathCAD. Проведенный эксперимент показал, что использование этих программ, которыми, кстати, многие пользуются, может привести к получению неверного результата.

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

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

В третьей главе предлагается адаптация разработанных классов overlong, rational и matrix к параллельным вычислениям. При организации параллельных вычислений было принято использовать MPICH, которая поддерживает стандарт MPI и имеет GNU лицензию [40].

Теоретические исследования показали, что параллельные реализации алгоритмов Эрмита и Жордана-Гаусса при решении задач с большими матрицами позволяют увеличить скорость нахождения решения в N раз, где N - число компьютеров, а которых решается задача.

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

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



Алгоритмы и программы вычисления инволютивных базисов и их применение для решения систем нелинейных алгебраических уравнений Янович Денис Александрович



Разработка методов и комплекса программ безошибочных вычислений для решения плохо обусловленных систем линейных алгебраических уравнений Кинцель Дмитрий Александрович



Разработка, обоснование и тестирование геометрических методов решения систем уравнений с применением современных компьютерных технологийФомочкина Анастасия Сергеевна



Применение уравнений в свертках к решению обратных задач гравиметрии и идентификации динамических системМойко Наталья Валентиновна



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

Ненулевые периодические решения систем дифференциальных уравненийЛискина, Екатерина Юрьевна



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

Метод решения системы релятивистских уравнений хартри-фока для статистического ансамбля ионов плазмыДенисов, Олег Борисович

Построение дискретных аналогов и разработка методов решения конечноэлементных систем уравнений при моделировании гармонических электромагнитных полейДомников, Петр Александрович



Алгоритмы и программное обеспечение для решения систем линейных алгебраических уравнений при анализе электромагнитного излучения проводных структурКуксенко Сергей Петрович