ЛАБОРАТОРНАЯ РАБОТА № 3-1

ТЕМА РАБОТЫ: МАШИННЫЕ АЛГОРИТМЫ УМНОЖЕНИЯ

Цель работы

В результате выполнения лабораторной работы:

1.1. Уметь реализовывать машинные алгоритмы умножения целых чисел.

Материал для предварительного изучения

2.1. Линейные и циклические сдвиги, поразрядные операции

2.2. Перевод целых чисел из 10-й системы счисления в 2-ю и наоборот

Задание к лабораторной работе

3.1. Выбрать вариант задания из табл. 5.1 по своему номеру в журнале группы.

3.2. Представить полученные двоичные числа в формате с фиксированной точкой X 2 и Y 2 в прямом (ПК) и дополнительном кодах (ДК).

3.3. Выполнить вручную умножение двоичных чисел X 2 и Y 2 . Использовать при сложении различные комбинации знаков исходных чисел: (+X 2 +Y 2); ((–X 2)+(–Y 2)); (+X 2 +(–Y 2)); ((–X 2)+Y 2).

3.4. Запустить программу lab5_ORK_06.exe, либо просмотрите и запустите на выполнение файл lab5_ORK_06.pas в среде Borland Pascal. Доказать корректность реализованного алгоритма умножения.

3.5. Оформить отчет о работе.

алгоритм умножения

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

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

1. Сдвиг множителя на 1 разряд в сторону младших разрядов с учетом переноса предыдущих сдвигов, т.е.SHR.

2. Если выдвинутый бит не равен «1», то перейти к 4-му пункту.

3. Добавить множимое к частичной сумме.

4. Сдвиг частичной суммы на 1 разряд в сторону младших разрядов, используя флаг переноса в качестве старшего разряда, т.е. RCR.

5. Если количество циклов не равно N+1, то перейти на пункт 1.

6. Восстановление значения частичной суммы путем сдвига ее на один разряд в сторону старших разрядов с учетом ранее выдвинутого бита, т.е.SHL.

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

Пусть А – множимое, В – множитель, D – частичная сумма.

Пример 4.1: Пусть A = 6 10 = 0110 2 (множимое);

B = 3 10 = 0011 2 (множитель);

D = 0000 2 (частичная сумма)

	№ такта	Действие	Флаг [C]
		Сдвиг В вправо	B = 001|1
			D = D + A
		Сдвиг D вправо	D = 011|0
		Сдвиг В вправо	B = 000|1
		[C] = 1, след. прибавляем множимое к частичной сумме	D = D + A
		Сдвиг D вправо	D = 100|1
		Сдвиг В вправо	B = 000|0
		Сдвиг D вправо	D = 010|0
		Сдвиг В вправо	B = 100|0
		Сдвиг D вправо	D = 001|0
		Сдвиг В вправо	B = 010|0
		Сдвиг D вправо	D = 000|1
		Сдвиг D влево	D = 0|000

Результат D, B: 0001, 0010. 00010010 2 = 18 10 .

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

Если множитель является отрицательным числом, то умножение чисел проводят в дополнительном коде по аналогичному алгоритму умножения чисел в прямом коде, но знак результата получается автоматически. При этом при умножении множимого А на знаковую единицу множителя В необходимо просуммировать не А , а [–А ] дк . Если множимое является отрицательным числом, то в сложении участвуют 1, полученные за счет дописывания слева перед множимым незначащих нулей и последующей инверсией.

Пример 4.2: Пусть A = 10 10 = 0 0110 2 (множимое); [ А] дк = 0 1010

B = -13 10 = 1 1101 2 (множитель); [ В] дк = 1 0011

1 0110 1

При умножении на знаковую единицу множителя В была сделана коррекция – подставлено и просуммировано [– А] дк = 1 0110.

Так как в знаковом разряде произведения стоит 1, то это означает, что результат умножения получен в дополнительном коде. Для перехода в прямой код произведение надо проинвертировать и прибавить 1 к младшему разряду: 1 10000001+1= 1 10000010.

Результат:

D =1 10000010 2 = –(1*2 7 +0*2 6 +0*2 5 +0*2 4 +0*2 3 +0*2 2 +1*2 1 +0*2 0) = –(128+2) =–130 10 .

Пример 4.3: Пусть A = -10 10 (множимое); [ А] дк = 1 0110.

B = 13 10 (множитель); [ В] дк = 0 1101

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

Для перехода в прямой код произведение надо проинвертировать и прибавить 1 к младшему разряду: 1 10000001+1= 1 10000010.

Результат:

D =1 10000010 2 = –(1*2 7 +0*2 6 +0*2 5 +0*2 4 +0*2 3 +0*2 2 +1*2 1 +0*2 0) = –(128+2) = –130 10 .

Табл.5.1. Индивидуальное задание

Вариант	Множимое – А 10	Множитель – В 10	Вариант	Множимое – А 10	Множитель – В 10
		–36			–27
				–5
	–25
				–4
	–36				–26
	–32	–10		–17
		–15			–19
	–35			–8	–5
		–19
	–7			–5
		–5			–12
		–8		–7

1) Номер лабораторной работы.

2) Тема лабораторной работы

3) Цель лабораторной работы.

4) Индивидуальное задание.

5) Ход выполнения лабораторной работы

6) Результат выполнения лабораторной работы.

7) Выводы.

Отчет выполняется на украинском языке .

МИНИСТЕРСТВО ОБРАЗОВАНИЯ НАУКИ И СПОРТА УКРАИНЫ

ХАРЬКОВСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ РАДИОЭЛЕКТРОНИКИ

Факультет Компьютерной инженерии и управления

Кафедра Безопасности информационных систем

КУРСОВАЯ РАБОТА

Дисциплина: Технологии программирования

Тема: Реализация операции возведения в квадрат для больших целых чисел с использованием «классического алгоритма»

Выполнил:

студент I курса

группы БИКС-12-2

Кареба Иван Сергеевич

Научный руководитель:

Мельникова Оксана Анатольевна

Харьков 2013

Харьковский национальный университет радиоэлектроники

Факультет: КИУ

Кафедра: Безопасность информационных технологий

Специальность: “Безопасность информационных и коммуникационных систем”

Дисциплина: “Технологии программирования”

УТВЕРЖДАЮ

Зав. кафедры БИТ

проф. И.Д. Горбенко

НА КУРСОВУЮ РАБОТУ

Студенту

Кареба Ивану Сергеевичу

Тема работы: Реализация операции возведения в квадрат для больших целых чисел с использованием «классического алгоритма».

Срок сдачи студентом законченной работы: .

Исходные данные к проекту:

Перечень графического материала: отсутсвует

________________________________________________________________

Основная литература и источники:

Дата выдачи задания: 25.02.2013

Дата сдачи задания: 25.05.2013

Руководитель работы: Мельникова Оксана Анатольевна

Задание принял к выполнению _______________________________

(подпись студента)

Студент: Кареба Иван Сергеевич _________

(подпись)

Курсовая работа содержит 25 стр., 6 источников, 1 приложение, 6 рисунков.

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

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

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

ВОЗВЕДЕНИЯ В КВАДРАТ, КЛАССИЧЕСКИЙ АЛГОРИТМ УМНОЖЕНИЯ, ДЛИННАЯ АРИФМЕТИКА,. ДОНАЛЬД КНУТ, VISUAL STUDIO 2012

ВВЕДЕНИЕ

ИСПОЛЬЗУЕМЫЕ МЕТОДЫ И АЛГОРИТМЫ

Кнут, его вклад в развитие вычислительных алгоритмов, для ЭВМ

«Классические алгоритмы» Дональда Кнута

1. «Классический алгоритм» операции сложения-вычитания

   «Классический алгоритм» операции умножения

   «Классический алгоритм» операции деления

1.3 Алгоритм Фюрера

1.4 История возникновения степени числа

ОПИСАНИЕ ПРОГРАММЫ

2.1 Общие сведения

2.2 Функциональное назначение

2.3 Описание логической структуры

2.4 Используемые технические средства

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 - Комбинаторные алгоритмы.

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

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

Его так называемые «Классические алгоритмы» пользовались огромным спросом, и не удивительно.

«Классические алгоритмы» Дональда Кнута.

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

Сложение и вычитание 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 над числами высокой точности могут быть теперь реализованы на основе простых операций сложения, вычитания, умножения и деления в столбик, которым учат детей в начальной школе. Фактически большинство алгоритмов, которые будут рассматриваться ниже, - не что иное, как механическое воспроизведение знакомых операций, выполняемых при помощи карандаша и бумаги. Конечно, алгоритмы придется формулировать гораздо более тщательно, чем в начальной школе. Кроме того, необходимо стремиться минимизировать используемую машинную память и время, затрачиваемое на выполнение программ.

«Классический алгоритм» операции сложения-вычитания.

Из-за сложности перевода книги из одного формата в другой и сложности написания формул, я предоставлю алгоритм в виде рисунка.

Рисунок 1.2 – «Представление «Классического алгоритма» сложения, основанного на размышлениях Дональда Эрвина Кнута»

Задача вычитания аналогична задаче сложения, но есть и заслуживающие внимания отличия.

Рисунок 1.3 – ««Представление «Классического алгоритма» вычитания, основанного на размышлениях Дональда Эрвина Кнута»

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

«Классический алгоритм» операции умножения.

Наша следующая задача-умножение. Здесь идеи, использованные при построении алгоритма А, получают дальнейшее развитие.

Рисунок 1.4 – «Первая часть алгоритма умножения»

Алгоритм B - не самый быстрый способ умножения, если множители m и n велики, хотя он имеет преимущество (он прост).

Рисунок 1.5 – «Вторая часть алгоритма умножения»

Классический итеративный алгоритм перемножения квадратных матриц размера n*n имеет сложность O (n 3), а нижняя оценка сложности не менее O (n 2). Следовательно, оптимальный алгоритм имеет сложность, заключенную в этом узком коридоре. Отыскивая алгоритм в классе алгоритмов, разбивающих задачу на a подзадач в c раз меньшего размера с уравнением для функции сложности:

Т (n) = а Т (n/с) + bnk, T (1) = b,

вспоминаем возможные оценки сложности O (n k), O (n k lоg c n), O (n lоg c n). Эти оценки были получены в предположении, что на один шаг разбиения задачи на a подзадач (без решения самих подзадач) требуется bn k операций. Три оценки отражают три варианта соотношений между а и c k : a < c k , a = c k , a > c k .

Поскольку хотим получить алгоритм с показателем функции сложности меньше трех, то не можем допустить в алгоритме ни одного шага со сложностью O (n 3) или более. Следовательно, k может быть равно только единице или двум. При k = 1 отпадают два первых варианта (а < с 1 , а = с 1), так как в этом случае получались бы оценки сложности ниже нижней границы O (n 2). В третьем варианте с учетом нижней границы требуется, чтобы 2 <= log c а < 3 или c 2 <= а < с 3 .

Сделаем попытку применить рекурсию с использованием известного в теории матриц блочного представления:

Здесь A ij - матрицы размера (n/2) * (n/2).

Аналогично представим блоками матрицы В и С . Тогда произведение С=АВ можно найти в четыре этапа, вычислив блоки С 11 , С 12 , С 21 , С 22 матрицы C по формулам C ij = A i,1 B 1,j + A i,2 B 2,j .

Рекурсивная процедура Перемножить вызывается с координатами левого верхнего угла (r A - номер строки, c A - номер столбца) матрицы A и с аналогичными координатами матриц В и С (при первом вызове все координаты равны единице), размером матриц n . В процессе выполнения процедура вызывает себя для перемножения блоков половинного размера. Для суммирования частных произведений она вызывает вспомогательную процедуру Сложить и использует вспомогательные матрицы XI и Х2 для хранения промежуточных результатов.

Если размеры матриц n=1 , то производится обычное умножение скалярных значений (элементов матриц).

процедура Перемножить (А, В: матрица;

переменная C: матрица; rА, сА, rВ, сВ, rС, сС: индекс; n: размер);

переменная X1, X2: матрица;

если n > 1 то

{Вычислить 1-й блок: }

Перемножить (A, В, XI, rА, сА, rВ, сВ, 1, 1, nil );

Перемножить (A, В, X2, rА, сA+n/2, rВ+n/2, сB, 1, 1, n/2);

Сложить (Х1, Х2, С, rС, cC, n/2);

{Вычислить 2-й блок: }

Перемножить (A, В, XI, rА, сА, rВ, сВ+n/2, 1, 1, n/2);

Перемножить (A, В, Х2, rА, сA+n/2, rВ+n/2, сB+n/2,1,1,n/2);

Сложить (Х1, Х2, С, rС, сC+n/2, n/2);

{Вычислить 3-й блок: }

Перемножить (A, В, XI, rА+n/2, сA, rВ, cВ,1,1, n/2);

Перемножить (A, В, Х2, rА+n/2, сA+n/2, rВ+n/2, сB,1,1,n/2);

Сложить (Х1, Х2, С, rС+n/2, cС, n/2);

{Вычислить 4-й блок: }

Перемножить (A, В, XI, rА+n/2, cА, rВ, cВ+n/2,1,1,n/2);

Перемножить (A, В, Х2, rА+n/2, cА+n/2, rВ+n/2, cВ+n/2,1,1, n/2);

Сложить (Х1, Х2, С, rС+n/2, cC+n/2, n/2);

иначе С : = А * В {Умножение скаляров. }

Легко видеть, что для этой процедуры k=2, c=2 , т.е. с k = 4 . Поскольку процедура вызывает себя восемь раз (a=8 ), то мы имеем вариант а > с k и решение уравнения для функции сложности имеет вид O (n log c a) = O (n 3).

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

Это удалось сделать в 1969 г. немецкому ученому Ф. Штрассену (Volker Strassen ). В его методе а=7 , т.е. сложность O (n 2,81).Ф. Штрассен предложил вычислять блоки матрицы-произведения следующим образом:

В этих равенствах только семь умножений матриц, следовательно, рекурсивная процедура содержит в своем теле семь рекурсивных вызовов. Кроме того, имеется 18 аддитивных (сложений и вычитаний) матричных операций, но они не рекурсивны и имеют квадратичную сложность.

Конечно, практическое значение алгоритм Штрассена вряд ли имеет, так как зависимость и 2,81 дает выигрыш против n 3 только при очень больших размерностях задачи, а накладные расходы на организацию рекурсии и на дополнительные аддитивные матричные операции (в классическом алгоритме их четыре) велики. Но с теоретической точки зрения результат очень важен: он помогает продвинуться к пониманию того, какова сложность задачи.

Задача перемножения длинных целых чисел без знака

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

Представление длинных целых чисел

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

Предположим, что перемножается два числа U = u n u n-1 u n-2 . u 3 u 2 u 1 и V = v n v n-1 v n-2 . v 3 v 2 v 1 . Результат имеет суммарную длину W = w n w n-1 w n-2 . w 3 w 2 w 1 . Числа записаны в позиционной системе счисления с основанием (базой) b : 0 <= u i , v i , w i < b . При этом индекс единица соответствует младшей цифре в записи числа.

Алгоритм умножения 1 (классический)

Этот алгоритм работает подобно тому, как производится умножение на бумаге. Числа представлены массивами цифр. Основание системы счисления b может быть как двоичным, b = 2 , так и сколь угодно большим, например, занимающим машинное слово. Важно, чтобы перемножить или сложить цифры можно было одной машинной операцией (или малым их числом). Для представления цифр процедура использует некоторый тип Digit .

procedure SimpleMultiplication (U, V: superlongpositive;

var W: superlongpositive; n, m: integer);

S: DoubleDigit; {Место для формирования двух цифр. }

C: Digit; {Разряд переноса. }

for i: = 1 to n do

W [i]: = 0; {Подготовка места для результата. }

for j: = 1 to m do {Пo цифрам числа V. }

С: = 0; {Сначала переноса нет. }

for i: = 1 to n do {Пo цифрам числа U. }

S: = U [i] *V [j] +W +C;

W : = S mod P; {Временное значение очередной цифры. }

С: = S div P; {Формирование разряда переноса. }

W : = С; {Старшая цифра частичного произведения. }

Непосредственно видно, что сложность этого алгоритма равна O (n m) или в случае сомножителей одинаковой длины - O (n 2).

Алгоритм умножения 2 (оптимизированный по времени). Разделим задачу на подзадачи, разделив запись каждого из сомножителей на две части: U= U 2 U 1 , V=V 2 V 1 . При n -разрядных сомножителях длины U i , V i будут равны n/2 . Индексу 1 соответствует младшая половина, а индексу 2 - старшая. Иначе можно записать U = U 2 00.00 + U 1 = U 2 b n/2 + U 1 .

Произведение UV = (U 2 b n/2 + U 1 ) (V 2 b n/2 + V 1 ) = UVb n + U 2 V 1 b n/2 + U 1 V 2 b n/2 + U 1 V 1 .

Вычисление произведения предлагаемым способом требует четырех умножений чисел половинной длины, трех сложений и трех умножений на величину b q . Умножения на степень b равносильны сдвигу и требуют времени O (n). То же можно сказать о сложности аддитивных операций.

Четырех умножений чисел оказывается слишком много: log 2 4 = 2 , сложность рекурсивного алгоритма будет равна O (n 2).

Но можно немного преобразовать расчетную формулу:

UV = U 2 V 2 (b n + b n/2) + (U 2 - U 1 ) (V 1 -V 2 ) b n/2 + U 1 V 1 (b n/2 +1)

Она содержит только три умножения. Очевидный алгоритм, строящийся по этой формуле, описывается уравнением для функции сложности:

Т (n) = 3Т (n/2) + в n ,

его решение Т (n) = O (n log3) = O (n 1,58), что значительно лучше классического алгоритма.

Возведение целого числа без знака в положительную целую степень

Вычисление у = х n для вещественных x и n не представляет никакого труда: y = e n*ln (x). Но для целых чисел этот способ неприменим, поскольку вычисления экспоненты и логарифма на цифровой вычислительной машине принципиально являются приближенными и не будут давать целочисленный результат. Не поможет здесь и округление, так как крайне трудно достоверно вычислить величину ошибки при приближенных расчетах, следовательно, не известно ни в какую сторону округлять, ни является ли истинным результатом ближайшее целое или ошибка составляет несколько единиц.

Особенно важна эта проблема для длинных целых x и больших n , что встречается в некоторых критических приложениях, например, в шифровании информации.

Правильный результат будет получен, если реализуем возведение в степень через целочисленное умножение. Решение "в лоб" - перемножение n экземпляров x , на что требуется (n-1) операция умножения.

Более остроумный метод состоит в том, чтобы на каждом шаге вычислений активно использовать достижения предыдущих шагов. Пусть, например, требуется вычислить x 1024 . Вместо 1023 умножений можно построить следующую цепочку: х = х 1 , х 2 = (x 1) 2 , х 4 = (x 2) 2 , x 8 = (x 4) 2 , х 16 , х 32 , х 64 , х 128 , х 256 , х 512 , х 1024 . На каждом шаге получается очередная степень x , которая на следующем шаге умножается сама на себя, т.е. предыдущее значение возводится в квадрат. Результат, таким образом, достигается за десять шагов.

Этот метод хорош, если n равно степени двойки. Его сложность равна log n умножений. Для других показателей он требует видоизменения.

Пусть, например, требуется вычислить х 1023 . Очевидным подходом является достижение за девять умножений значения х 512 и перемножение еще за девять операций всех ранее найденных степеней: 1023 = 1 + 2 + 4 + 8 +. + 256 + 512 . Интересно, что для меньшей степени (1023 < 1024) требуется на восемь умножений больше!

Для произвольного n можно использовать так называемый бинарный метод. Представим n его двоичной записью. Читая запись слева направо, начиная с первой значащей цифры (единицы), будем производить следующие действия: первую единицу игнорируем; переменной y присваиваем начальное значение, равное x ; далее в цикле пока не закончились цифры - умножаем y на себя, а если очередная цифра равна единице, то дополнительно умножаем y на x . По окончании цикла в y находится значение x n .

Эти действия можно описать следующей процедурой.

procedure BinaryMethod (x, n: integer; var у: integer);

В: = NextBit (n);

В: = NextBit (n); {В B - первая единица. }

В: = NextBit (n);

while not Eon (n) do {Пока не закончилась запись числа n. }

if В = 1 then у: = у*х;

Сложность процедуры зависит от количества единиц ? (n) в записи числа n и может быть определена формулой:

Т (n) = log n + л (n) - 1.

Минимальная сложность получается для степеней двойки, n = 2 m -1, ? (n) =1 . Максимальная сложность - для чисел n = 2 m -1 :

л (n) = log 2 (n+l).

Что общего между рассмотренными методами оптимизации алгоритмов?

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

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

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

Введение

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

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

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

Однако не только великий Пифагор думал и учил окружающих тому, что способов действия с числами - бесконечное множество.

Очень далеко от Греческого города Кротона, где творил Пифагор, а также, много лет спустя, причём, вряд ли под непосредственным влиянием Пифагора, в России, были, оказывается творческие личности, которые не были связаны догматами о законченности арифметики. И, вот отличный пример того, как русские люди в очередной раз изобрели "пифагоровский" велосипед. К сожалению, точно неизвестно когда и кем конкретно было открыто сие, на мой взгляд, не менее великое изобретение.

Прежде всего, это - не Пифагоров способ умножения. Это - иной способ умножения, истинное происхождение которого пока не установлено. Здесь нет знаменитой таблицы умножения, но есть манипуляции, которые приводят к нужному результату.

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

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

Но, почему же для нас так важен этот малоизвестный способ умножения, изобретенный давным-давно? Где его применяют сейчас? Об этом я напишу далее. А сейчас рассмотрим алгоритм работы русского народного умножения.

Алгоритм умножения

Рассмотрим принцип действия этого способа:

Перемножим два числа: 987 и 1998.

1. Одно запишем слева, другое - справа в строке (Рисунок 2).

2. Левое число будем делить на 2, правое - умножать на 2 и результаты записывать в столбик под ними (если в результате деления возникает остаток, то его отбрасывают и записывают целую часть).