Редактирование: Арифметика чисел в b-ичной системе счисления (Длинная арифметика)

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 9: Строка 9:
 
==Представление в памяти==
 
==Представление в памяти==
  
Один из вариантов хранения длинных чисел — массив целых чисел '''int''', где каждый элемент — это одна цифра числа в <tex>b</tex>-ичной системе счисления.
+
Один из вариантов хранения длинных чисел — массив целых чисел <tex>int</tex>, где каждый элемент — это одна цифра числа в ''b''-ичной системе счисления.
Для повышения эффективности каждый элемент вектора может содержать не одну, а несколько цифр (например, работаем в системе счисления по основанию миллиард, тогда каждый элемент вектора содержит <tex>9</tex> цифр):
 
  '''const''' '''int''' base <tex>\,=\,</tex> 1000 <tex>\cdot</tex> 1000 <tex>\cdot</tex> 1000
 
 
 
 
Цифры будут храниться в массиве в следующем порядке: сначала идут наименее значимые цифры (т.е., например, единицы, десятки, сотни, и т.д.).
 
Цифры будут храниться в массиве в следующем порядке: сначала идут наименее значимые цифры (т.е., например, единицы, десятки, сотни, и т.д.).
  
Кроме того, все операции реализуются таким образом, что после выполнения любой из них лидирующие нули (т.е. лишние нули в начале числа) отсутствуют (разумеется, в предположении, что перед каждой операцией лидирующие нули также отсутствуют).
+
Кроме того, все операции реализуются таким образом, что после выполнения любой из них лидирующие нули (т.е. лишние нули в начале числа) отсутствуют (разумеется, в предположении, что перед каждой операцией лидирующие нули также отсутствуют). Следует отметить, что в представленной реализации для числа ноль корректно поддерживаются сразу два представления: пустой вектор цифр, и вектор цифр, содержащий единственный элемент — ноль.
Следует отметить, что в представленной реализации для числа ноль корректно поддерживаются сразу два представления: пустой вектор цифр, и вектор цифр, содержащий единственный элемент — ноль.
 
  
 
==Операции над числами==
 
==Операции над числами==
Строка 22: Строка 18:
 
Операции над числами производятся с помощью "школьных" алгоритмов сложения, вычитания, умножения, деления столбиком.
 
Операции над числами производятся с помощью "школьных" алгоритмов сложения, вычитания, умножения, деления столбиком.
 
После совершения операций следует не забывать удалять лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.
 
После совершения операций следует не забывать удалять лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.
К ним также применимы алгоритмы быстрого умножения: [[Быстрое преобразование Фурье | Быстрое преобразование Фурье]] и [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> :
+
    <font color=green>//Прибавляет к числу a число b и сохраняет результат в a:</font>
 
+
     carry = 0
Алгоритм работает за <tex>O(max(n, m))</tex>, где <tex>n, m</tex> — длины чисел <tex>a</tex> и <tex>b</tex>.
+
    i = 0
 
+
    '''while''' i < max(a.size(),b.size()) || carry
Алгоритм не требует дополнительной памяти.
+
      '''if''' i == a.size()
 
+
        a.push_back (0)
     '''function''' getSum(a: '''vector<int>''', b: '''vector<int>'''): '''vector<int>'''
+
      a[i] += carry + (i < b.size() ? b[i] : 0)
        carry = 0
+
      carry = a[i] <tex>\geqslant</tex> base
        i = 0
+
      '''if''' carry
        '''while''' i < max(a.size(),b.size()) || carry
+
        a[i] -= base
            '''if''' i == a.size()
+
      i++
                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>:
+
    <font color=green>//Отнимает от числа a число b (a \ge b) и сохраняет результат в a:</font>
 
+
     carry = 0
Алгоритм работает за <tex>O(max(n, m))</tex>, где <tex>n, m</tex> — длины чисел <tex>a</tex> и <tex>b</tex>.
+
    i = 0
 
+
    '''while''' i < b.size() || carry
Алгоритм не требует дополнительной памяти.
+
      a[i] -= carry + (i < b.size() ? b[i] : 0)
     '''function''' getSub(a: '''vector<int>''', b: '''vector<int>'''): '''vector<int>'''
+
      carry = a[i] < 0
        carry = 0
+
      '''if''' carry
        i = 0
+
        a[i] += base
        '''while''' i < b.size() || carry
+
      i++
            '''if''' i < b.size()
+
    '''while''' a.size() > 1 && a.back() == 0
                a[i] -= carry + b[i]
+
      a.pop_back()
            '''else'''
+
    <font color=green>//Здесь мы после выполнения вычитания удаляем лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.</font>
                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> :
+
    <font color=green>//Умножает длинное a на короткое b (b < {\rm base}) и сохраняет результат в a:</font>
 +
    carry = 0
 +
    i = 0
 +
    '''while''' i < a.size() || carry
 +
      '''if''' i == a.size()
 +
        a.push_back (0)
 +
      '''long long''' cur = carry + a[i] <tex>\cdot</tex> 1ll <tex>\cdot</tex> b;
 +
      a[i] = cur '''mod''' base
 +
      carry = cur / base
 +
      i++
 +
    '''while''' a.size() > 1 && a.back() == 0
 +
      a.pop_back()
 +
    <font color=green>//Здесь мы после выполнения деления удаляем лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.</font>
  
Алгоритм работает за <tex>O(n)</tex>, где <tex>n</tex> — длина длинного числа.
+
=== Умножение двух длинных чисел ===
 +
    <font color=green>//Умножает a на b и результат сохраняет в c:</font>
 +
    carry = 0
 +
    i = 0
 +
    '''while''' i < a.size()
 +
      j = 0
 +
      '''while''' (j < b.size() || carry)
 +
        '''long long''' cur = c[i+j] + a[i] <tex>\cdot</tex> 1ll <tex>\cdot</tex> (j < (int)b.size() ? b[j] : 0) + carry
 +
        c[i+j] = cur '''mod''' base
 +
        carry = cur / base
 +
        i++
 +
      j++
 +
    '''while''' c.size() > 1 && c.back() == 0
 +
      c.pop_back()
  
Алгоритм требует <tex>O(n)</tex> памяти, где <tex>n</tex> — длина длинного числа.
+
=== Деление длинного на короткое  ===
 +
    <font color=green>//Делит длинное a на короткое b (b < {\rm base}), частное сохраняет в a, остаток в carry:</font>
 +
    carry = 0
 +
    i = a.size()-1
 +
    '''while''' i \geqslant 0
 +
      '''long long''' cur = a[i] + carry <tex>\cdot</tex> 1ll <tex>\cdot</tex> base
 +
        a[i] = cur '''mod''' base
 +
        carry = cur / base
 +
      i--
 +
    '''while''' a.size() > 1 && a.back() == 0
 +
      a.pop_back()
  
    '''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
 
  
=== Умножение двух длинных чисел ===
+
==Подбор значения очередной цифры в алгоритме деления в столбик==
Умножает <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>k \in [0, b)</tex> частного можно производить с помощью стандартного алгоритма двоичного поиска за <tex>\ln(b)</tex>.
  
Алгоритм требует <tex>O(n \cdot m)</tex> памяти, где <tex>n, m</tex> — длины чисел <tex>a</tex> и <tex>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} \geqslant </tex> '''BASE''' <tex>/ 2</tex> (где '''BASE''' — основание системы счисления), то можно доказать следующие факты:
  
    '''function''' getCompLongLong(a: '''vector<int>''', b: '''vector<int>'''): '''vector<int>'''
+
*1. Если положить '''qGuess''' <tex> = (u_n \cdot</tex><tex> </tex> '''BASE''' <tex>+\ u_{n-1}) / b_{n-1}</tex> , то '''qGuess'''<tex>-2 \leqslant q \leqslant</tex> '''qGuess'''.
        carry = 0
+
Иначе говоря, вычисленная таким способом “догадка” будет не меньше искомого частного,
        i = 0
+
но может быть больше на <tex>1</tex> или <tex>2</tex>.
        '''while''' i < a.size()
+
*2. Если же дополнительно выполняется неравенство '''qGuess'''<tex> \cdot b_{n-2} ></tex> '''BASE''' <tex>\cdot r +\ u_{n-2}</tex> , где <tex>r</tex> – остаток при нахождении '''qGuess''' и '''qGuess''' <tex>≠</tex>  '''BASE''', то '''qGuess''' <tex>-1 \leqslant q \leqslant</tex> '''qGuess''', причем вероятность события '''qGuess'''<tex> = q + 1</tex> приблизительно равна <tex>2 / </tex> '''BASE'''.
            j = 0
+
Таким образом, если <tex>b_{n-1} \geqslant </tex> '''BASE'''<tex>/2</tex>, то можно вычислить '''qGuess''' <tex> = (u_n \cdot</tex><tex>\ </tex>'''BASE''' <tex> + u_{n-1}) / b_{n-1}</tex> и уменьшать на единицу до тех пор, пока не станут выполняться условия. Получившееся значение будет либо правильным частным <tex>q</tex>, либо, с вероятностью <tex>2/</tex>'''BASE''', на единицу большим числом.
            '''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>b_{n-1}</tex> слишком мало, чтобы пользоваться таким способом?
Делит длинное <tex>a</tex> на короткое <tex>b\, (b < base)</tex>, частное сохраняет в <tex>a</tex>, остаток в <tex>carry</tex> :
+
Например, можно домножить делитель и делимое на одно и то же число '''scale''' <tex> = </tex> '''BASE'''<tex> / ( b_{n-1} +1 )</tex>. В случае, если основание системы счисления является степенью двойки, '''scale''' можно выбрать соответствующей степенью двойки.
 +
При этом несколько изменится способ вычисления остатка, а частное останется прежним. Такое домножение иногда называют нормализацией числа. На тот случай, если '''qGuess''' получилось все же на единицу большим <tex>q</tex>, будем использовать вычитание, которое вместо отрицательного числа даст дополнение до следующей степени основания. Если такое произошло, то последний перенос будет равен <tex>-1</tex>. Это сигнал, что необходимо прибавить одно B назад.
 +
Заметим, что в конце сложения будет лишний перенос на единицу, о котором нужно забыть (он компенсирует последний перенос <tex>(-1)</tex>).
  
Алгоритм работает за <tex>O(n)</tex>, где <tex>n</tex> — длина длинного числа.
+
[http://forum.sources.ru/index.php?showtopic=210512&hl= Источник]
  
Алгоритм не требует дополнительной памяти.
+
== Источники информации ==
   
+
* [http://e-maxx.ru/algo/big_integer e-maxx: Длинная арифметика]
    '''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
 
  
 
== См. также ==
 
== См. также ==
 
*[[Системы счисления | Системы счисления]]
 
*[[Системы счисления | Системы счисления]]
 
*[[Разложение на множители (факторизация) | Разложение на множители (факторизация)]]
 
*[[Разложение на множители (факторизация) | Разложение на множители (факторизация)]]
 
 
== Источники информации ==
 
* [http://e-maxx.ru/algo/big_integer e-maxx: Длинная арифметика]
 
 
 
[[Категория: Алгоритмы алгебры и теории чисел]]
 
[[Категория: Теория чисел]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: