Длинная арифметика

Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования

САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ

ИМЕНИ Н. Г. ЧЕРНЫШЕВСКОГО 
 
 
 
 

      Кафедра теоретических основ компьютерной

      безопасности  и криптографии 
 
 
 

Длинная арифметика 

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

студента 4 курса факультета компьютерных наук

и информационных технологий

Дружинина Олега  Сергеевича 
 

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

ассистент   Аджигельдиев А.Р. 
 

Зав.кафедрой

профессор,  к.ф.-м.н                       Салий В. Н. 
 
 
 
 
 
 

Саратов 2010

 

Содержание

   Введение 3

  1. Структуры, алгоритмы классических «длинных» чисел  5

  1.1 Структура класса «BigInt» 6

  1.2 Операции над большими числами 7

   2. Структуры и алгоритмы факториальной длинной арифметики 10

   2.1 Структура  факториальной длинной арифметики 10

   2.2 Функции  и операции над числами факториальной арифметики 11

   3. Сравнение систем счисления 15

   3.1 Набор  необходимых для сравнения инструментов 15

   3.2 Сравнение систем счисления 16

   Заключение 20

   Список использованной литературы 21

   Приложение: Class BigInt, функции для работы с классом 22

 

   Введение

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

  «Длинными»  называются числа, для представления которых в базовых типах данных не хватает количества двоичных разрядов. «Длинная» арифметика – это реализация арифметических операций над «длинными» числами.

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

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

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

  Цель  моей курсовой работы заключается в  реализации структур и алгоритмов для  работы с «длинными» числами для последующего использования их в вычислениях. Скорость работы алгоритмов сильно зависит от выбора основания системы счисления (BASE).

  Введем  понятие «факториальная длинная  арифметика», которое означает длинную  арифметику, каждый разряд которой  зависит от факториала номера разряда. Например, число 54321_! представимо в виде: 54321_! = 1*1! + 2*2! +  
+ 3*3! + 4*4! + 5*5! (BASE=n!). В десятичной системе счисления 54321_! = 719₁₀. Более подробно факториальная длинная арифметика описана в главе 2.

  В своей работе я постараюсь проанализировать преимущества факториальной длинной арифметики над стандартной десятичной арифметикой (BASE=10).

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

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

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

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

   BASE – степень двойки позволяет проводить быстрые операции на низком уровне.

   Положим #define BASE 10. Это позволит нам понять функции в общем виде, не вдаваясь в тонкости битовых операций.

 

 1. Структуры, алгоритмы «длинных» чисел

  Обычно, неотрицательное целое число N длины n представляется в виде:

   ,

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

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

  12345₁₀ = 5 + 4*10¹ + 3*10² + 2*10³ + 1*10⁴ (BASE=10).

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

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

  Как видно, цифры хранятся в обратном порядке. Дело в том, что реализации алгоритмов при этом имеют более естественный вид.

  Такое представление N является частным случаем  многочлена n-й степени P(x) = a₀ + a₁*x¹ + a₂*x² + ... + a_n-1*x^n-1, который также удобно хранить в виде массива коэффициентов. Поэтому большинство основных операций над числами при соответствующем упрощении алгоритмов работают для произвольных многочленов (сложение, умножение и т.п.).

 

    1.1 Структура класса «BigInt»

   Длинные числа будем рассматривать как  класс «BigInt» с простейшими операциями. Основными элементами нашего класса являются: количество разрядов длинного числа и массив коэффициентов для каждого разряда. (В массиве цифры хранятся в обратном порядке).

   При объявлении длинного числа используется один из четырех конструкторов:

1. Создание полностью пустого числа
2. Выделение памяти под определенное количество цифр
3. Ввод длинного числа со строки
4. Конструктор копирования

   Уничтожение длинного числа происходит через деструктор.

   Используется  функция zero(), которая обнуляет число, заполняя нулями все коэффициенты и заменяя текущее количество разрядов на 1.

   Оператор long() вычисляет число в “обычном виде”

   N = Coef[0] + Coef[1]BASE + ... + Coef[n-1] BASE^n-1,

   он  может быть весьма полезен при  отладке, когда BASE = 10, а числа небольшие.

   Несколько более интересен оператор присваивания. Для его правильной работы необходимо разобрать случай A=A и при необходимости выделить дополнительную память под коэффициенты. Если присваивание вида A=A, то выйти из функции. Если размера не хватает – происходит переинициализация.

 

    1.2 Операции над большими числами

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

   BigInt& operator+(BigInt&);

   Однако, рассмотрим, что произойдет при вычислении C=A+B.

   Оператор  при всем желании не сможет получить доступ к числу C, поэтому придется создавать временное число Temp=A+B, которое затем будет скопировано в C оператором присваивания.

   Лишних  операций и использования дополнительной памяти можно избежать, если записывать результат в C напрямую.

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

   а) Сложение и вычитание

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

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

   Для вычисления C = A+B, работает вызов вида Add (A, B, C).

   temp играет роль “временной” цифры, до выполнения переноса. Возможно, temp > BASE. В примерах для быстрого доступа к коэффициентам объявляются временные указатели a,b,c.

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

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

   Например, при обычном вычитании 35 – 46 = -11, при нашем 35 – 46 = 89, так как выполняется равенство 89 = 100 – 11(89 дополнение 11 до 100).

   Для вычисления C=A-B работает вызов Sub(A, B, C), причем A.Size должен быть не меньше B.Size. Если длины (Size) равны, но A < B: возвращается -1, результат будет дополнением.

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

   Сложность алгоритмов сложения и вычитания  не превосходит O(n), где n – длина наибольшего слагаемого, а в случае вычитания – уменьшаемого.

   б) Умножение

   Рассмотрим  умножение двух длинных чисел. Mul(A,B,C)

   Алгоритм:

  1. Обнулить C

  2. i = 0

  3. Вычислить временный результат,  соответствующий умножению i-ой  цифры A на число B, в процессе вычисления сразу прибавлять его к C, начиная с i-ой позиции. Если получившаяся цифра C больше BASE – сделать перенос.

  4. Если A не кончилось, увеличить i на единицу и перейти на шаг 3.

   Алгоритм  состоит A.Size циклов по всем цифрам B, значит, время работы оценивается произведением длин чисел – O(n*m), где n и m – длины чисел А и B.

  в) Деление

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