Арифметика чисел в b-ичной системе счисления (Длинная арифметика) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Подбор значения очередной цифры в алгоритме деления в столбик)
(Вычитание)
(Метки: правка с мобильного устройства, правка из мобильной версии)
 
(не показаны 63 промежуточные версии этого же участника)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Длинная арифметика — это набор программных средств (структуры данных и алгоритмы), которые позволяют работать с числами гораздо больших величин, чем это позволяют стандартные типы данных.
+
'''Длинная арифметика''' (англ. ''arbitrary-precision arithmetic'', или ''bignum arithmetic'') — это набор программных средств (структуры данных и алгоритмы), которые позволяют работать с числами гораздо больших величин, чем это позволяют стандартные типы данных.
 
}}
 
}}
 +
{{Определение
 +
|definition=
 +
'''Классическая длинная арифметика''' — длинная арифметика, основная идея которой заключается в том, что число хранится в виде массива его цифр. Цифры могут использоваться из той или иной системы счисления, обычно применяются десятичная система счисления и её степени (десять тысяч, миллиард), двоичная система счисления либо любая другая.
 +
}}
 +
==Представление в памяти==
 +
 +
Один из вариантов хранения длинных чисел — массив целых чисел '''int''', где каждый элемент — это одна цифра числа в <tex>b</tex>-ичной системе счисления.
 +
Для повышения эффективности каждый элемент вектора может содержать не одну, а несколько цифр (например, работаем в системе счисления по основанию миллиард, тогда каждый элемент вектора содержит <tex>9</tex> цифр):
 +
  '''const''' '''int''' base <tex>\,=\,</tex> 1000 <tex>\cdot</tex> 1000 <tex>\cdot</tex> 1000
 +
 +
Цифры будут храниться в массиве в следующем порядке: сначала идут наименее значимые цифры (т.е., например, единицы, десятки, сотни, и т.д.).
 +
 +
Кроме того, все операции реализуются таким образом, что после выполнения любой из них лидирующие нули (т.е. лишние нули в начале числа) отсутствуют (разумеется, в предположении, что перед каждой операцией лидирующие нули также отсутствуют).
 +
Следует отметить, что в представленной реализации для числа ноль корректно поддерживаются сразу два представления: пустой вектор цифр, и вектор цифр, содержащий единственный элемент — ноль.
 +
 +
==Операции над числами==
 +
 +
Операции над числами производятся с помощью "школьных" алгоритмов сложения, вычитания, умножения, деления столбиком.
 +
После совершения операций следует не забывать удалять лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.
 +
К ним также применимы алгоритмы быстрого умножения: [[Быстрое преобразование Фурье | Быстрое преобразование Фурье]] и [https://ru.wikipedia.org/wiki/%D0%A3%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5_%D0%9A%D0%B0%D1%80%D0%B0%D1%86%D1%83%D0%B1%D1%8B Алгоритм Карацубы].
 +
 +
Приведённые ниже алгоритмы корректны в силу того, что они являются реализацией "школьных" алгоритмов действий в столбик:
 +
 +
<tex>A = abc = 100 \cdot a + 10 \cdot b + c </tex>
 +
 +
<tex>B = de = 10 \cdot d + e </tex>
 +
 +
Тогда сумма <tex>A + B = abc + de = (100 \cdot a + 10 \cdot b + c) + (10 \cdot d + e) = 100 \cdot a + 10 \cdot (b + d) + (c + e) </tex>
 +
 +
Разность <tex>A - B = abc - de = (100 \cdot a + 10 \cdot b + c) - (10 \cdot d + e) = 100 \cdot a + 10 \cdot (b - d) + (c - e) </tex>
 +
 +
Произведение <tex>A \cdot B = abc \cdot de = (100 \cdot a + 10 \cdot b + c) \cdot (10 \cdot d + e) = 100 \cdot a \cdot 10 \cdot d + 10 \cdot b \cdot 10 \cdot d + c \cdot 10 \cdot d + 100 \cdot a \cdot e + 10 \cdot b \cdot e + c \cdot e = 1000 \cdot a \cdot d + 100 \cdot (a \cdot e + b \cdot d) + 10 \cdot (b \cdot e + c \cdot d) + c \cdot e</tex>
 +
 +
=== Сложение ===
 +
Прибавляет к числу <tex>a</tex> число <tex>b</tex> и сохраняет результат в <tex>a</tex> :
 +
 +
Алгоритм работает за <tex>O(max(n, m))</tex>, где <tex>n, m</tex> — длины чисел <tex>a</tex> и <tex>b</tex>.
 +
 +
Алгоритм не требует дополнительной памяти.
 +
 +
    '''function''' getSum(a: '''vector<int>''', b: '''vector<int>'''): '''vector<int>'''
 +
        carry = 0
 +
        i = 0
 +
        '''while''' i < max(a.size(),b.size()) || carry
 +
            '''if''' i == a.size()
 +
                a.push_back(0)
 +
            '''if''' i < b.size()
 +
                a[i] += carry + b[i]
 +
            '''else'''
 +
                a[i] += carry
 +
            carry = a[i] <tex>\geqslant</tex> base
 +
            '''if''' carry
 +
                a[i] -= base
 +
            i++
 +
        '''return''' a
 +
 +
=== Вычитание ===
 +
Отнимает от числа <tex>a</tex> число <tex>b\,(a \geqslant b)</tex>  и сохраняет результат в <tex> a</tex>:
 +
 +
Алгоритм работает за <tex>O(max(n, m))</tex>, где <tex>n, m</tex> — длины чисел <tex>a</tex> и <tex>b</tex>.
 +
 +
Алгоритм не требует дополнительной памяти.
 +
    '''function''' getSub(a: '''vector<int>''', b: '''vector<int>'''): '''vector<int>'''
 +
        carry = 0
 +
        i = 0
 +
        '''while''' i < b.size() || carry
 +
            '''if''' i < b.size()
 +
                a[i] -= carry + b[i]
 +
            '''else'''
 +
                a[i] -= carry
 +
            carry = a[i] < 0
 +
            '''if''' carry
 +
                a[i] += base
 +
            i++
 +
        '''while''' a.size() > 1 && a.back() == 0
 +
            a.pop_back()
 +
        <font color=green>//Здесь мы после выполнения вычитания удаляем лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.</font>
 +
        '''return''' a
 +
 +
=== Умножение длинного на короткое ===
 +
Умножает длинное <tex>a</tex> на короткое <tex>b\, (b < base)</tex> и сохраняет результат в <tex>a</tex> :
  
Основная идея заключается в том, что число хранится в виде массива его цифр.
+
Алгоритм работает за <tex>O(n)</tex>, где <tex>n</tex> — длина длинного числа.
  
Цифры могут использоваться из той или иной системы счисления, обычно применяются десятичная система счисления и её степени (десять тысяч, миллиард), двоичная система счисления либо любая другая.
+
Алгоритм требует <tex>O(n)</tex> памяти, где <tex>n</tex> — длина длинного числа.
  
==Представление в памяти==
+
    '''function''' getCompLongShort(a: '''vector<int>''', b: '''int'''): '''vector<int>'''
 +
        carry = 0
 +
        i = 0
 +
        '''while''' i < a.size() || carry
 +
            '''if''' i == a.size()
 +
                a.push_back(0)
 +
            cur = carry + a[i] <tex>\cdot</tex> b;
 +
            a[i] = cur '''mod''' base
 +
            carry = cur / base
 +
            i++
 +
        '''return''' a
  
Один из вариантов хранения длинных чисел можно реализовать в виде массива целых чисел, где каждый элемент — это одна цифра числа в '''b'''-й системе счисления.
+
=== Умножение двух длинных чисел ===
 +
Умножает <tex>a</tex> на <tex>b</tex> и результат сохраняет в <tex>c</tex> :
  
Цифры будут храниться в массиве в таком порядке, что сначала идут наименее значимые цифры (т.е., например, единицы, десятки, сотни, и т.д.).
+
Алгоритм работает за <tex>O(n \cdot m)</tex>, где <tex>n, m</tex> — длины чисел <tex>a</tex> и <tex>b</tex>.
  
Кроме того, все операции будут реализованы таким образом, что после выполнения любой из них лидирующие нули (т.е. лишние нули в начале числа) отсутствуют (разумеется, в предположении, что перед каждой операцией лидирующие нули также отсутствуют). Следует отметить, что в представленной реализации для числа ноль корректно поддерживаются сразу два представления: пустой вектор цифр, и вектор цифр, содержащий единственный элемент — ноль.
+
Алгоритм требует <tex>O(n \cdot m)</tex> памяти, где <tex>n, m</tex> — длины чисел <tex>a</tex> и <tex>b</tex>.
  
==Сложение, вычитание, умножение, деление на короткое, деление на длинное==
+
    '''function''' getCompLongLong(a: '''vector<int>''', b: '''vector<int>'''): '''vector<int>'''
 +
        carry = 0
 +
        i = 0
 +
        '''while''' i < a.size()
 +
            j = 0
 +
            '''while''' (j < b.size() || carry)
 +
                '''if''' j < b.size()
 +
                    cur = c[i + j] + a[i] <tex>\cdot</tex> b[j] + carry
 +
                '''else'''
 +
                    cur = c[i + j] + carry
 +
                c[i + j] = cur '''mod''' base
 +
                carry = cur / base
 +
                j++
 +
            i++
 +
        '''while''' c.size() > 1 && c.back() == 0
 +
            c.pop_back()
 +
        '''return''' c
  
Операции над числами в этом виде длинной арифметики производятся с помощью "школьных" алгоритмов сложения, вычитания, умножения, деления столбиком.
+
=== Деление длинного на короткое  ===
 +
Делит длинное <tex>a</tex> на короткое <tex>b\, (b < base)</tex>, частное сохраняет в <tex>a</tex>, остаток в <tex>carry</tex> :
  
После совершения операций следует не забывать удалять лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.
+
Алгоритм работает за <tex>O(n)</tex>, где <tex>n</tex> — длина длинного числа.
  
==Подбор значения очередной цифры в алгоритме деления в столбик==
+
Алгоритм не требует дополнительной памяти.
 +
   
 +
    '''function''' getDivLongShort(a: '''vector<int>''', b: '''int'''): '''vector<int>'''
 +
        carry = 0
 +
        i = a.size() - 1
 +
        '''while''' i <tex>\geqslant</tex> 0
 +
            cur = a[i] + carry <tex>\cdot</tex> base
 +
            a[i] = cur '''mod''' base
 +
            carry = cur / base
 +
            i--
 +
        '''while''' a.size() > 1 && a.back() == 0
 +
            a.pop_back()
 +
        '''return''' a
  
Подбор следующей цифры <tex>k \in [0, b)</tex> частного можно производить с помощью стандартного алгоритма двоичного поиска за <tex>\ln(b)</tex>.
+
== См. также ==
 +
*[[Системы счисления | Системы счисления]]
 +
*[[Разложение на множители (факторизация) | Разложение на множители (факторизация)]]
  
Но также существуют и более быстрые алгоритмы. Довольно интересный способ состоит в высказывании догадки ('''qGuess''') по первым цифрам
 
делителя и делимого. Понятно, что этих нескольких цифр недостаточно для гарантированно
 
правильного результата, однако неплохое приближение все же получится.
 
Пусть очередной шаг представляет собой деление некоторого <tex>U = (u_0, u_1, \cdots, u_n)</tex> на <tex>B = (b_0, b_1, \cdots, b_{n-1})</tex>.
 
Если <tex>b_{n-1} \ge</tex> '''BASE''' <tex>/2</tex> ('''BASE''' — основание системы счисления), то можно доказать следующие факты:
 
  
*1. Если положить '''qGuess''' <tex> = (u_n \cdot </tex> '''BASE''' <tex>+ u_{n-1}) / b_{n-1}</tex> , то '''qGuess'''<tex>-2 \le q \le</tex> '''qGuess'''.
+
== Источники информации ==
Иначе говоря, вычисленная таким способом “догадка” будет не меньше искомого частного,
+
* [http://e-maxx.ru/algo/big_integer e-maxx: Длинная арифметика]
но может быть больше на 1 или 2.
 
*2. Если же дополнительно выполняется неравенство '''qGuess'''<tex> \cdot b_{n-2} ></tex> '''BASE''' <tex>\cdot r + u_{n-2}</tex> , где r – остаток при нахождении '''qGuess''' и '''qGuess''' ≠ '''BASE''', то '''qGuess''' <tex>-1 \le q \le</tex> '''qGuess''', причем вероятность события '''qGuess''' = q + 1 приблизительно равна 2 / '''BASE'''.
 
Таким образом, если <tex>b_{n-1} \ge</tex> '''BASE'''<tex>/2</tex>, то можно вычислить '''qGuess''' <tex> = (u_n \cdot</tex>'''BASE''' <tex> + u_{n-1}) / b_{n-1}</tex> и уменьшать на единицу до тех пор, пока не станут выполняться условия. Получившееся значение будет либо правильным частным q, либо, с вероятностью 2/'''BASE''', на единицу большим числом.
 
  
Что делать, если <tex>b_{n-1}</tex> слишком мало, чтобы пользоваться таким способом?
 
Например, можно домножить делитель и делимое на одно и то же число '''scale'''='''BASE'''<tex> / ( b_{n-1} +1 )</tex>. В случае, если основание системы счисления является степенью двойки, '''scale''' можно выбрать соответствующей степенью двойки.
 
При этом несколько изменится способ вычисления остатка, а частное останется прежним. Такое домножение иногда называют нормализацией числа. На тот случай, если '''qGuess''' получилось все же на единицу большим q, будем использовать вычитание, которое вместо отрицательного числа даст дополнение до следующей степени основания. Если такое произошло, то последний перенос будет равен -1. Это сигнал, что необходимо прибавить одно B назад.
 
Заметим, что в конце сложения будет лишний перенос на единицу, о котором нужно забыть (он компенсирует последний перенос (-1)).
 
  
http://forum.sources.ru/index.php?showtopic=210512&hl=
+
[[Категория: Алгоритмы алгебры и теории чисел]]
 +
[[Категория: Теория чисел]]

Текущая версия на 11:41, 2 июня 2018

Определение:
Длинная арифметика (англ. arbitrary-precision arithmetic, или bignum arithmetic) — это набор программных средств (структуры данных и алгоритмы), которые позволяют работать с числами гораздо больших величин, чем это позволяют стандартные типы данных.


Определение:
Классическая длинная арифметика — длинная арифметика, основная идея которой заключается в том, что число хранится в виде массива его цифр. Цифры могут использоваться из той или иной системы счисления, обычно применяются десятичная система счисления и её степени (десять тысяч, миллиард), двоичная система счисления либо любая другая.

Представление в памяти[править]

Один из вариантов хранения длинных чисел — массив целых чисел int, где каждый элемент — это одна цифра числа в [math]b[/math]-ичной системе счисления. Для повышения эффективности каждый элемент вектора может содержать не одну, а несколько цифр (например, работаем в системе счисления по основанию миллиард, тогда каждый элемент вектора содержит [math]9[/math] цифр):

  const int base [math]\,=\,[/math] 1000 [math]\cdot[/math] 1000 [math]\cdot[/math] 1000

Цифры будут храниться в массиве в следующем порядке: сначала идут наименее значимые цифры (т.е., например, единицы, десятки, сотни, и т.д.).

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

Операции над числами[править]

Операции над числами производятся с помощью "школьных" алгоритмов сложения, вычитания, умножения, деления столбиком. После совершения операций следует не забывать удалять лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют. К ним также применимы алгоритмы быстрого умножения: Быстрое преобразование Фурье и Алгоритм Карацубы.

Приведённые ниже алгоритмы корректны в силу того, что они являются реализацией "школьных" алгоритмов действий в столбик:

[math]A = abc = 100 \cdot a + 10 \cdot b + c [/math]

[math]B = de = 10 \cdot d + e [/math]

Тогда сумма [math]A + B = abc + de = (100 \cdot a + 10 \cdot b + c) + (10 \cdot d + e) = 100 \cdot a + 10 \cdot (b + d) + (c + e) [/math]

Разность [math]A - B = abc - de = (100 \cdot a + 10 \cdot b + c) - (10 \cdot d + e) = 100 \cdot a + 10 \cdot (b - d) + (c - e) [/math]

Произведение [math]A \cdot B = abc \cdot de = (100 \cdot a + 10 \cdot b + c) \cdot (10 \cdot d + e) = 100 \cdot a \cdot 10 \cdot d + 10 \cdot b \cdot 10 \cdot d + c \cdot 10 \cdot d + 100 \cdot a \cdot e + 10 \cdot b \cdot e + c \cdot e = 1000 \cdot a \cdot d + 100 \cdot (a \cdot e + b \cdot d) + 10 \cdot (b \cdot e + c \cdot d) + c \cdot e[/math]

Сложение[править]

Прибавляет к числу [math]a[/math] число [math]b[/math] и сохраняет результат в [math]a[/math] :

Алгоритм работает за [math]O(max(n, m))[/math], где [math]n, m[/math] — длины чисел [math]a[/math] и [math]b[/math].

Алгоритм не требует дополнительной памяти.

    function getSum(a: vector<int>, b: vector<int>): vector<int>
        carry = 0
        i = 0
        while i < max(a.size(),b.size()) || carry
            if i == a.size()
                a.push_back(0)
            if i < b.size()
                a[i] += carry + b[i]
            else
                a[i] += carry
            carry = a[i] [math]\geqslant[/math] base
            if carry
                a[i] -= base
            i++
        return a

Вычитание[править]

Отнимает от числа [math]a[/math] число [math]b\,(a \geqslant b)[/math] и сохраняет результат в [math] a[/math]:

Алгоритм работает за [math]O(max(n, m))[/math], где [math]n, m[/math] — длины чисел [math]a[/math] и [math]b[/math].

Алгоритм не требует дополнительной памяти.

    function getSub(a: vector<int>, b: vector<int>): vector<int>
        carry = 0
        i = 0
        while i < b.size() || carry
            if i < b.size()
                a[i] -= carry + b[i]
            else
                a[i] -= carry
            carry = a[i] < 0
            if carry
                a[i] += base
            i++
        while a.size() > 1 && a.back() == 0
            a.pop_back()
        //Здесь мы после выполнения вычитания удаляем лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.
        return a

Умножение длинного на короткое[править]

Умножает длинное [math]a[/math] на короткое [math]b\, (b \lt base)[/math] и сохраняет результат в [math]a[/math] :

Алгоритм работает за [math]O(n)[/math], где [math]n[/math] — длина длинного числа.

Алгоритм требует [math]O(n)[/math] памяти, где [math]n[/math] — длина длинного числа.

    function getCompLongShort(a: vector<int>, b: int): vector<int>
        carry = 0
        i = 0
        while i < a.size() || carry
            if i == a.size()
                a.push_back(0)
            cur = carry + a[i] [math]\cdot[/math] b;
            a[i] = cur mod base
            carry = cur / base
            i++
        return a

Умножение двух длинных чисел[править]

Умножает [math]a[/math] на [math]b[/math] и результат сохраняет в [math]c[/math] :

Алгоритм работает за [math]O(n \cdot m)[/math], где [math]n, m[/math] — длины чисел [math]a[/math] и [math]b[/math].

Алгоритм требует [math]O(n \cdot m)[/math] памяти, где [math]n, m[/math] — длины чисел [math]a[/math] и [math]b[/math].

    function getCompLongLong(a: vector<int>, b: vector<int>): vector<int>
        carry = 0
        i = 0
        while i < a.size()
            j = 0
            while (j < b.size() || carry)
                if j < b.size()
                    cur = c[i + j] + a[i] [math]\cdot[/math] b[j] + carry
                else
                    cur = c[i + j] + carry
                c[i + j] = cur mod base
                carry = cur / base
                j++
            i++
        while c.size() > 1 && c.back() == 0
            c.pop_back()
        return c

Деление длинного на короткое[править]

Делит длинное [math]a[/math] на короткое [math]b\, (b \lt base)[/math], частное сохраняет в [math]a[/math], остаток в [math]carry[/math] :

Алгоритм работает за [math]O(n)[/math], где [math]n[/math] — длина длинного числа.

Алгоритм не требует дополнительной памяти.

    function getDivLongShort(a: vector<int>, b: int): vector<int>
        carry = 0
        i = a.size() - 1
        while i [math]\geqslant[/math] 0
            cur = a[i] + carry [math]\cdot[/math] base
            a[i] = cur mod base
            carry = cur / base
            i--
        while a.size() > 1 && a.back() == 0
            a.pop_back()
        return a

См. также[править]


Источники информации[править]