МИНИСТЕРСТВО ОБРАЗОВАНИЯ НАУКИ И СПОРТА УКРАИНЫ
ХАРЬКОВСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ РАДИОЭЛЕКТРОНИКИ
Факультет Компьютерной инженерии и управления
Кафедра Безопасности информационных систем
КУРСОВАЯ РАБОТА
Дисциплина: Технологии программирования
Тема: Реализация операции возведения в квадрат для больших целых чисел с использованием «классического алгоритма»
Выполнил:
студент I курса
группы БИКС-12-2
Кареба Иван Сергеевич
Научный руководитель:
Мельникова Оксана Анатольевна
Харьков 2013
Харьковский национальный университет радиоэлектроники
Факультет: КИУ
Кафедра: Безопасность информационных технологий
Специальность: “Безопасность информационных и коммуникационных систем”
Дисциплина: “Технологии программирования”
УТВЕРЖДАЮ
Зав. кафедры БИТ
проф. И.Д. Горбенко
“20“ апреля 2013 г.
ЗАДАНИЕ
НА КУРСОВУЮ РАБОТУ
Студенту
Кареба Ивану Сергеевичу
Тема работы: Реализация операции возведения в квадрат для больших целых чисел с использованием «классического алгоритма».
Срок сдачи студентом законченной работы: .
Исходные данные к проекту:
Содержание пояснительной записки: необходимо осуществить реализацию возведения в квадрат, использую классический алгоритм умножения.
Перечень графического материала: отсутсвует
________________________________________________________________
Основная литература и источники:
Дата выдачи задания: 25.02.2013
Дата сдачи задания: 25.05.2013
Руководитель работы: Мельникова Оксана Анатольевна
Задание принял к выполнению _______________________________
(подпись студента)
Студент: Кареба Иван Сергеевич _________
(подпись)
РЕФЕРАТ
Курсовая работа содержит 25 стр., 6 источников, 1 приложение, 6 рисунков.
Объектом исследования является операция возведения в квадрат больших целых чисел.
Предметом исследования является программная реализация операции возведения в квадрат больших целых чисел.
Основной задачей работы является реализация операции возведения в квадрат больших целых чисел (от 512 бит ) с использованием классического алгоритма, то есть умножения «в столбик».
ВОЗВЕДЕНИЯ В КВАДРАТ, КЛАССИЧЕСКИЙ АЛГОРИТМ УМНОЖЕНИЯ, ДЛИННАЯ АРИФМЕТИКА,. ДОНАЛЬД КНУТ, VISUAL STUDIO 2012
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
ИСПОЛЬЗУЕМЫЕ МЕТОДЫ И АЛГОРИТМЫ
Кнут, его вклад в развитие вычислительных алгоритмов, для ЭВМ
«Классические алгоритмы» Дональда Кнута
«Классический алгоритм» операции сложения-вычитания
«Классический алгоритм» операции умножения
«Классический алгоритм» операции деления
1.3 Алгоритм Фюрера
1.4 История возникновения степени числа
ОПИСАНИЕ ПРОГРАММЫ
2.1 Общие сведения
2.2 Функциональное назначение
2.3 Описание логической структуры
2.4 Используемые технические средства
2.5 Вызов и загрузка программы
2.6 Входные и выходные данные
ВЫВОДЫ
ПЕРЕЧЕНЬ ССЫЛОК
ПРИЛОЖЕНИЕ А
ВВЕДЕНИЕ
С развитием науки и всего человечества, появилась потребность в быстрой работе с большими числами. Создавались и придумывались различные алгоритмы позволяющие быстро складывать, вычитать, умножать, делить и так далее. Это была сложная и кропотливая работа – сидеть и считать такие числа. Поэтому человечество упрощала эту работу различными приборами, помогающими считать: таблиц, счеты и так далее…
Одним из таких приборов была ЭВМ. Она делала все эти операции за считанные секунды, что в значительной мере ускорило развитие наук. Вскоре наука так стремительно развинулась, что и для компьютера арифметические операции стали непосильной задачей. Проблема была с ограниченной памятью разрядной сетки: 8 бит, 16 бит, 32 бит, а в скорее и 64 бит. Но этого было мало.
И в ХХ веке заслуженный профессор, математик и программист, а также «отец» основных алгоритмов вычислительной математики Дональд Эрвин Кнут разработал серию так называемых «Классических алгоритмов» для арифметических операций с использованием ЭВМ.
Эти алгоритмы помогли компьютерам имея разрядность значительно меньшую разрядности вычисляемых чисел давать верный ответ над многими арифметическими операциями.
В основу этих алгоритмов легли школьные алгоритмы: сложение, вычитание, умножение «в столбик», деление «уголком» и прочее, что многие дети изучают в школе.
Мы рассмотрим алгоритмы для сложения-вычитания, умножения и подробней рассмотрим алгоритм возведения в степень.
1 Используемые методы и алгоритмы
Кнут, его вклад в развитие вычислительных алгоритмов, для ЭВМ.
Дональд Эрвин Кнут (англ. Donald Ervin Knuth, МФА: /kəˈnuːθ/, родился 10 января 1938) — американский учёный, почётный профессор в отставке (professor emeritus) Стэнфордского университета и нескольких других университетов в разных странах, иностранный член Российской академии наук, преподаватель и идеолог программирования, автор 19 монографий (в том числе ряда классических книг по программированию) и более 160 статей, разработчик нескольких известных программных технологий. Автор всемирно известной серии книг, посвящённой основным алгоритмам и методам вычислительной математики, а также создатель настольных издательских систем TEX и METAFONT, предназначенных для набора и вёрстки книг, посвящённых технической тематике (в первую очередь — физико-математических).
Рисунок 1.1 – «Дональд Эрвин Кнут»
Дональд Кнут является автором интересующих нас книг:
«Искусство программирования» том 1 - Основные алгоритмы, «Искусство программирования» том 2 - Получисленные методы, «Искусство программирования» том 3 - Сортировка и поиск, «Искусство программирования» том 4 - Комбинаторные алгоритмы.[1]
В этих книгах описываются всевозможные алгоритмы и методы работы с ЭВМ, упрощающие и дающие более широкий спектр ресурсов.
Для разработки этих методов и алгоритмов требуется необычайно творческий склад ума, а также доскональное понимание алгебры, высшей математики и абстрактной алгебры. Все это присутствовало в сознании Дональда Эрвина, что принципе и позволило ему создать свои алгоритмы.
Его так называемые «Классические алгоритмы» пользовались огромным спросом, и не удивительно.
«Классические алгоритмы» Дональда Кнута.
В этом разделе будут рассмотрены алгоритмы следующих операций:
- сложение и вычитание n-разрядных целых чисел с получением n-разрядного результата и разряда переноса;
- умножение m-разрядного целого числа на n-разрядное целое число с получением (m+n)-разрядного результата;
- деление (m+n)-разрядного числа на n-разрядного числа с получением (m+1)-разрядного частного и n-разрядного остатка.
Эти алгоритмы можно назвать классическими, так как само слово “алгоритм” на протяжении столетий использовалось в связи с реализацией вычислительных процессов. Термин “n-разрядное целое число” означает любое неотрицательное целое число, меньшее b^n, где b есть основание обычной позиционной системы счисления, в которой представляются числа; такие числа в этой системе записываются с использованием не более чем n-“разрядов”.
Классические алгоритмы для целых чисел можно очевидным образом распространять на числа с разделяющей точкой внутри числа или числа в формате с плавающей точкой, заданные с повышенной точностью.
В настоящем разделе будут рассмотрены алгоритмы выполнения перечисленных операций над целыми числами, представляемыми в позиционной системе по основанию b, где b — заданное целое число, равное или большее 2. Таким образом, эти алгоритмы представляют собой достаточно общие определения арифметических процессов, и в этом качестве они не связаны ни с какой конкретной вычислительной машиной. Тем не менее, рассуждения будут некоторым образом машинно-ориентированными, поскольку нас, в основном, интересуют эффективные методы выполнения при помощи компьютера вычислений с высокой точностью. Хотя приведенные примеры ориентированы на гипотетический компьютер М1Х, по существу, те же рассуждения применимы почти для любой другой машины.
Для понимания сути чисел повышенной точности наиболее существенно то, что их можно рассматривать как числа, записанные в системе счисления по основанию w, где w — размер слова. Например, целое число, заполняющее 10 машинных слов в памяти компьютера, размер слова которой — w = 10^10, имеет 100 десятичных разрядов. Однако мы будем рассматривать его как 10-разрядное число по основанию 10^10. Такой подход обосновывается теми же соображениями, что и переход, скажем, от двоичной системы счисления к шестнадцатеричной; мы просто группируем биты.
С учетом этих соглашений будем рассматривать следующие элементарные операции:
А) сложение и вычитание одноразрядных целых чисел с получением одноразрядного результата и разряда переноса;
B) умножение одноразрядного целого числа на одноразрядное с получением двухразрядного результата;
С) деление двухразрядного целого числа на одноразрядное, которое обеспечивает получение частного как одноразрядного целого числа и одноразрядного остатка.
В связи с тем, что целые числа повышенной точности воспринимаются как числа по основанию b, полезно представить себе соответствующую ситуацию при Ь = 10, считая при этом, что арифметические операции выполняются вручную. Тогда операция A аналогична запоминанию таблицы сложения, операция B аналогична запоминанию таблицы умножения, а операция C - это, по существу, запоминание “обращенной” таблицы умножения. Более сложные операции A, B и C над числами высокой точности могут быть теперь реализованы на основе простых операций сложения, вычитания, умножения и деления в столбик, которым учат детей в начальной школе. Фактически большинство алгоритмов, которые будут рассматриваться ниже, — не что иное, как механическое воспроизведение знакомых операций, выполняемых при помощи карандаша и бумаги. Конечно, алгоритмы придется формулировать гораздо более тщательно, чем в начальной школе. Кроме того, необходимо стремиться минимизировать используемую машинную память и время, затрачиваемое на выполнение программ.
Далее я приведу алгоритмы операций А, B и C. И подробнее мы рассмотрим операцию деления.
«Классический алгоритм» операции сложения-вычитания.
Из-за сложности перевода книги из одного формата в другой и сложности написания формул, я предоставлю алгоритм в виде рисунка.
Рисунок 1.2 – «Представление «Классического алгоритма» сложения, основанного на размышлениях Дональда Эрвина Кнута»
Задача вычитания аналогична задаче сложения, но есть и заслуживающие внимания отличия.
Рисунок 1.3 – ««Представление «Классического алгоритма» вычитания, основанного на размышлениях Дональда Эрвина Кнута»
Эрвин Кнут, в своей книге советует не создавать одну комбинированную программу, для сложения-вычитания, а создать две абсолютно независимых программы. Он поясняет это тем, что в общем случае для реализации этих операций предпочтительнее использовать две разные программы, чтобы внутренний вычислительный цикл выполнялся настолько быстро, насколько это возможно.[2]
«Классический алгоритм» операции умножения.
Наша следующая задача—умножение. Здесь идеи, использованные при построении алгоритма А, получают дальнейшее развитие.
Рисунок 1.4 – «Первая часть алгоритма умножения»
Алгоритм B — не самый быстрый способ умножения, если множители m и n велики, хотя он имеет преимущество (он прост).
Рисунок 1.5 – «Вторая часть алгоритма умножения»