Арифметика многоразрядных чисел

 
 
 
 
 
 
 

     Арифметика  многоразрядных чисел 
 
 
 

                                          Выполнил:

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

                                          математического факультета

                                          33 группы 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Оглавление 

Введение…………………………………………………………………………...3 

Представление числа в любой системе счисления…………………………......4

Операции  над длинными числами..…………………………………………......5

Сложение  многоразрядных чисел……………………………………………….6

Вычитание многоразрядных чисел ……………………………………………...7

Умножение многоразрядных чисел ……………………………………………8

Быстрое умножение……………………………………………………………...11

Сравнение “быстрого” и “школьного” умножения…...………………………22

Точность  вычислений и её улучшение………………………………………...23 

Заключение……………………………………………………………………….24 

Литература……………………………………………………………………….26 

Приложение…..………………………………………………………………….27 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Введение

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

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

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

Представление числа в любой  системе счисления

     Обычно, неотрицательное целое число N длины n представляется в виде N = a0 + a1*BASE + a2*BASE2 + ... + an-1 BASEn-1,

     где BASE – основание системы счисления, все коэффициенты 0 . ai < BASE.

     Например, число  в этой интерпретации будет иметь вид

     1234510 = 5 + 4*10 + 3*102 + 2*103 + 1*104 (BASE=10).

     Длинное число хранится в массиве, где i-й  элемент соответствует коэффициенту числа при BASE.

     В качестве примера, рассмотрим массив для : : (5, 4, 3, 2, 1).

     Как видно, цифры хранятся в обратном порядке. Это – некая “заготовка на будущее”: дело в том, что реализации алгоритмов при этом имеют более  естественный вид.

     Такое представление N является частным случаем многочлена n-й степени P(x) = a0 + a1*x + a2*x2 + ... + an-1 xn-1, который также удобно хранить в виде массива коэффициентов. Поэтому большинство основных операций над числами при соответствующем упрощении алгоритмов работают для произвольных многочленов (сложение, умножение и т.п).

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

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

     1. Основание должно подходить под  один из базовых типов данных 

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

     3. Для удобства можно выбрать  BASE как степень 10 (вывод информации, отладка).

     Операции  над «длинными числами»

     Рассмотрим  достаточно популярную в программировании задачу на работу с "длинными" числами. Реально с "астрономическими" или "микроскопическими" числами  приходится сталкиваться не так уж и часто. Тем не менее, упражнения, рассматриваемые в этой публикации, могут послужить хорошей тренировкой в области программирования и занять достойное место в классах с углубленным изучением информатики или на кружках по программированию. Алгоритмы, представленные ниже, записаны на Turbo Pascal, версия 7.0 и на Си++. При желании или необходимости они могут легко быть адаптированы к любой другой программной среде. Диапазон представления целых чисел (Integer, Word, LongInt) ограничен, о чем не раз уже говорилось (впрочем, для действительных величин это замечание тоже актуально). Поэтому при решении задач всегда приходится действовать с оглядкой, — как бы не допустить возникновения ошибки выхода за диапазон или переполнения. Например, вычисляя факториал (n! = 1 * 2 * 3 * … * n), в диапазоне представления величин типа Integer удастся правильно получить только 7! = 5040, а в диапазоне представления типа LongInt — 12! = 479001600. Для больших значений, конечно, можно использовать действительные типы данных, но это уже не гарантирует точного результата. Поэтому полезно для получения точных значений при действиях с многозначными числами разработать другие способы представления таких чисел, алгоритмы выполнения арифметических и других операций, процедуры ввода и вывода результатов и т.д.

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

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

Сложение  многоразрядных(длинных) чисел

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

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

     Найдём  сумму чисел А и В. Будем складывать элементы массивов с одинаковыми номерами и хранить полученные результаты, как элементы массива С (алгоритм работы с такими массивами напоминает сложение в столбик). Если на каком-то шаге получим С[i] , то на месте C[i] оставляем остаток от деления C[i] на 10 (количество единиц данного разряда), а к элементу C[i+1] прибавим 1 (перенос 1 в следующий разряд).

     Если число А состоит из N цифр, а число В – из M цифр, то число С имеет либо max(N,M) цифр, либо max(N,M)+1 цифру. Обозначим через К величину max(N,M)+1.

     Перед выполнением сложения следует дополнить  незначащими нулями число с меньшим  количеством цифр так, чтобы количество цифр уравнялось. Этого можно достигнуть и обнулив массивы А и В  до ввода цифр.

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

     После выполнения данного алгоритма в  первых К элементах массива С  будет храниться сумма чисел  А и В, С[1]- цифра младшего разряда. Последняя проверка позволяет убрать незначащий нуль из старшего разряда числа С.

     Вычитание многоразрядных чисел

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

     Если  длины одинаковы, но одно больше другого - это приведет к тому, что в конце процесса останется неиспользованное заимствование, а результат будет дополнением до BASEB.Size.

     Для определённости будем считать, что  А>B. Если нет, то необходимо поменять числа местами, а результат сделать отрицательным. 

     Если  число А состоит из N цифр, тогда  число В не может иметь более  чем N цифр. Разность будет содержать  не более чем N цифр.

     Найдём  разность чисел А и В. Будем  вычитать элементы массива В из элементов  массива А с соответствующими номерами. Полученные результаты будем хранить в массиве С. Если на каком-то шаге получим C[i]<0, то к элементу C[i] прибавляем 10, а от элемента C[i+1] отнимаем 1(забираем 1 из следующего разряда).

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

     Умножение многоразрядных чисел

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

                         Const MNax = 2000;

               Type Digit = 0..9;

                    DlChislo = Array[1..Nmax] Of Digit;

     Для решения поставленной задачи необходимо уметь выполнять следующие действия:

     1) ввод "длинного" числа;

     2) собственно умножение двух "длинных"  чисел;

     3) вывод "длинного" числа;

     4) определение количества цифр в записи числа.

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

     (Процедура  преобразования длинного числа,  записанного в виде строки, в  массив цифр; переменная OK принимает  значение True, если в записи числа  нет посторонних символов, отличных от десятичных цифр, иначе — false)

      Procedure Translate(S : String; Var A : DlChislo; Var OK : Boolean);

      Var I : Word;

      Begin

          Zero(A); I := Length(S); OK := True;

          While (I >= 1) And OK Do

           Begin

               If S[I] In ['0'..'9']

               Then A[Length(S)- I + 1]:= Ord(S[I]) - 48

               Else OK := False; I := I - 1

           End

      End;

     В процедуре вызывается подпрограмма Zero(A), назначение которой — запись нуля в каждый разряд длинного числа. Вот текст этой процедуры:

          (Процедура обнуления длинного числа)

          Procedure Zero(Var A : DlChislo);

          Var I : Integer;

          Begin

             For I := 1 To NMax Do A[I] := 0;

          End;

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

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

        (Функция определения количества цифр в записи длинного числа)

          Function Dlina(C : DlChislo) : Integer;

          Var I : Integer;