Арифметика произвольной точности Пояснение

Я пытаюсь изучить C и столкнулся с неспособностью работать с ДЕЙСТВИТЕЛЬНО большими числами (например, 100 цифр, 1000 цифр и т. Д.). Я знаю, что для этого существуют библиотеки, но я хочу попытаться реализовать это сам.

Я просто хочу знать, есть ли у кого-нибудь или может ли предоставить очень подробное и упрощенное объяснение арифметики произвольной точности.

Все дело в адекватном хранилище и алгоритмах обработки чисел как меньших частей. Предположим, у вас есть компилятор, в котором intможет быть только от 0 до 99, и вы хотите обрабатывать числа до 999999 (здесь мы будем беспокоиться только о положительных числах, чтобы было проще).

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

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

Дополнение, например 123456 + 78:

12 34 56
      78
-- -- --
12 35 34

Работаем с наименее значимого конца:

• начальный перенос = 0.
• 56 + 78 + 0 перенос = 134 = 34 с 1 переносом
• 34 + 00 + 1 перенос = 35 = 35 с 0 переносом
• 12 + 00 + 0 перенос = 12 = 12 с 0 переносом

Фактически так сложение обычно работает на битовом уровне внутри вашего процессора.

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

Я на самом деле написал библиотеки для такого рода вещей, используя максимальную степень десяти, которая может быть помещена в целое число в квадрате (чтобы предотвратить переполнение при умножении двух ints вместе, например, 16-битное intограничение от 0 до 99, чтобы сгенерировать 9801 (<32768) в квадрате или 32-битное intиспользование от 0 до 9999 для генерации 99 980 001 (<2 147 483 648)), что значительно упростило алгоритмы.

Некоторые хитрости, на которые следует обратить внимание.

1 / При сложении или умножении чисел предварительно выделите максимальное необходимое пространство, а затем уменьшите его, если вы обнаружите, что это слишком много. Например, добавление двух 100-значных (где цифра - это int) числа никогда не даст вам более 101 цифры. При умножении 12-значного числа на 3-значное число никогда не будет больше 15 цифр (добавьте количество цифр).

2 / Для увеличения скорости нормализуйте (уменьшите необходимое для хранения) числа только в случае крайней необходимости - в моей библиотеке это было отдельным вызовом, чтобы пользователь мог выбирать между скоростью и хранением.

3 / Сложение положительного и отрицательного числа является вычитанием, а вычитание отрицательного числа аналогично сложению эквивалентного положительного числа. Вы можете сэкономить довольно много кода, заставив методы сложения и вычитания вызывать друг друга после настройки знаков.

4 / Избегайте вычитания больших чисел из маленьких, так как вы неизменно получаете такие числа, как:

         10
         11-
-- -- -- --
99 99 99 99 (and you still have a borrow).

Вместо этого вычтите 10 из 11, а затем отрицайте это:

11
10-
--
 1 (then negate to get -1).

Вот комментарии (преобразованные в текст) из одной из библиотек, для которой мне пришлось это сделать. Сам код, к сожалению, защищен авторским правом, но вы можете выбрать достаточно информации для выполнения четырех основных операций. Предположим далее, что -aи -bпредставляют отрицательные числа, а aи b- ноль или положительные числа.

Для сложения , если знаки разные, используйте вычитание отрицания:

-a +  b becomes b - a
 a + -b becomes a - b

Для вычитания , если знаки разные, используйте сложение отрицания:

 a - -b becomes   a + b
-a -  b becomes -(a + b)

Также специальная обработка, чтобы гарантировать, что мы вычитаем маленькие числа из больших:

small - big becomes -(big - small)

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

475(a) x 32(b) = 475 x (30 + 2)
               = 475 x 30 + 475 x 2
               = 4750 x 3 + 475 x 2
               = 4750 + 4750 + 4750 + 475 + 475

Способ, которым это достигается, включает извлечение каждой из 32 цифр по одной (в обратном порядке), а затем использование add для вычисления значения, которое будет добавлено к результату (изначально нулевое).

ShiftLeftи ShiftRightоперации используются для быстрого умножения или деления a LongIntна значение переноса (10 для «реальной» математики). В приведенном выше примере мы прибавляем 475 к нулю 2 раза (последняя цифра 32), чтобы получить 950 (результат = 0 + 950 = 950).

Затем мы сдвигаем влево 475, чтобы получить 4750, и сдвиг вправо 32, чтобы получить 3. Добавляем 4750 к нулю 3 раза, чтобы получить 14250, затем прибавляем к результату 950, чтобы получить 15200.

Сдвиг влево 4750, чтобы получить 47500, сдвиг вправо, 3, чтобы получить 0. Поскольку смещение вправо 32 теперь равно нулю, мы закончили, и на самом деле 475 x 32 действительно равно 15200.

Деление также сложно, но основано на ранней арифметике (метод «газинты» для «входит в»). Рассмотрим следующее длинное деление 12345 / 27:

       457
   +-------
27 | 12345    27 is larger than 1 or 12 so we first use 123.
     108      27 goes into 123 4 times, 4 x 27 = 108, 123 - 108 = 15.
     ---
      154     Bring down 4.
      135     27 goes into 154 5 times, 5 x 27 = 135, 154 - 135 = 19.
      ---
       195    Bring down 5.
       189    27 goes into 195 7 times, 7 x 27 = 189, 195 - 189 = 6.
       ---
         6    Nothing more to bring down, so stop.

Поэтому 12345 / 27остается 457с остатком 6. Проверить:

  457 x 27 + 6
= 12339    + 6
= 12345

Это реализуется с помощью переменной уменьшения (изначально равной нулю) для уменьшения сегментов 12345 по одному, пока она не станет больше или равна 27.

Затем мы просто вычитаем из него 27, пока не станет меньше 27 - количество вычитаний - это сегмент, добавленный к верхней строке.

Когда больше нет сегментов, которые нужно сбивать, у нас есть результат.

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

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

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

Я также обнаружил, что сотрудники MPIR ( ответвление GMP) более поддаются обсуждению потенциальных изменений - они кажутся более дружелюбными для разработчиков.

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

Например, умножение. Наивно, вы могли бы подумать о методе «школьника», то есть написать одно число над другим, а затем проделать долгое умножение, как вы учили в школе. пример:

      123
    x  34
    -----
      492
+    3690
---------
     4182

но этот метод очень медленный (O (n ^ 2), n - количество цифр). Вместо этого современные пакеты bignum используют либо дискретное преобразование Фурье, либо числовое преобразование, чтобы превратить это по существу в операцию O (n ln (n)).

И это только для целых чисел. Когда вы переходите к более сложным функциям с некоторым типом реального представления числа (log, sqrt, exp и т. Д.), Все становится еще сложнее.

Если вам нужны теоретические знания, я настоятельно рекомендую прочитать первую главу книги Япа «Фундаментальные проблемы алгоритмической алгебры» . Как уже упоминалось, библиотека gmp bignum - отличная библиотека. Для реальных чисел я использовал mpfr, и он мне понравился.

Не изобретайте велосипед: он может оказаться квадратным!

Используйте стороннюю библиотеку, такую ​​как GNU MP , которая проверена и протестирована.

Вы делаете это в основном так же, как с карандашом и бумагой ...

• Число должно быть представлено в буфере (массиве), способном принимать произвольный размер (что означает использование mallocи realloc) по мере необходимости.
• вы реализуете базовую арифметику в максимально возможной степени, используя структуры, поддерживаемые языком, и имеете дело с переносами и перемещением точки счисления вручную
• вы просматриваете тексты числового анализа, чтобы найти эффективные аргументы для решения более сложной функции
• вы реализуете ровно столько, сколько вам нужно.

Обычно вы будете использовать в качестве базовой единицы вычисления

• байты, содержащие 0-99 или 0-255
• 16-битные слова, содержащие 0-9999 или 0-65536
• 32-битные слова, содержащие ...
• ...

как продиктовано вашей архитектурой.

Выбор двоичной или десятичной основы зависит от ваших желаний для максимальной эффективности использования пространства, удобочитаемости и отсутствия поддержки математики в двоично-десятичном формате (BCD) на вашем чипе.

Вы можете сделать это со старшим школьным уровнем математики. Хотя на самом деле используются более продвинутые алгоритмы. Так, например, чтобы добавить два 1024-байтовых числа:

unsigned char first[1024], second[1024], result[1025];
unsigned char carry = 0;
unsigned int  sum   = 0;

for(size_t i = 0; i < 1024; i++)
{
    sum = first[i] + second[i] + carry;
    carry = sum - 255;
}

результат должен быть больше one placeв случае добавления, чтобы позаботиться о максимальных значениях. Посмотри на это :

9
   +
9
----
18

TTMath - отличная библиотека, если вы хотите учиться. Он построен с использованием C ++. Вышеприведенный пример был глупым, но именно так в целом выполняется сложение и вычитание!

Хороший справочник по этому предмету - Вычислительная сложность математических операций . Он сообщает вам, сколько места требуется для каждой операции, которую вы хотите реализовать. Например, если у вас есть два N-digitчисла, то вам нужно 2N digitsсохранить результат умножения.

Как сказал Митч , это далеко не простая задача! Я рекомендую вам взглянуть на TTMath, если вы знаете C ++.

Одна из основных ссылок (IMHO) - это TAOCP Том II Кнута. В нем объясняется множество алгоритмов представления чисел и арифметических операций над этими представлениями.

@Book{Knuth:taocp:2,
   author    = {Knuth, Donald E.},
   title     = {The Art of Computer Programming},
   volume    = {2: Seminumerical Algorithms, second edition},
   year      = {1981},
   publisher = {\Range{Addison}{Wesley}},
   isbn      = {0-201-03822-6},
}

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

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

• Храните бит знака отдельно.

• Сложение двух чисел в основном сводится к сложению цифр с последующей проверкой переноса на каждом шаге.

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

• Даже когда вы храните числа в виде строки отдельных десятичных цифр, деление (также модификация / изменение) может быть выполнено для получения в результате примерно 13 десятичных цифр за раз. Это намного эффективнее, чем деление, которое работает только с одной десятичной цифрой за раз.

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

• Многие операции (факторинг, тесты простоты и т. Д.) Выиграют от операции powermod. То есть, когда вы вычисляете mod (a ^ p, N), уменьшайте результат mod N на каждом шаге возведения в степень, когда p было выражено в двоичной форме. Не вычисляйте сначала a ^ p, а затем пытайтесь уменьшить его по модулю N.

Вот простой (наивный) пример, который я сделал на PHP.

Я реализовал «Сложение» и «Умножение» и использовал это для примера экспоненты.

http://adevsoft.com/simple-php-arbitrary-precision-integer-big-num-example/

Фрагмент кода

// Add two big integers
function ba($a, $b)
{
    if( $a === "0" ) return $b;
    else if( $b === "0") return $a;

    $aa = str_split(strrev(strlen($a)>1?ltrim($a,"0"):$a), 9);
    $bb = str_split(strrev(strlen($b)>1?ltrim($b,"0"):$b), 9);
    $rr = Array();

    $maxC = max(Array(count($aa), count($bb)));
    $aa = array_pad(array_map("strrev", $aa),$maxC+1,"0");
    $bb = array_pad(array_map("strrev", $bb),$maxC+1,"0");

    for( $i=0; $i<=$maxC; $i++ )
    {
        $t = str_pad((string) ($aa[$i] + $bb[$i]), 9, "0", STR_PAD_LEFT);

        if( strlen($t) > 9 )
        {
            $aa[$i+1] = ba($aa[$i+1], substr($t,0,1));
            $t = substr($t, 1);
        }

        array_unshift($rr, $t);
     }

     return implode($rr);
}