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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

в соответствии с вашей архитектурой.

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

Assuming that you wish to write a big integer code yourself, this can be surprisingly simple to do, spoken as someone who did it recently (though in MATLAB.) Here are a few of the tricks I used:

• I stored each individual decimal digit as a double number. This makes many operations simple, especially output. While it does take up more storage than you might wish, memory is cheap here, and it makes multiplication very efficient if you can convolve a pair of vectors efficiently. Alternatively, you can store several decimal digits in a double, but beware then that convolution to do the multiplication can cause numerical problems on very large numbers.

• Store a sign bit separately.

• Addition of two numbers is mainly a matter of adding the digits, then check for a carry at each step.

• Multiplication of a pair of numbers is best done as convolution followed by a carry step, at least if you have a fast convolution code on tap.

• Even when you store the numbers as a string of individual decimal digits, division (also mod/rem ops) can be done to gain roughly 13 decimal digits at a time in the result. This is much more efficient than a divide that works on only 1 decimal digit at a time.

• To compute an integer power of an integer, compute the binary representation of the exponent. Then use repeated squaring operations to compute the powers as needed.

• Many operations (factoring, primality tests, etc.) will benefit from a powermod operation. That is, when you compute mod(a^p,N), reduce the result mod N at each step of the exponentiation where p has been expressed in a binary form. Do not compute a^p first, and then try to reduce it mod N.

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

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

9
   +
9
----
18

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

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

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