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

StackOverflow https://stackoverflow.com/questions/1218149

  •  10-07-2019
  •  | 
  •  

Вопрос

Я пытаюсь выучить 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 переносом

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

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

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

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

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

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

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

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 операции используются для быстрого умножения или деления числа. 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 - это существенно лучше и быстрее, чем мои собственные библиотеки.

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

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

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

Другие советы

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

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

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

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

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

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

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

Используйте стороннюю библиотеку, например ГНУ МП, это проверено.

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

  • Число должно быть представлено в буфере (массиве), способном принимать произвольный размер (что означает использование 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 ++.

Одной из окончательных ссылок (ИМХО) является 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.

Я реализовал " Добавить " и " Multiply " и использовал это в качестве примера степени.

http://adevsoft.com/simple-php -arbitrary-прецизионный целочисленный большой Num-пример /

Кодовый фрагмент 

// 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);
}
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top