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

Естественно, что смысл умножения сохраняется и для многознач­ных чисел, но меняется техника вычислений. Произведение много­значных чисел, как правило, находят, выполняя умножение столби­ком, по определенному алгоритму. Выясним, каким образом возника­ет этот алгоритм, какие теоретические факты лежат в его основе.

Умножим, например, столбиком 428 на 263.

Видим, что для получения ответа нам пришлось умножить 428 на 3, 6 и 2, т.е. умножить многозначное число на однозначное; но, умножив на 6, результат записали по-особому, поместив единицы числа 2568 под десятками, так как умножали на 60 и получили число 25680, но нуль в конце записи опустили. Слагаемое 856 - »то результат умножения на 2 сотни, т.е. число 85600. Кроме того, нам пришлось найти сумму многозначных чисел.

Итак, чтобы выполнять умножение многозначного числа на мно­гозначное, необходимо уметь:

умножать многозначное число на однозначное и на степень десяти;

складывать многозначные числа.

Сначала рассмотрим умножение многозначного числа на однозначное. Умножим, например, 428 на 3. Согласно правилу записи чи­сел в десятичной системе счисления, 428 можно представить в виде 4∙10² + 2∙10 + 8 и тогда 428∙3 = (4∙10² + 2∙10 + 8) ∙ З; На основании дистрибутивности умножения относительно сложения раскроем скобки: (4∙10²) ∙ З + (2∙10)∙ З + 8 ∙ З

Произведения в скобках могут быть найде­ны по таблице умножения однозначных чисел. Видим, что умножение многозначного числа на однозначное свелось к умножению однозначных чисел. Но чтобы получить окончательный результат, надо преобразовать выражение 12∙10² + 6∙10 + 24 - коэф­фициенты перед степенями 10 должны быть меньше 10. Для этого представим число 12 в виде 1 10 + 2, а число 24 в виде 2 10 + 4. Затем раскроем скобки и на основании ассоциативности сложения и дистрибутивности умножения относительно сложения сгруппируем слагаемые.

Таким образом, умножение многозначного числа на однозначное основывается на:

Записи чисел в десятичной системе счисления;

Свойствах сложения и умножения;

Таблицах сложения и умножения однозначных чисел.

Выведем правило умножения многозначного числа на однозначное в общем виде. Пусть требуется умножить х = х = ,

на однозначное число у:

х ∙ у = (a n ·10 n + a n -1 ·10 n -1 + ... +а 1· 10 + а 0 ) ∙ у

причем преобразования выполнены на основании свойств умножения. После этого, используя таблицу умножения, заменяем все произведе­ния а к ∙ у =b к ∙ ∙10 + с и получаем:

х ∙ у = (b n ∙ 10 + с n ) ·10 n + ( b n -1 ∙10 + c n -1 · ) ∙10 n -1 + … + (b 1 ∙10 + с 1 ) ·10 + (b 0 · 10 + с 0 ) =

b n ∙ 10 n + (с n + b n -1 ) ∙10 n + … + ( с 1 + b 0 ) · 10 + с 0

По таблице сложения заменяем суммы ск + b к-1 , где 0 £ к £ n и к : = 0, 1, 2, ..., n , их значениями. Если, например, с 0 одно­значно, то последняя цифра произведения равна с 0 . Если же с 0 = 10 + m 0 , то последняя цифра равна m 0 , а к скобке ( с 1 + b 0 ) надо прибавить 1. Продолжая этот процесс, получим десятичную запись числа х ∙ у .

Описанный процесс позволяет сформулировать в общем виде ал­горитм умножения многозначного числа х = а n а n -1 …а 1 а 0 на однозначное число у.

1. Записываем второе число под первым.

2. Умножаем цифры разряда единиц числа х на число у. Если произведение меньше 10, его записываем в разряд единиц ответа и пере­ходим к следующему разряду (десятков).

3. Если произведение цифр единиц числа х на число у больше или равно 10, то представляем его в виде 10 q 1 + c 0 ; , где c 0 – однозначное число; записываем c 0 в разряд единиц ответа и запоминаем q 1 - пере­нос в следующий разряд.

4. Умножаем цифры разряда десятков на число у, прибавляем к по­лученному произведению число q 1 и повторяем процесс, описанный в пп. 2 и 3.

5. Процесс умножения заканчивается, когда окажется умноженной цифра старшего разряда.

Как известно, умножение числа х на число вида 10 сводится к приписыванию к десятичной записи данного числа к нулей. Покажем это. Умножим число)

х = a n ·10 n + a n -1 ·10 n -1 + ... +а 1· 10 + а 0 на 10 :

(a n ·10 n + a n -1 ·10 n -1 + ... +а 1· 10 + а 0 ) ×10

Полученное выражение является суммой разрядных слагаемых числа

а n а n -1 …а 1 а 0 0…0 , так как равно

a n ·10 n + + a n -1 ·10 n + -1 + ... + а 0 · 10+ 0 × 10+ 0 × 10+…+ 0 × 10 + 0.

Например, 347 × 10 ³ ⁵⁴ = (3× 10 ² + 4 ×10 + 7) × 10 ³ = 3 × 10 ⁵ + 4 × 10 ⁴ + 7 × 10 ³ + 0 × 10 ² + 0 × 10 + 0 = 347000.

Заметим еще, что умножение на число у × 10 , где у - однозначное число, сводится к умножению на однозначное число у и на число 10 . Например, 52 × 300 = 52 × (3 × 10 ²) = (52× 3) = 156 × 10 ² = 15600.

Рассмотрим теперь алгоритм умножения многозначного числа на многозначное. Обратимся сначала к примеру, с которого начинали, т.е. к произведению 428 × 263. Представим число 263 в виде суммы 2× 10 ² + 6 ×10 + 3 и запишем произведение 428 × (2× 10 ² + 6 ×10 + 3). Оно, согласно дистрибутивности умножения относительно сложения, равно 428 × (2× 10 ²) + 428 × (6 ×10) + 428 × 3 . Отсюда, применив ассоциативное свойство умножения, получим: (428 × 2) × 10 ² + (428 × 6) ×10 + 428 × 3 . Видим, что умножение многозначного числа 428 на многозначное число 263 свелось к умножению многозначного числа 428 на однозначные числа 2, 6 и 3, а также на степени 10.

Рассмотрим умножение многозначного числа на многозначное в общем виде. Пусть х и у - многозначные числа, причем у

у = b·10 + b·10 + ... + b 1· 10 + b 0 ,

В силу дистрибутивности умножения относитель­но сложения, а также ассоциативности умножения можно записать: х × у = (х · b·10 + b·10 + ... + b 1· 10 + b 0 ) =х · b 1 на 10.

4. Продолжаем вычисление произведений до вычисления х · bк .

5. Полученные к + 1 произведения складываем.

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

428 × 3 = (400 + 20 + 8) × 3 = 400 × 3 + 20 × 3 + 8 × 3 = 1200 + 60 + 24 = 1284. Основой выполненных преобразований являются:

Представление первого множителя в виде суммы разрядных слагаемых (т.е. запись числа в десятичной системе счисления);

правило умножения суммы на число (или дистрибутивность умножения относительно сложения);

умножение «круглых» (т.е. оканчивающихся нулями) чисел на однозначное число, что сводится к умножению однозначных чисел.

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

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

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

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

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

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

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

Выполнил:

студент 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 – «Вторая часть алгоритма умножения»

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

Естественно, что смысл умножения сохраняется и для многозначных чисел, но меняется техника вычислений. Произведение многозначных чисел, как правило, находят, выполняя умножение столбиком, по определенному алгоритму. Выясним, каким образом возника­ет этот алгоритм, какие теоретические факты лежат в его основе.

Умножим, например, столбиком 428 на 263.

Видим, что для получения ответа нам пришлось умножить 428 на 3, 6 и 2, т.е. умножить многозначное число на однозначное; но, умножив на 6, результат записали по - особому, поместив единицы числа 2568 под десятками числа 1284, так как умножали на 60 и получили число 25680, но нуль в конце записи опустили. Слагаемое 856 - это результат умножения на 2 сотни, т.е. число 85600. Кроме того, нам пришлось найти сумму многозначных чисел.

Итак, чтобы выполнять умножение многозначного числа на многозначное, необходимо уметь:

Умножать многозначное число на однозначное и на степень десяти;

Складывать многозначные числа.

Сначала рассмотрим умножение многозначного числа на однозначное.

Умножим, например, 428 на 3. Согласно правилу записи чи­сел в десятичной системе счисления, 428 можно представить в виде 4 × 10 2 + 2 × 10 + 8 и тогда 428× 3 = (4× 10 2 + 2 × 10+ 8)× 3. На основании дистрибутивности умножения относительно сложения раскроем скобки: (4 × 10 2 + (2× 10)× 3 + 8 × 3. Произведения в скобках могут быть найде­ны по таблице умножения однозначных чисел: 12× 10 2 + 6 × 10 + 24. Видим, что умножение многозначного числа на однозначное свелось к умножению однозначных чисел. Но чтобы получить окончательный результат, надо преобразовать выражение 12× 10 2 + 6 × 10 + 24 - коэф­фициенты перед степенями 10 должны быть меньше 10. Для этого представим число 12 в виде 1 ·10 + 2, а число 24 в виде 2·10 + 4. Затем в выражении (1·10 + 2) ·10 2 + 6·10 + (2·10 + 4) раскроем скобки: 1·10 3 +2·10 2 +6·10+2·10+4. На основании ассоциативности сложения и дистрибутивности умножения относительно сложения сгруппируем слагаемые 6·10 и 2·10 и вынесем 10 за скобки: 1·10 3 + 2·10 2 + (6 + 2) ·10+4. Сумма 6+2 есть сумма однозначных чисел и может быть найдена по таблице сложения: 1 · 10 3 + 2·10 2 + 8 ·10 + 4. Полученное выражение есть десятичная запись числа 1284, т. е. 428·3 = 1284.

Таким образом, умножение многозначного числа на однозначное основывается на:

Записи чисел в десятичной системе счисления;

Свойствах сложения и умножения;

Таблицах сложения и умножения однозначных чисел.

Выведем правило умножения многозначного числа на однозначное в общем виде.

Пусть требуется умножить х = а n × 10 n + а n – 1 × 10 n – 1 + …+ а 1 × 10 + а 0 на однозначное число у:

х × у = (а n × 10 n + а n – 1 × 10 n – 1 + …+ а 1 × 10 + а 0) × у = (а n × у) × 10 n +(а n – 1 × у) × 10 n – 1 + … + а 0 × у причем преобразования выполнены на основании свойств умножения. После этого, используя таблицу умножения, заменяем все произведения а k × у, где 0 £ k £ n, соответствующими значениями а k × у = b k ×10 + с и получаем: х× у = (b п ×10 + с п) + (b п - 1 ×10+ с п - 1) ×10 п - 1 + ... +(b 1 ×10 + с 1) ×10 + (b 0 ×10 + с 0) = b п ×10 п + 1 + (с п + b п - 1) ×10 п + ... + (с 1 + b 0) ×10 + с 0 . По таблице сложения заменяем суммы с k + b k - 1 , где 0 £ k £ n и k = 0, 1, 2, ..., n, их значениями. Если, например, с 0 однозначно, то последняя цифра произведения равна с 0 . Если же с 0 = 10 + m 0 , то последняя цифра равна m 0 , а к скобке (с 1 + b 0) надо прибавить 1. Продолжая этот процесс, получим десятичную запись числа х × у.

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

1. Записываем второе число под первым.

2. Умножаем цифры разряда единиц числа х на число у. Еслипроизведение меньше 10, его записываем в разряд единиц ответа и переходим к следующему разряду (десятков).

3. Если произведение цифр единиц числа х на число у большеили равно 10, то представляем его в виде 10q 1 + с 0 , где с 0 – однозначное число; записываем с 0 в разряд единиц ответа и запоминаем q 1 - перенос в следующий разряд.

4. Умножаем цифры разряда десятков на число у, прибавляемк полученному произведению число q 1 и повторяем процесс, описанный пп. 2 и 3.

5. Процесс умножения заканчивается, когда окажется умноженной цифра старшего разряда.

Как известно, умножение числа х на число вида 10 k сводится к приписыванию к десятичной записи данного числа k нулей. Покажем это. Умножим число х = а n × 10 n + а n – 1 × 10 n – 1 + …+ а 1 × 10 + а 0 на 10 k: (а n × 10 n + а n – 1 × 10 n – 1 + …+ а 1 × 10 + а 0) × 10 k = а n × 10 n+ k + а n – 1 × 10 n+ k – 1 + …+ а 0 × 10 k . Полученное выражение является суммой разрядных слагаемых числа , так как равно a n × 10 n+ k + а n – 1 × 10 n+ k – 1 + …+ а 0 × 10 k + 0 ×10 k -1 + 0× 10 k –2 + …+ 0× 10 + 0.

Например ,

347·10 3 =(3·10 2 +4·10+7)·10 3 =3·10 5 +4·10 4 +7·10 3 =3·10 5 +4·10 4 +7·10 3 +0·10 2 +0·10+0= =347000

Заметим еще, что умножение на число у× 10 k , где у – однозначное число сводится к умножению на однозначное число у и на число 10 k . Например, 52×300 = 52×(3×10 2) = (52×3) ×10 2 = 156×10 2 = 15600.

Рассмотрим теперь алгоритм умножения многозначного числа на многозначное. Обратимся сначала к примеру, с которого начинали, т.е. к произведению 428× 263. Представим число 263 в виде суммы 2× 10 2 + 6× 10 + 3 и запишем произведение 428× (2× 10 2 + 6× 10 + 3). Оно, согласно дистрибутивности умножения относительно сложения, равно 428× (2× 10 2) + 428× (6× 10) + 428× 3. Отсюда, применив ассоциативное свойство умножения, получим: (428× 2) × 10 2 + (428× 6) × 10 + 428× 3. Видим, что умножение многозначного числа 428 на многозначное число 263 свелось к умножению многозначного числа 428 на однозначные числа 2,6 и 3, а также на степени 10.

Рассмотрим умножение многозначного числа на многозначное в общем виде.

Пусть х и у - многозначные числа, причем у = b m × 10 m + b m – 1 × 10 m – 1 + …+ b 0 . В силу дистрибутивности умножения относитель­но сложения, а также ассоциативности умножения можно записать:

х× у = х× (b m × 10 m + b m – 1 × 10 m – 1 + …+ b 0) = (х× b m) × 10 m + (х× b m – 1)× 10 m – 1 + …+ b 0 × х. Последовательно умножая число х на однозначные числа b m , b m – 1 , …, b 0 , а затем на 10 m , 10 m – 1 , …, 1, получаем слагаемые, сумма которых равна х× у.

Сформулирует в общем виде алгоритм умножения числа х = на число у = .

1. Записываем множитель х под ним второй множитель у.

2. Умножаем число х на младший разряд b 0 числа у и записываем произведение х × b 0 под числом у.

3. Умножаем число х на следующий разряд b 1 числа у и записываем произведение х × b 1 , но со сдвигом на один разряд влево, что соответствует умножению х × b 1 на 10.

4. Продолжаем вычисление произведений до вычисления х × b k .

5. Полученные k + 1 произведения складываем.

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

428 × 3 = (400 + 20 + 8) × 3 == 400× 3 + 20× 3 + 8× 3 == 1200 + 60 + 24 = 1284.

Основой выполненных преобразований являются:

Представление первого множителя в виде суммы разрядных слагаемых (т.е. запись числа в десятичной системе счисления);

Правило умножения суммы на число (или дистрибутивность умножения относительно сложения);

Умножение «круглых» (т.е. оканчивающихся нулями) чиселна однозначное число, что сводится к умножению однозначных чисел.

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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