Предисловие [Длинная арифметика]

[Вся длинная арифметика] 

Итак мы начинаем разговор о длинной арифметике.
Под длинной арифметикой мы, как и все, будем понимать математические действия над числами, которые по своему размеру превышают ограничения стандартных типов данных. Так например в тип int(4 байта) уместиться число 2^31 = 2147483648 (~2e9), в unsigned int(те же 4 байта) – число 2^32 = 4294967296 (~4e9). В переменную типа long long или __int64(8 байт) “влезет” 2^63 = 9223372036854775808 (~9e18), в безнаковый тип в два раза больше (~1e19). Как мы видим, уже для чисел в 25 разрядов в десятичной системе счисления нет типа в 32 разрядной системе, который бы удовлетворял нашим нуждам. Как быть? Ведь на практике встречаются числа с куда большим количеством разрядов. Унывать не стоит! Предки уже решили эту проблему за нас. Нам остается просто научиться делать тоже самое и не изобретать велосипед. Хотя крайне полезно сперва его изобрести и попытаться самостоятельно решить возникшие в результате проблемы.

Итак первый логичный вопрос, который может возникнуть у человека, впервые столкнувшимся с длинными числами, это: “Как хранить число в памяти компьютера?”. Два самых распространенных ответа: в виде строки, в виде массива. Очень многие сперва предлагают строку. Мол это удобно и на одну цифру тратиться 1 байт. Доводы весомы и с ними сложно не согласиться. Но заглядывая вперед отметим тот факт, что для ускорения операций мы будем хранить по несколько разрядов в одной цифре(<osn) при основании системы счисления (osn) равной степени десятки. При этом сама цифра может достигать значений до 1e8. И как мы понимаем, здесь 1 байтный тип данных бессилен. Поэтому пока договоримся что все храним в массиве типа int.

Второй вопрос, скорее всего не появится, если конечно вы не читали первую главу книги Окулова “Программирование в алгоритмах”. Он звучит так: “Как хранить число в массиве?”. Очевидный ответ: “Как есть число, так и храним”. Как раз такой подход используется в лекции Михаила Густокашина. Меня познакомил с длинной арифметикой мой сокомандник и товарищ Роман Джабаров, опираясь на первую главу из книги Окулова “Программирование в алгоритмах”. Поэтому мы будем придерживаться этого курса. А именно хранить число задом наперед. Лица студентов, услышавших это выражают, как у нас принято говорить “легкий скепсис”. Почему так? Этот вопрос отпадет, когда будем разбирать операцию A+B.

Итак разберем услышанное на пальцах. Допустим имеем дело с числом N = 1234567. В зависимости от основания системы счисления разбиваем исходное число на цифры и записываем их в обратном порядке. Напомним, что цифра – это число d такое что 0<=d<osn. Поэтому не удивляйтесь, что 67 – это цифра в системе счисления с основанием 100

osn\цифры[индекс]	0	1	2	3	4	5	6
osn = 10	7	6	5	4	3	2	1
osn = 100	67	45	23	1
osn = 1000	567	234	1

За всеми остальными подробностями направляю вас во всю ту же первую главу “Программирование в алгоритмах”

Итак что мы должны вынести из всего вышесказанного? Храним длинное число в виде структуры, описанной ниже:

1. const int max_len = 500; // в зависимости от задачи
2. int osn = 10; // или 100, 1000 и т.д.
3. struct BigInt
4. {
5.   int amount;     // количество цифр в числе
6.   int digits[max_len]; // массив цифр в обратном порядке
7. };

P.S: Длинная арифметика уже встроена в язык Java, но не присутствует в других языках: C++, C#(в framework 4.0 появился BigInteger) или Pascal. Ну чтож один плюс Java за такую находку. Но длинную арифметику нужно уметь реализовывать, хотя бы только ради того, чтобы разобраться что там происходит. На олимпиадах при надобности хороший наборщик может набрать все операции за 15 минут.