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

Решая задачи, многим из нас приходилось сталкиваться с тем, что нам просто не хватало размерностей типов для, казалось, простейших операций: сложение, вычитание и умножение. Все эти операции знакомы Вам с ранних классов. Но что делать, если одну из этих операций необходимо применить для огромных чисел, скажем так 1000 знаков или более…(насколько хватит фантазии!). Данная статья поможет решить эту проблему. 

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

Сложение длинных чисел

Рассмотрим арифметическую операцию сложения, применяемую в длинной арифметике. Алгоритм этого нехитрого арифметического действия, на удивление, простой. Он выглядит так:

    // определяем длину массива суммы
    if (size_a > size_b)
        length = size_a + 1;
    else
        length = size_b + 1;

    for (int ix = 0; ix < length; ix++)
    {
        b[ix] += a[ix]; // суммируем последние разряды чисел
        b[ix + 1] += (b[ix] / 10); // если есть разряд для переноса, переносим его в следующий разряд
        b[ix] %= 10; // если есть разряд для переноса он отсекается
    }

    if (b[length - 1] == 0)
        length--;

“Виновники торжества” – то есть числа, которые мы будем складывать, предположительно записаны в массивы a и b. Необходимо учесть, что они записаны “зеркально”, то есть первый элемент массива соответствует последней цифре соответствующего числа, второй элемент – предпоследней, и т.д. Размеры длин чисел хранятся в переменных size_a и size_b, но Вы можете использовать любые другие. Вы конечно же задумались: “Зачем здесь оператор выбора if, строки 2 — 5?” или “Для чего он здесь?”. В этом блоке кода мы определяем максимальную длину числа, полученного в результате суммирования. Ведь, чаще всего суммируемые числа, разной длинны, одно больше, другое меньше, а нам нужно выделить память так, чтобы каждое число вместилось.

Далее, в алгоритме, делаем так, как нас учили на уроках математики: сначала складываем отдельные разряды, начиная с конца, строка 9; делим получившуюся сумму на 10 и получаем целую часть от деления на десять, которую мы сразу прибавляем к следующему разряду, строка 10.  В строке 11, мы отсекаем первый разряд полученного числа, если конечно он есть.
Вот и все. Главное не забыть, что число будет храниться в массиве b и выводить его следует с конца.

Вычитание длинных чисел

Вторая, наиболее используемая арифметическая операция – это вычитание. И эта часть статьи поможет Вам научиться писать алгоритмы вычитания больших и огромных чисел. 
Будем считать, что наши числа хранятся в массивах a и b, m и n – длинны этих чисел соответственно. Следует учесть, что числа записаны “зеркально”(см. выше). Конечно, если мы знаем какое число больше, то задача упрощается. Но мы можем и не знать этого. Тогда нам следует сперва найти, какое из чисел больше. Это нам понадобится для определения знака получившегося числа, то есть, если первое число меньше второго, то в ответе появится минус. И так, приступим к написанию первой части алгоритма, то есть определению большего числа. Алгоритм выглядит так:

    int k = 3; // если к == 3, значит числа одинаковой длинны
    length = size_a;
    if (size_a > size_b)
    {
        length = size_a;
        k = 1; // если к == 1, значит первое число длиннее второго
    }
    else
        if (size_b > size_a)
        {
            length = size_b;
            k = 2; // если к == 2, значит второе число длиннее первого
        }
        else // если числа одинаковой длинны, то необходимо сравнить их веса
            for (int ix = 0; ix < length;) // поразрядное сравнение весов чисел
            {
                if (a[ix] > b[ix]) // если разряд первого числа больше
                {
                    k = 1; // значит первое число длиннее второго
                    break; // выход из цикла for
                }

                if(b[ix] > a[ix]) // если разряд второго числа больше
                {
                    k = 2; // значит второе число длиннее первого
                    break; // выход из цикла for
                }
            } // конец for

Теперь поясню написанное. Сначала Вы можете увидеть, что переменной k придается значение 3. В данной части алгоритма переменная k является флагом результата проверки. Если числа равны, то k останется равно 3, если первое больше второго, то k примет значение 1, если второе больше первого, то k примет значение 2. Переменная length примет значение длинны большего числа. Теперь перейдем к обоснованию работоспособности этого алгоритма. Сравнение чисел происходит в два этапа. Сначала мы сравниваем длинны чисел: какое число длиннее, то и больше, строки 1 — 11. Если числа одинаковой длинны, то переходим к по разрядовому сравнению, строки 13 — 26. Начинаем по порядку сравнивать разряды начиная с самого старшего, так мы определим, больший вес числа. В этом и заключается суть и сложность первой части. Теперь перейдем ко второй части алгоритма — вычитание. Она выглядит так:

int difference (int *x, int *y, int *z, int length)
{
    for (int ix = 0; ix < (length - 1); ix++) // проход по всем разрядам числа, начиная с последнего, не доходя до первого
    {
        if (ix < (length - 1)) // если текущий разряд чисел не первый
        {
            x[ix + 1]--; // в следующуем разряде большего числа занимаем 1.
            z[ix] += 10 + x[ix]; // в ответ записываем сумму значения текущего разряда большего числа и 10-ти

        } else  // если текущий разряд чисел - первый
                z[ix] += x[ix]; // в ответ суммируем значение текущего разряда большего числа

        z[ix] -= y[ix]; // вычитаем значение текущего разряда меньшего числа

        if (z[ix] / 10 > 0) // если значение в текущем разряде двухразрядное
        {
            z[ix + 1]++; // переносим единицу в старший разряд
            z[ix] %= 10; // в текущем разряде отсекаем ее
        }
    }
    return 0;
}

Для самого вычитания удобно написать функцию, ведь нам тогда не придется писать два алгоритма для двух случаев: когда первое число больше второго, и наоборот. В массиве x мы содержим большее число, в массиве y – меньшее, в массиве z – результат. Алгоритм довольно простой: для каждого разряда мы добавляем 10, с учетом вычитания из старшего разряда — 1. Это делается для упрощения вычитания разрядов. Эта операция делается лишь в том случае, когда рассматриваемый разряд не является последним в массиве (первым в числе). После вычитания разрядов мы проверяем получившееся число в данном разряде в массиве z. Ответ запишется в массив z, причем “зеркальным” (см. выше) способом. Процедуру следует вызывать следующим образом:

if (k == 1) difference(a,b,c, length); - если первое число больше второго,
if (k == 2) difference(b,a,c, length); - если второе число больше первого.

Теперь ответ будет храниться в массиве c все в том же “зеркальном” порядке. Вот мы и научились вычитать большие и огромные числа.

Умножение длинных чисел

Теперь перейдем к последней, но не менее важной теме нашей статьи – к произведению. Этот алгоритм чаще двух предыдущих можно встретить при решении задач. Собственно меньше демогогики. Перейдем непосредственно к самому алгоритму. Представляю Вашему вниманию алгоритм:

    length = size_a + size_b + 1;

    for (int ix = 0; ix < size_a; ix++)
        for (int jx = 0; jx < size_b; jx++)
            c[ix + jx - 1] += a[ix] * b[jx];

    for (int ix = 0; ix < length; ix++)
    {
        c[ix + 1] +=  c[ix] / 10;
        c[ix] %= 10; 
    }

    while (c[length] == 0)
        length-- ;

Вот так выглядит алгоритм задачи. Теперь попробуем “это” разобрать, точнее разобраться, как это работает. Сначала у нас имелось два числа в массивах a и b все в том же “зеркальном” (см. выше) виде. Длинны чисел хранятся в переменных size_a и size_b. В переменной length хранится длинна результирующего числа. Она будет равна либо сумме длин первоначальных чисел, либо этой сумме увеличенной на единицу. Но так, как мы не знаем точной длинны полученного числа, то возьмем длину побольше, то есть второй вариант. Теперь после этих не хитрых подсчетов, приступим к перемножению чисел. Будем их перемножать так, как нас учили в школе. Для этого запускаем два цикла: один до size_a, другой до size_b. После этих циклов вы можете увидеть еще один до length. благодаря ему в записи числа в массиве, в каждой ячейке массива мы получаем по одной цифре полученного числа. Последний цикл нужен, что бы узнать точную длину полученного числа, ведь предположенная нами длина числа может быть больше действительной. Ответ будет храниться в массиве c, все в том же “зеркальном” виде.
Вот и весь алгоритм. Проще его понять, когда он реализован на языке программирования, в нашем случае — это С++.