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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
(Метки: правка с мобильного устройства, правка из мобильной версии)
(Добавлены операции - псевдокод)
(Метки: правка с мобильного устройства, правка из мобильной версии)
Строка 3: Строка 3:
 
Длинная арифметика (англ. ''arbitrary-precision arithmetic'', или ''bignum arithmetic'') — это набор программных средств (структуры данных и алгоритмы), которые позволяют работать с числами гораздо больших величин, чем это позволяют стандартные типы данных.
 
Длинная арифметика (англ. ''arbitrary-precision arithmetic'', или ''bignum arithmetic'') — это набор программных средств (структуры данных и алгоритмы), которые позволяют работать с числами гораздо больших величин, чем это позволяют стандартные типы данных.
 
}}
 
}}
 
+
{{Определение
==Классическая длинная арифметика==
+
|definition=
Основная идея "классической длинной арифметики" заключается в том, что число хранится в виде массива его цифр.
+
Классическая длинная арифметика — длинная арифметика, основная идея которой заключается в том, что число хранится в виде массива его цифр. Цифры могут использоваться из той или иной системы счисления, обычно применяются десятичная система счисления и её степени (десять тысяч, миллиард), двоичная система счисления либо любая другая.
Цифры могут использоваться из той или иной системы счисления, обычно применяются десятичная система счисления и её степени (десять тысяч, миллиард), двоичная система счисления либо любая другая.
+
}}
 
 
 
==Представление в памяти==
 
==Представление в памяти==
  
Один из вариантов хранения длинных чисел — массив целых чисел, где каждый элемент — это одна цифра числа в ''b''-ичной системе счисления.
+
Один из вариантов хранения длинных чисел — массив целых чисел <tex>int</tex>, где каждый элемент — это одна цифра числа в ''b''-ичной системе счисления.
 
Цифры будут храниться в массиве в следующем порядке: сначала идут наименее значимые цифры (т.е., например, единицы, десятки, сотни, и т.д.).
 
Цифры будут храниться в массиве в следующем порядке: сначала идут наименее значимые цифры (т.е., например, единицы, десятки, сотни, и т.д.).
  
 
Кроме того, все операции реализуются таким образом, что после выполнения любой из них лидирующие нули (т.е. лишние нули в начале числа) отсутствуют (разумеется, в предположении, что перед каждой операцией лидирующие нули также отсутствуют). Следует отметить, что в представленной реализации для числа ноль корректно поддерживаются сразу два представления: пустой вектор цифр, и вектор цифр, содержащий единственный элемент — ноль.
 
Кроме того, все операции реализуются таким образом, что после выполнения любой из них лидирующие нули (т.е. лишние нули в начале числа) отсутствуют (разумеется, в предположении, что перед каждой операцией лидирующие нули также отсутствуют). Следует отметить, что в представленной реализации для числа ноль корректно поддерживаются сразу два представления: пустой вектор цифр, и вектор цифр, содержащий единственный элемент — ноль.
  
==Сложение, вычитание, умножение, деление на короткое, деление на длинное==
+
==Операции над числами==
  
 
Операции над числами производятся с помощью "школьных" алгоритмов сложения, вычитания, умножения, деления столбиком.
 
Операции над числами производятся с помощью "школьных" алгоритмов сложения, вычитания, умножения, деления столбиком.
 
После совершения операций следует не забывать удалять лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.
 
После совершения операций следует не забывать удалять лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.
 +
К ним также применимы алгоритмы быстрого умножения: Быстрое преобразование Фурье и Алгоритм Карацубы.
 +
 +
=== Сложение ===
 +
    <font color=green>//Прибавляет к числу a число b и сохраняет результат в a:</font>
 +
    carry = 0
 +
    i = 0
 +
    '''while''' i < max(a.size(),b.size()) || carry
 +
      '''if''' i == a.size()
 +
        a.push_back (0)
 +
      a[i] += carry + (i < b.size() ? b[i] : 0)
 +
      carry = a[i] <tex>\geqslant</tex> base
 +
      '''if''' carry
 +
        a[i] -= base
 +
      i++
 +
=== Вычитание ===
 +
    <font color=green>//Отнимает от числа a число b (a \ge b) и сохраняет результат в a:</font>
 +
    carry = 0
 +
    i = 0
 +
    '''while''' i < b.size() || carry
 +
      a[i] -= carry + (i < b.size() ? b[i] : 0)
 +
      carry = a[i] < 0
 +
      '''if''' carry
 +
        a[i] += base
 +
      i++
 +
    '''while''' a.size() > 1 && a.back() == 0
 +
      a.pop_back()
 +
    <font color=green>//Здесь мы после выполнения вычитания удаляем лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.</font>
 +
=== Умножение длинного на короткое ===
 +
    <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>
 +
 +
=== Умножение двух длинных чисел ===
 +
    <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()
 +
 +
=== Деление длинного на короткое  ===
 +
    <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()
 +
  
 
==Подбор значения очередной цифры в алгоритме деления в столбик==
 
==Подбор значения очередной цифры в алгоритме деления в столбик==
Строка 41: Строка 109:
 
Заметим, что в конце сложения будет лишний перенос на единицу, о котором нужно забыть (он компенсирует последний перенос <tex>(-1)</tex>).
 
Заметим, что в конце сложения будет лишний перенос на единицу, о котором нужно забыть (он компенсирует последний перенос <tex>(-1)</tex>).
  
http://forum.sources.ru/index.php?showtopic=210512&hl=
+
[http://forum.sources.ru/index.php?showtopic=210512&hl= Источник]
  
 
== Источники информации ==
 
== Источники информации ==

Версия 00:33, 12 мая 2018

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


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

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

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

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

Операции над числами

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

Сложение

   //Прибавляет к числу a число b и сохраняет результат в a:
    carry = 0
    i = 0
    while i < max(a.size(),b.size()) || carry
      if i == a.size()
        a.push_back (0)
      a[i] += carry + (i < b.size() ? b[i] : 0)
      carry = a[i] [math]\geqslant[/math] base
      if carry
        a[i] -= base
      i++

Вычитание

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

Умножение длинного на короткое

   //Умножает длинное a на короткое b (b < {\rm base}) и сохраняет результат в a:
    carry = 0
    i = 0
    while i < a.size() || carry
      if i == a.size()
        a.push_back (0)
      long long cur = carry + a[i] [math]\cdot[/math] 1ll [math]\cdot[/math] b;
      a[i] = cur mod base
      carry = cur / base
      i++
    while a.size() > 1 && a.back() == 0
      a.pop_back()
   //Здесь мы после выполнения деления удаляем лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.

Умножение двух длинных чисел

   //Умножает a на b и результат сохраняет в c:
    carry = 0
    i = 0
    while i < a.size()
      j = 0
      while (j < b.size() || carry)
        long long cur = c[i+j] + a[i] [math]\cdot[/math] 1ll [math]\cdot[/math] (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()

Деление длинного на короткое

   //Делит длинное a на короткое b (b < {\rm base}), частное сохраняет в a, остаток в carry:
   carry = 0
   i = a.size()-1
   while i \geqslant 0
     long long cur = a[i] + carry [math]\cdot[/math] 1ll [math]\cdot[/math] base
        a[i] = cur mod base
        carry = cur / base
     i--
   while a.size() > 1 && a.back() == 0
     a.pop_back()


Подбор значения очередной цифры в алгоритме деления в столбик

Подбор следующей цифры [math]k \in [0, b)[/math] частного можно производить с помощью стандартного алгоритма двоичного поиска за [math]\ln(b)[/math].

Но также существуют и более быстрые алгоритмы. Довольно интересный способ состоит в высказывании догадки (qGuess) по первым цифрам делителя и делимого. Понятно, что этих нескольких цифр недостаточно для гарантированно правильного результата, однако неплохое приближение все же получится. Пусть очередной шаг представляет собой деление некоторого [math]U = (u_0, u_1, \cdots, u_n)[/math] на [math]B = (b_0, b_1, \cdots, b_{n-1})[/math]. Если [math]b_{n-1} \geqslant [/math] BASE [math]/ 2[/math] (где BASE — основание системы счисления), то можно доказать следующие факты:

  • 1. Если положить qGuess [math] = (u_n \cdot[/math][math] [/math] BASE [math]+\ u_{n-1}) / b_{n-1}[/math] , то qGuess[math]-2 \leqslant q \leqslant[/math] qGuess.

Иначе говоря, вычисленная таким способом “догадка” будет не меньше искомого частного, но может быть больше на [math]1[/math] или [math]2[/math].

  • 2. Если же дополнительно выполняется неравенство qGuess[math] \cdot b_{n-2} \gt [/math] BASE [math]\cdot r +\ u_{n-2}[/math] , где [math]r[/math] – остаток при нахождении qGuess и qGuess [math]≠[/math] BASE, то qGuess [math]-1 \leqslant q \leqslant[/math] qGuess, причем вероятность события qGuess[math] = q + 1[/math] приблизительно равна [math]2 / [/math] BASE.

Таким образом, если [math]b_{n-1} \geqslant [/math] BASE[math]/2[/math], то можно вычислить qGuess [math] = (u_n \cdot[/math][math]\ [/math]BASE [math] + u_{n-1}) / b_{n-1}[/math] и уменьшать на единицу до тех пор, пока не станут выполняться условия. Получившееся значение будет либо правильным частным [math]q[/math], либо, с вероятностью [math]2/[/math]BASE, на единицу большим числом.

Что делать, если [math]b_{n-1}[/math] слишком мало, чтобы пользоваться таким способом? Например, можно домножить делитель и делимое на одно и то же число scale [math] = [/math] BASE[math] / ( b_{n-1} +1 )[/math]. В случае, если основание системы счисления является степенью двойки, scale можно выбрать соответствующей степенью двойки. При этом несколько изменится способ вычисления остатка, а частное останется прежним. Такое домножение иногда называют нормализацией числа. На тот случай, если qGuess получилось все же на единицу большим [math]q[/math], будем использовать вычитание, которое вместо отрицательного числа даст дополнение до следующей степени основания. Если такое произошло, то последний перенос будет равен [math]-1[/math]. Это сигнал, что необходимо прибавить одно B назад. Заметим, что в конце сложения будет лишний перенос на единицу, о котором нужно забыть (он компенсирует последний перенос [math](-1)[/math]).

Источник

Источники информации

См. также