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

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

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

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

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

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

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

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

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

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

студента 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.

  в) Деление

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

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

   г) Печать длинного числа

   С++ допускает перегрузку операторов ввода-вывода, которой воспользуемся для удобства последующего использования.

   Для вывода при помощи этой функции необходимо, чтобы основание BASE было степенью 10, например, BASE = 1000 = 10³. Тогда количество цифр в одном знаке числа будет равно этой степени, а реализация алгоритма – тривиальной.

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

   Для удобства и гибкости класса зададим количество цифр в коэффициенте заранее константой BASE_DIG

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

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

   Длинная арифметика повсеместно используется для работы с большими числами. Возникает  вопрос: какую систему счисления  выбрать, чтобы по минимуму «разместить» длинные числа в памяти и потом  производить расчеты наиболее эффективно, с наименьшими временными затратами? Для ответа на этот вопрос рассмотрим систему счисления, основанную на факториалах позиций цифр в числе. В такой системе счисления с ростом разрядов в разы увеличивается число, представленное по BASE = 10, т.е. например, 3_! = 6₁₀ , а 4_! = 24₁₀ что в 4 раза больше.

   Структура класса полностью совпадает со структурой класса «длинных» чисел, за исключением  того, что BASE, т.е. основание системы счисления меняется в зависимости от разряда числа. Например, число 54321_! в этой интерпретации будет иметь вид:

  54321_! = 1*1! + 2*2! + 3*3! + 4*4! + 5*5! (BASE=n!).

   Заметим следующую закономерность: что разряд «единиц» может колебаться от 0 до 1, «десятков» – от 0 до 2 и т.п. Таким  образом, например, разряд с порядковым номером «30» может колебаться от 0 до 30. Простым представлением длинного числа не обойтись, а через класс BigInt можно, выводя каждый из «сложных» (которые больше 9) коэффициентов по отдельности. происходит бинарным поиском коэффициентов и условием того, что каждый i-й коэффициент частного, умноженный на делитель не превосходит делимого. Сложность алгоритма деления равна O(n²*log₂ n): проверка коэффициентов и бинарный поиск.

 

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

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

  1. перевод числа в факториальную систему счисления

  Функция DecToFac(BigInt A), возвращающая BigInt, но уже в нужном «факториальном» представлении.

  Перевод в факториальную систему счисления  осуществляется за счет деления A на очередную компоненту, при этом остаток от деления на эту компоненту заносится в массив коэффициентов.

  2. перевод числа из факториальной системы счисления в десятичную.

  Функция FacToDec(BigInt A), где А – «факториальное» представление числа, возвращает BigInt по основанию BASE

  Пробегаемся по всей длине числа (i=n-1;0) и записываем в переменную типа BigInt значение соответствующего коэффициента, умноженного на его номер, умноженной на A.Coef[i] и суммируем со следующим значением. (Для реализации вводим две функции: сложение длинного числа с простым целым  умножение длинного числа на простое целое в десятичном виде).

  3. Процедуры сложения/вычитания аналогичны, что и при BASE=10, только на каждом шаге итерации нужно учитывать возможность переноса в следующий разряд, при этом увеличив BASE на единицу.

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

   Для вычисления C = A+B, перегружен оператор сложения.

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

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

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

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

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

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

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

   На  вход подаются два длинных числа. Создаем длинное число res и обнуляем его. Запускаем цикл по длине первого множителя, начиная со старшего разряда, в котором заполняем число-результат:

1. Умножаем второй множитель на i-ый коэффициент первого.
2. Добавляем получившийся результат к res.
3. Умножаем res на i.

   В итоге res и будет являться произведением двух чисел.

   5. Деление длинного числа на число базового типа: описано функцией  
void Div_fac(const BigInt& A, const BigInt& B, BigInt& Q, int& R),  
где A – делимое, B – делитель, Q – частное, R – остаток.

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

  В R записывается последний промежуточный остаток от деления.

  Теперь  перейдем к реализации деления длинных чисел, основанных на факториальной системе счисления. Данную реализацию осуществляет функция void Div_fac(BigInt& A, BigInt& B, BigInt& Q, BigInt& R);

  Сначала создадим вспомогательное число  fact = 0, у которого только один коэффициент по ходу алгоритма не должен быть нуль, примем R = A.  
Учитывая то, что , двигаясь  
в цикле от старшего разряда делимого к младшему, бинарным поиском находим коэффициенты частного. Промежуточным остатком будет R = R – B * fact.

  После выполнения цикла в Q вернется целая часть от деления, в R – остаток от деления.

  Для удобства пользования классом BigInt перегружены «operator /», «operator %», которые возвращают Q и R соответственно как в функции void Div_Fac(…).

  6. Реализованный класс BigInt имеет перегруженные операторы сравнения длинных чисел, основанных на факториалах, которые незамысловато реализуются.

 

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

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

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

  Возьмем класс длинной арифметики, с основанием 2³². Каждый разряд числа, записанного в этом классе, колеблется от 0 до 4 294 967 296, операции сложения, вычитания, умножения и деления выполняются быстро за счет сдвига на низком уровне.

 

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

   а) Рассмотрим десятичное представление числа: посмотрим, сколько разрядов будут занимать числа в факториальной и 2³² системах счисления в зависимости от увеличения числа в десятичной системе счисления.

   

    
табл.1 Изменение количества разрядов в зависимости от BASE (1)

рис.1 Зависимость разрядов BASE от десятичных разрядов (1)

   На  рис.1 рассмотрены десятичные числа  длиной от 1 до 65, числовые характеристики занесены в табл.1. Видно, что с  ростом числа десятичных разрядов растут разряды в других системах счисления, причем кривая 2³² ближе к оси абсцисс, нежели двух других кривых. Факториальная система счисления совершенно не выгодна для десятичных чисел длиной меньше 22, а дальше начинает выигрывать у десятичной системы счисления.

   Продолжим дальше увеличивать длину десятичных чисел до миллиона. Посмотрим изменения:

   

   табл.2 Изменение количества разрядов в зависимости от BASE (2)

рис.2 Зависимость разрядов BASE от десятичных разрядов (2)

   На  рис.2 видно, что при 1млн. разрядов десятичная система счисления содержит в 5 раз больше разрядов, чем факториальная и в 10 раз больше, чем система 2³². Соответственно использовать систему счисления на факториалах выгоднее, чем десятичную.