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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 9: Строка 9:
 
==Представление в памяти==
 
==Представление в памяти==
  
Один из вариантов хранения длинных чисел — массив целых чисел '''int''', где каждый элемент — это одна цифра числа в <tex>b</tex>-ичной системе счисления.
+
Один из вариантов хранения длинных чисел — массив целых чисел '''int''', где каждый элемент — это одна цифра числа в ''b''-ичной системе счисления.
 
Для повышения эффективности каждый элемент вектора может содержать не одну, а несколько цифр (например, работаем в системе счисления по основанию миллиард, тогда каждый элемент вектора содержит <tex>9</tex> цифр):  
 
Для повышения эффективности каждый элемент вектора может содержать не одну, а несколько цифр (например, работаем в системе счисления по основанию миллиард, тогда каждый элемент вектора содержит <tex>9</tex> цифр):  
 
   '''const''' '''int''' base <tex>\,=\,</tex> 1000 <tex>\cdot</tex> 1000 <tex>\cdot</tex> 1000
 
   '''const''' '''int''' base <tex>\,=\,</tex> 1000 <tex>\cdot</tex> 1000 <tex>\cdot</tex> 1000
Строка 22: Строка 22:
 
Операции над числами производятся с помощью "школьных" алгоритмов сложения, вычитания, умножения, деления столбиком.
 
Операции над числами производятся с помощью "школьных" алгоритмов сложения, вычитания, умножения, деления столбиком.
 
После совершения операций следует не забывать удалять лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.
 
После совершения операций следует не забывать удалять лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.
К ним также применимы алгоритмы быстрого умножения: [[Быстрое преобразование Фурье | Быстрое преобразование Фурье]] и [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 Алгоритм Карацубы].
+
К ним также применимы алгоритмы быстрого умножения: Быстрое преобразование Фурье и Алгоритм Карацубы.
  
 
Приведённые ниже алгоритмы корректны в силу того, что они являются реализацией "школьных" алгоритмов действий в столбик:
 
Приведённые ниже алгоритмы корректны в силу того, что они являются реализацией "школьных" алгоритмов действий в столбик:
Строка 60: Строка 60:
  
 
=== Вычитание ===
 
=== Вычитание ===
Отнимает от числа <tex>a</tex> число <tex>b\,(a \geqslant b)</tex>  и сохраняет результат в <tex> a</tex>:
+
Отнимает от числа <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>.
 
Алгоритм работает за <tex>O(max(n, m))</tex>, где <tex>n, m</tex> — длины чисел <tex>a</tex> и <tex>b</tex>.
Строка 83: Строка 83:
  
 
=== Умножение длинного на короткое ===
 
=== Умножение длинного на короткое ===
Умножает длинное <tex>a</tex> на короткое <tex>b\, (b < base)</tex> и сохраняет результат в <tex>a</tex> :
+
Умножает длинное <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> — длина длинного числа.
Строка 127: Строка 127:
  
 
=== Деление длинного на короткое  ===
 
=== Деление длинного на короткое  ===
Делит длинное <tex>a</tex> на короткое <tex>b\, (b < base)</tex>, частное сохраняет в <tex>a</tex>, остаток в <tex>carry</tex> :
+
Делит длинное <tex>a</tex> на короткое <tex>b (b < base)</tex>, частное сохраняет в <tex>a</tex>, остаток в <tex>carry</tex> :
  
 
Алгоритм работает за <tex>O(n)</tex>, где <tex>n</tex> — длина длинного числа.
 
Алгоритм работает за <tex>O(n)</tex>, где <tex>n</tex> — длина длинного числа.

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

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

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

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