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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Умножение длинного на короткое)
(Метки: правка с мобильного устройства, правка из мобильной версии)
(Вычитание)
(Метки: правка с мобильного устройства, правка из мобильной версии)
 
(не показано 25 промежуточных версий этого же участника)
Строка 24: Строка 24:
 
К ним также применимы алгоритмы быстрого умножения: [[Быстрое преобразование Фурье | Быстрое преобразование Фурье]] и [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 Алгоритм Карацубы].
 
К ним также применимы алгоритмы быстрого умножения: [[Быстрое преобразование Фурье | Быстрое преобразование Фурье]] и [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>
  
 
=== Сложение ===
 
=== Сложение ===
Строка 31: Строка 41:
 
Алгоритм работает за <tex>O(max(n, m))</tex>, где <tex>n, m</tex> — длины чисел <tex>a</tex> и <tex>b</tex>.
 
Алгоритм работает за <tex>O(max(n, m))</tex>, где <tex>n, m</tex> — длины чисел <tex>a</tex> и <tex>b</tex>.
  
Алгоритм требует <tex>O(n + m)</tex> памяти, где <tex>n, m</tex> — длины чисел <tex>a</tex> и <tex>b</tex>.
+
Алгоритм не требует дополнительной памяти.
  
     carry = 0
+
     '''function''' getSum(a: '''vector<int>''', b: '''vector<int>'''): '''vector<int>'''
    i = 0
+
        carry = 0
    '''while''' i < max(a.size(),b.size()) || carry
+
        i = 0
      '''if''' i == a.size()
+
        '''while''' i < max(a.size(),b.size()) || carry
        a.push_back(0)
+
            '''if''' i == a.size()
      a[i] += carry + (i < b.size() ? b[i] : 0)
+
                a.push_back(0)
      carry = a[i] <tex>\geqslant</tex> base
+
            '''if''' i < b.size()
      '''if''' carry
+
                a[i] += carry + b[i]
        a[i] -= base
+
            '''else'''
      i++
+
                a[i] += carry
 +
            carry = a[i] <tex>\geqslant</tex> base
 +
            '''if''' carry
 +
                a[i] -= base
 +
            i++
 +
        '''return''' a
  
 
=== Вычитание ===
 
=== Вычитание ===
Строка 49: Строка 64:
 
Алгоритм работает за <tex>O(max(n, m))</tex>, где <tex>n, m</tex> — длины чисел <tex>a</tex> и <tex>b</tex>.
 
Алгоритм работает за <tex>O(max(n, m))</tex>, где <tex>n, m</tex> — длины чисел <tex>a</tex> и <tex>b</tex>.
  
Алгоритм требует <tex>O(n + m)</tex> памяти, где <tex>n, m</tex> — длины чисел <tex>a</tex> и <tex>b</tex>.
+
Алгоритм не требует дополнительной памяти.
    carry = 0
+
    '''function''' getSub(a: '''vector<int>''', b: '''vector<int>'''): '''vector<int>'''
    i = 0
+
        carry = 0
    '''while''' i < b.size() || carry
+
        i = 0
      a[i] -= carry + (i < b.size() ? b[i] : 0)
+
        '''while''' i < b.size() || carry
      carry = a[i] < 0
+
            '''if''' i < b.size()
      '''if''' carry
+
                a[i] -= carry + b[i]
        a[i] += base
+
            '''else'''
      i++
+
                a[i] -= carry
    '''while''' a.size() > 1 && a.back() == 0
+
            carry = a[i] < 0
      a.pop_back()
+
            '''if''' carry
    <font color=green>//Здесь мы после выполнения вычитания удаляем лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.</font>
+
                a[i] += base
 +
            i++
 +
        '''while''' a.size() > 1 && a.back() == 0
 +
            a.pop_back()
 +
        <font color=green>//Здесь мы после выполнения вычитания удаляем лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.</font>
 +
        '''return''' a
  
 
=== Умножение длинного на короткое ===
 
=== Умножение длинного на короткое ===
Строка 67: Строка 87:
 
Алгоритм работает за <tex>O(n)</tex>, где <tex>n</tex> — длина длинного числа.
 
Алгоритм работает за <tex>O(n)</tex>, где <tex>n</tex> — длина длинного числа.
  
Алгоритм требует <tex>O(n \cdot m)</tex> памяти, где <tex>n, m</tex> — длины чисел <tex>a</tex> и <tex>b</tex>.
+
Алгоритм требует <tex>O(n)</tex> памяти, где <tex>n</tex> — длина длинного числа.
  
     carry = 0
+
     '''function''' getCompLongShort(a: '''vector<int>''', b: '''int'''): '''vector<int>'''
    i = 0
+
        carry = 0
    '''while''' i < a.size() || carry
+
        i = 0
      '''if''' i == a.size()
+
        '''while''' i < a.size() || carry
        a.push_back(0)
+
            '''if''' i == a.size()
      cur = carry + a[i] <tex>\cdot</tex> 1ll <tex>\cdot</tex> b;
+
                a.push_back(0)
      a[i] = cur '''mod''' base
+
            cur = carry + a[i] <tex>\cdot</tex> b;
      carry = cur / base
+
            a[i] = cur '''mod''' base
      i++
+
            carry = cur / base
    '''while''' a.size() > 1 && a.back() == 0
+
            i++
      a.pop_back()
+
        '''return''' a
    <font color=green>//Здесь мы после выполнения деления удаляем лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.</font>
 
  
 
=== Умножение двух длинных чисел ===
 
=== Умножение двух длинных чисел ===
Строка 89: Строка 108:
 
Алгоритм требует <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>.
  
     carry = 0
+
     '''function''' getCompLongLong(a: '''vector<int>''', b: '''vector<int>'''): '''vector<int>'''
    i = 0
+
        carry = 0
    '''while''' i < a.size()
+
        i = 0
      j = 0
+
        '''while''' i < a.size()
      '''while''' (j < b.size() || carry)
+
            j = 0
        cur = c[i + j] + a[i] <tex>\cdot</tex> 1ll <tex>\cdot</tex> (j < (int)b.size() ? b[j] : 0) + carry
+
            '''while''' (j < b.size() || carry)
        c[i + j] = cur '''mod''' base
+
                '''if''' j < b.size()
        carry = cur / base
+
                    cur = c[i + j] + a[i] <tex>\cdot</tex> b[j] + carry
        i++
+
                '''else'''
      j++
+
                    cur = c[i + j] + carry
    '''while''' c.size() > 1 && c.back() == 0
+
                c[i + j] = cur '''mod''' base
      c.pop_back()
+
                carry = cur / base
 +
                j++
 +
            i++
 +
        '''while''' c.size() > 1 && c.back() == 0
 +
            c.pop_back()
 +
        '''return''' c
  
 
=== Деление длинного на короткое  ===
 
=== Деление длинного на короткое  ===
Строка 107: Строка 131:
 
Алгоритм работает за <tex>O(n)</tex>, где <tex>n</tex> — длина длинного числа.
 
Алгоритм работает за <tex>O(n)</tex>, где <tex>n</tex> — длина длинного числа.
  
Алгоритм требует <tex>O(n + m)</tex> памяти, где <tex>n, m</tex> — длины чисел <tex>a</tex> и <tex>b</tex>.
+
Алгоритм не требует дополнительной памяти.
 
+
   
    carry = 0
+
    '''function''' getDivLongShort(a: '''vector<int>''', b: '''int'''): '''vector<int>'''
    i = a.size() - 1
+
        carry = 0
    '''while''' i <tex>\geqslant</tex> 0
+
        i = a.size() - 1
      cur = a[i] + carry <tex>\cdot</tex> 1ll <tex>\cdot</tex> base
+
        '''while''' i <tex>\geqslant</tex> 0
      a[i] = cur '''mod''' base
+
            cur = a[i] + carry <tex>\cdot</tex> base
      carry = cur / base
+
            a[i] = cur '''mod''' base
      i--
+
            carry = cur / base
    '''while''' a.size() > 1 && a.back() == 0
+
            i--
      a.pop_back()
+
        '''while''' a.size() > 1 && a.back() == 0
 +
            a.pop_back()
 +
        '''return''' a
  
 
== См. также ==
 
== См. также ==
Строка 126: Строка 152:
 
== Источники информации ==
 
== Источники информации ==
 
* [http://e-maxx.ru/algo/big_integer e-maxx: Длинная арифметика]
 
* [http://e-maxx.ru/algo/big_integer e-maxx: Длинная арифметика]
 +
 +
 +
[[Категория: Алгоритмы алгебры и теории чисел]]
 +
[[Категория: Теория чисел]]

Текущая версия на 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

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


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