Кафедра: «Высшая математика»
|
Скачать 262.97 Kb.
|
|
Санкт – Петербургский Государственный Университет Точной Механики и Оптики. Кафедра: «Высшая математика» Бакалаврская работа. Анализ алгоритмов умножения чисел неограниченной разрядности. Студент: Кирильчук В.Е. Научный руководитель: Кубенский А.А. Санкт-Петербург -2010- Содержание Введение……………………………………………………………………………………………………………….8 1.Цели и задачи…………………………………………………………….……………………………………..10 2.Представление чисел неограниченной разрядности………………………………………11 3.Реализация чисел неограниченной разрядности в Java..………………………………..12 4.Обзор существующих библиотек……………………………………………………………………..16 4.1 The GNU Multiple Precision Arithmetic Library………………………………………16 4.2 FXT………………………………………………………………………………………………………….17 4.3 Arbitrary Precision Arithmetic Package…………………………………………………..17 4.4 Вывод…………………………………………………………………………………………………….18 5.Выбранные алгоритмы….………………………………………………………………………………….19 5.1 Алгоритм умножения “в столбик”……………………………………………….……….19 5.2 Алгоритм Карацубы…………………………………………………………………….…….….19 5.3 Алгоритм Toom-Cook 3-way…………………………………………………………….……22 5.4 Алгоритм с использованием БПФ………………………………………………….…….26 5.5 Алгоритм с использованием БПХ………………………………….………………….….28 6.Результаты работы…………………………………………………………………………………………….30 6.1 Выбор оптимальных параметров…………………………………………………………30 6.2 Эффективность полученной операции умножения…………………………….35 6.3 Заключение……………………….…………………………………………………………….…….37 Список литературы……………………………………………………………………………………………….38 Приложения………………………………………………………………………………………………………….39 ВВЕДЕНИЕ В вычислительной технике существует такое понятие, как “длинная арифметика” – операции над числами, разрядность которых превышает длину машинного слова данной вычислительной машины. Частный случай – арифметика произвольной точности – относится к арифметике, в которой длина чисел ограничена только объёмом доступной памяти. Такие числа в данной работе будут называться числами неограниченной разрядности. История чисел неограниченной разрядности берёт своё начало с компьютера IBM 1620, анонсированного IBM в 1959 году. Этот компьютер выполнял целочисленные операции над строками (состоящими из цифр), длина которых была ограничена только объёмом доступной памяти. В то время пределом стала длина в 60 000 десятичных знаков. Однако ранняя программная реализация чисел неограниченной разрядности связана с языком программирования Maclisp, появившимся в 70-х годах и являющегося диалектом языка Lisp. Для чего же используется арифметика произвольной точности? Самое простое применение это, конечно же, математическое и финансовое программное обеспечение, требующее, чтобы результат вычисления на компьютере совпадал до последнего разряда с результатом вычисления на бумаге. Однако наиболее интересны всё же другие сферы применения, а именно: криптография, астрономия, «спортивные» вычисления знаменитых трансцендентных чисел (π, e и т. д.) с высокой точностью, а также высококачественные изображения фракталов. В настоящее время, арифметика произвольной точности реализуется только программными средствами, так как, несмотря на обширную сферу применения чисел неограниченной разрядности, для решения подавляющего большинства задач хватает базовых арифметических типов, а аппаратная реализация достаточно сложна. И тут возникает вопрос об эффективности программной реализации таких чисел и эффективности операций над ними. Некоторые современные языки программирования имеют встроенную поддержку чисел неограниченной разрядности, для других существуют библиотеки для работы с арифметикой произвольной точности. В данной работе изложение будет вестись относительно реализации таких чисел в объектно-ориентированном языке программирования Java, разработанном компанией Sun Microsystems. Этот язык программирования выбран не случайно, дело в том, что в интернете существует сайт, ранее принадлежавший Sun Microsystems, а ныне - компании Oracle, купившей Sun Microsystems, на котором каждый может оставить сообщение об ошибке или необходимом улучшении касательно Java. В 1999 и 2003 годах разными людьми было написано несколько сообщений о необходимости улучшения операции умножения в классе BigInteger, который является стандартным классом библиотеки Java для работы с арифметикой произвольной точности. Однако качественных улучшений так и не последовало. Собственно говоря, данная работа и посвящена анализу эффективных алгоритмов умножения чисел неограниченной разрядности и их реализации, с целью сделать операцию умножения в классе BigInteger более эффективной. Так же в работе был рассмотрен вопрос об оптимальности представления чисел неограниченной разрядности, существующего в классе BigInteger. 1. Цели и задачи
2. Представление чисел неограниченной разрядности Неотрицательное число N представляется в виде: где , а BASE – основание системы счисления. Например, число Такое представление N является частным случаем многочлена n-ой степени Основание системы счисления BASE обычно зависит от максимального размера базового типа данных, предоставляемого языком программирования (если мы говорим о программной реализации) или аппаратным обеспечением (если мы говорим об аппаратной реализации). Везде в дальнейшем будет говориться именно о программной реализации. Исходя из того, что написано выше, для программной реализации возникает несколько главных вопросов:
Существует два широко распространённых варианта: А) Little-endian нотация, когда младший коэффициент хранится в начале структуры, а старший в конце. Б) Big-endian нотация, когда младший коэффициент хранится в конце структуры, а старший в начале.
Ответы на эти вопросы будут даны в следующей главе при рассмотрении реализации чисел неограниченной разрядности в языке Java. 3. Реализация чисел неограниченной разрядности в Java В стандартной библиотеке Java есть класс BigInteger, который предназначен для работы с числами неограниченной разрядности. Он имеет все необходимые функции для работы с ними, однако, в базе данных запросов об улучшениях и исправлениях для языка Java, можно найти около десятка запросов на улучшение эффективности некоторых из этих функций. В частности, половина этих запросов связана с тем, что алгоритмы умножения и возведения в степень в классе BigInteger реализованы недостаточно эффективно. Одной из целей работы как раз является улучшение эффективности операции умножения в классе BigInteger. Было выдвинуто предположение, что добиться этого можно тремя способами:
Первый способ подразумевает под собой изучение текущего представления. О чём сейчас и пойдёт речь. В случае если окажется, что изменение представления нецелесообразно, для улучшения эффективности останется только второй способ. Итак, в классе BigInteger для хранения коэффициентов выбрана стандартная встроенная в Java структура – массив. Возможно ли использование вместо массива какой-либо более эффективной структуры? Ответ – нет. Даже, если использовать для каждого коэффициента отдельную переменную примитивного типа (что само по себе очень не разумно), это окажется менее эффективно. Почему? Дело в том, что современные процессоры осуществляют доступ к памяти не побайтно, а небольшими блоками, которые называют строками кэша. Обычно размер строки составляет 64 байта. Когда вы читаете какое-либо значение из памяти, в кэш попадает как минимум одна строка кэша. Последующий доступ к какому-либо значению из этой строки происходит очень быстро. Отдельные переменные не обязательно будут расположены в памяти друг за другом, а вот элементы массива всегда располагаются в памяти последовательно, а, следовательно, при доступе к первому элементу, в кэше окажутся несколько последующих элементов и доступ к ним будет быстрее. Другое предложение – это использование более сложных структур данных, в основе которых лежит массив, но, если нам не требуется ничего кроме доступа к коэффициентам, то это не даёт никаких преимуществ, и, более того, может ухудшить эффективность операций. Таким образом, структура для хранения коэффициентов в BigInteger оптимальна. Рассмотрим вопрос о порядке хранения коэффициентов. Как уже было сказано в предыдущей главе, существует два широко распространённых способа расположения коэффициентов в структуре: от младшего коэффициента к старшему и от старшего - к младшему. В BigInteger используется big-endian нотация. Основное преимущество такой записи в отличие от little-endian – естественность записи, ведь мы записываем арабские числа именно таким образом. С другой стороны, большинство операций с числами выполняется от младших разрядов к старшим, а, значит, при таком порядке придётся идти с конца массива в начало, не повлияет ли это на кэширование? На трёх разных системах была проведена проверка этого предположения, и, как оказалось, это абсолютно не влияет на эффективность операций. Таким образом, порядок коэффициентов существенной роли не играет. Осталось рассмотреть последний пункт – выбор основания. В BigInteger коэффициенты принадлежат стандартному примитивному типу языка Java - int, что соответствует основанию системы счисления, равному 2^32. На следующей странице приведен график, на котором отображены кривые, показывающие зависимость времени выполнения операции умножения методом “в столбик” от размера исходных данных при различных основаниях, соответствующих 2^8(byte), 2^16(short), 2^32(int). Стоит отметить, что чем больше основание, тем меньше коэффициентов содержит представление. То есть если размер исходных данных составляет 1024 байта, то для основания 2^8 мы получим 1024 коэффициента, для 2^16 – уже 512 коэффициентов, а для 2^32 – всего 256 коэффициентов. Умножение выполняется над числами одинаковой длины, то есть с одинаковым количеством коэффициентов. Результаты получены на системе с процессором Intel Core 2 Duo E7200 с 2 гигабайтами оперативной памяти. Как видно из графика, чем большее основание мы выбираем, тем быстрее выполняется умножение. Обеспечивается это как раз тем, что чем больше основание, тем меньше коэффициентов содержит представление исходных чисел, а умножение коэффициентов одного типа(byte, short или int) занимает одинаковое количество времени. По крайней мере, это верно для процессоров с разрядностью 32 бита и выше. Однако в языке Java существует ещё один примитивный тип long, что соответствует основанию системы счисления, равному 2^64. Почему бы не выбрать его в качестве типа коэффициентов? Дело в том, что при умножении двух коэффициентов, мы можем получить так называемое переполнение, когда результат умножения не помещается в используемый нами тип. Для контроля такого переполнения необходимо использовать более вместительный тип данных. Для byte таким типом данных будет short, для short – int, для int – long, а вот для long подходящего типа уже нет. Поэтому нельзя использовать long. Таким образом, можно сказать, что представление чисел неограниченной разрядности в Java является оптимальным. Следовательно, для улучшения эффективности операции умножения в классе BigInteger остаётся только второй способ – использование более эффективного алгоритма. А какой алгоритм используется в существующей реализации и можно ли улучшить его? На рис.1 не случайно приведёно время выполнения операции умножения методом “в столбик”. Именно этот алгоритм и используется в BigInteger для перемножения чисел неограниченной разрядности. Он также написан оптимально и его улучшение нецелесообразно. Асимптотическая оценка скорости этого алгоритма в случае, когда длины множителей равны, есть O(n^2). Однако существуют алгоритмы умножения чисел неограниченной разрядности с лучшей асимптотической оценкой. В работе была предпринята попытка использовать некоторые из них, чтобы добиться улучшения эффективности операции умножения класса BigInteger. Перед предоставлением результатов стоит сначала рассмотреть, какие же алгоритмы умножения используются в специализированных библиотеках для работы с числами неограниченной разрядности, рассказать о том, какие алгоритмы были выбраны для реализации и, наконец, показать, в чём состоит суть каждого из выбранных алгоритмов. 4. Обзор существующих библиотек Далее будут перечислены наиболее распространённые библиотеки для работы с числами неограниченной разрядности, дано их краткое описание и представлен список использующихся в них алгоритмов для умножения. Исходя из этих списков, и были выбраны алгоритмы, которые использовались в работе. Однако в данной главе суть алгоритмов раскрываться не будет, будут даны лишь названия. Более подробно об алгоритмах, которые были реализованы в работе, можно прочитать в главе, посвящённой алгоритмам.
Описание: GMP - это свободно распространяемая библиотека для арифметических операций произвольной точности со знаковыми целыми, рациональными числами и числами с плавающей точкой. Предел точности не ограничен, за исключением ограничений, вытекающих из размера доступной памяти. GMP содержит богатый набор функций, оснащенных стандартизованным интерфейсом. Разработчики ставили целью высокую скорость, как для маленьких операндов, так и больших. Скорость работы достигается путем использования быстрых алгоритмов с оптимизированным под большинство процессоров ассемблерным кодом для большинства общих внутренних циклов и благодаря основному акценту на скорость (вместо простоты и элегантности). Считается, что GMP работает быстрее, чем любая другая подобная библиотека. Библиотека широко используется в криптографических целях и для компьютерных вычислений. Библиотека написана на языках C\C++ с использованием ассемблерных вставок и считается самой быстрой и эффективной. Кроме того, она является самой известной из описанных в этой главе библиотек. Рассмотрим алгоритмы, которые используются в GMP для умножения чисел неограниченной разрядности.
|
Добавить документ в свой блог или на сайт
Похожие:
 |
Рабочая программа учебной дисциплины «Высшая математика» Изучение основных понятий высшей математики, теории вероятностей и математической статистики, теоретических основ математических... |
 |
Методические рекомендации по подготовке дипломного проекта 8 Изучение... Методические указания к дипломному проектированию [Текст] / Государственный университет управления, Высшая школа бизнеса гуу, кафедра... |
|
Русский язык математика история этика природоведение география Математика. 5-9 классы (М. Н. Перова — научный редактор программы; Б. Б. Горскин, А. П. Антропов, М. Б. Ульянцева) |
|
Программа учебной дисциплины «Управление данными» «Математика», «Информатика», «Программирование на языках высокого уровня», «Дискретная математика», «Объектно-ориентированное программирование»,... |
|
Справка Компакт -диск "Математика. Мультимедийное сопровождение уроков в начальной школе Компакт -диск "Математика. Демонстрационные таблицы.... |
|
Алексей Гладкий Необходимо широкое разностороннее образование А. Ю. Алексеевым) я узнал, что кафедра классической филологии резко сокращает набор студентов и фактически находится под угрозой... |
|
Математика Дисциплина «Математика» «Общие математические и естественнонаучные дисциплины» учебного плана специальности 080505 Управление персоналом и адресована студентам... |
|
Контрольная работа по дисциплине «Финансовая математика» для групп... Общие требования по оформлению и содержанию контрольной работы дисциплине «Финансовая математика» |
|
Основная образовательная программа 231300 Прикладная математика Квалификация... Преподаваемая дисциплина является средством решения математических задач при помощи программирования на языке C++ |
|
Алексей Гладкий Необходимо широкое разностороннее образование Из обращения преподавателей Санкт-Петербургской Классической Гимназии я узнал, что кафедра классической филологии резко сокращает... |