Lec_07

ДЛИННАЯ АРИФМЕТИКА

2014		Парамонов А.И.

БОЛЬШИЕ ЧИСЛА

2

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

Более того, мы ограничены величиной чисел, с которыми можем работать.

Числа, для представления которых в стандартных компьютерных типах данных не хватает количества двоичных разрядов, называются “длинными”.

Реализация арифметических операций над такими “длинными” числами получила название “длинной

арифметики”.

Пример больших чисел

3

Посчитаем N-ное число Фибоначчи.

Эти числа растут чуть менее чем 2n.

Таким образом мы можем посчитать не более 32-го числа.

Используя длинную арифметику, мы сможем посчитать «любое» из них (всё зависит от возможностей памяти).

Если мы захотим посчитать 3000 число Фибоначчи, нам придется хранить только 250 чисел

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

4

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

N a0 a1 BASE a2 BASE 2 ... an1 BASE n1

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

0 ai BASE

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

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

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

8

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

В качестве примера, рассмотрим массив для

1234510: (5, 4, 3, 2, 1).

*** Как видно, цифры хранятся в обратном порядке.

Такое представление N является частным случаем многочлена n-й степени

P(x) a0 a1 x a2 x2 ... an1 xn1

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

9

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

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

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

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

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

Пример представления “длинного” числа

10

30! = 265252859812191058636308480000000

BASE = 10 000

30! = 2 * BASE8 + 6525 * BASE 7 + 2859 * BASE 8121 * BASE 5 + 9105 * BASE 4 + 8636 * BASE 3084 * BASE 2 + 8000 * BASE + 0000.

6

3

+

+

Запишем данное представление в виде массива коэффициентов:

Номер элемента	0	1	2	3	4	5	6	7	8	9
в массиве
Значение	9	0	8000	3084	8636	9105	8121	2859	6525	2

ОПЕРАЦИИ НАД «ДЛИННЫМИ» ЧИСЛАМИ

11

ВВОД ЧИСЛА int MaxDig = 1000;

//Максимальное количество цифр — четырехзначных int Base = 10000;

//Основание системы счисления int Number[MaxDig];

//Максимальное количество цифр в числе

Пусть вводится число 23851674

основанием (BASE) является 1000 (значит храним по три цифры в элементе массива Number).

Изменение значений элементов массива Number в процессе ввода (посимвольного в переменную figure) рассмотрим на примере..

Процесс ввода “длинного” числа

12

	Number			figure	Примечание
[0]	[1]	[2]	[3]
3	674	851	23		Конечное состояние
0	0	0	0	2	Начальное состояние
1	2	0	0	3	1-й шаг
1	23	0	0	8	2-й шаг
1	238	0	0	5	3-й шаг
2	385	2	0	1	4-й шаг: старшая цифра элемента Number[1]
					перешла в пока пустой элемент Number[2]
2	851	23	0	6	5-й шаг
2	516	238	0	7	6-й шаг
3	167	385	2	4	7-й шаг
3	674	851	23

Фрагмент псевдокода

13

while ( НЕ КОНЕЦ ВВОДА )

{

for (i = Number[0]; i>=1; i--)

{

//протаскивание старшей цифры в числе из Number[i]

//в младшую цифру числа из Number[i+1]

Number[i+1] = Number[i+1]+(Number[i]*10)/base; Number[i] = ((Number[i]*10)%base);

}

// добавляем младшую цифру к числу из Number[1] if (isdigit(figure))

Number[1]=Number[1]+(int)figure - int('0');

// изменяем длину числа задействованных элементов массива Number if (Number[Number[0]+1]>0)

Number[0]++;

СЧИТЫВАЕМ СИМВОЛ В figure

}