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

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

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

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

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

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

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

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

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

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

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

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

• байты, содержащие с 0-99 или 0-255
• 16 бит слова contaning увядают 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.) Вот несколько трюков, которые я использую:

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

• хранить знаковый бит отдельно.

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

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

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

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

• многие операции (факторинг, тесты на примитивность и т. д.) выиграет от операции powermod. То есть,когда вы вычисляете mod(a^p, N), уменьшите результат mod N на каждом шаге возведения в степень, где p было выражено в двоичной форме. Не вычисляйте сначала a^p, а затем попробуйте уменьшить его mod 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);
}