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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 144: Строка 144:
 
             a.pop_back()
 
             a.pop_back()
 
         '''return''' a
 
         '''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, \ldots, b_{n-1})</tex>.
 +
Если <tex>b_{n-1} \geqslant </tex><tex>\frac{BASE}{2}</tex> (где '''BASE''' — основание системы счисления), то можно доказать следующие факты:
 +
 +
*1. Если положить '''qGuess''' <tex> = \frac{ (u_n \cdot BASE  + \ u_{n-1}) }{ b_{n-1} }</tex> , то '''qGuess'''<tex>-2 \leqslant q \leqslant</tex> '''qGuess'''.
 +
Иначе говоря, вычисленная таким способом “догадка” будет не меньше искомого частного,
 +
но может быть больше на <tex>1</tex> или <tex>2</tex>.
 +
*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>\frac{2}{BASE}</tex>.
 +
Таким образом, если <tex>b_{n-1} \geqslant </tex> <tex>\frac{BASE}{2}</tex>, то можно вычислить '''qGuess''' <tex> = \frac{ (u_n \cdot BASE  + \ u_{n-1}) }{ b_{n-1} }</tex>  и уменьшать на единицу до тех пор, пока не станут выполняться условия. Получившееся значение будет либо правильным частным <tex>q</tex>, либо, с вероятностью <tex>\frac{2}{BASE}</tex>, на единицу большим числом.
 +
 +
Что делать, если <tex>b_{n-1}</tex> слишком мало, чтобы пользоваться таким способом?
 +
Например, можно домножить делитель и делимое на одно и то же число '''scale''' <tex> = \frac{BASE}{b_{n-1} + 1}</tex>. В случае, если основание системы счисления является степенью двойки, '''scale''' можно выбрать соответствующей степенью двойки.
 +
При этом несколько изменится способ вычисления остатка, а частное останется прежним. Такое домножение иногда называют нормализацией числа. На тот случай, если '''qGuess''' получилось все же на единицу большим <tex>q</tex>, будем использовать вычитание, которое вместо отрицательного числа даст дополнение до следующей степени основания. Если такое произошло, то последний перенос будет равен <tex>-1</tex>. Это сигнал, что необходимо прибавить одно B назад.
 +
Заметим, что в конце сложения будет лишний перенос на единицу, о котором нужно забыть (он компенсирует последний перенос <tex>(-1)</tex>).
 +
 +
[http://forum.sources.ru/index.php?showtopic=210512&hl= Источник]
  
 
== См. также ==
 
== См. также ==

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

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

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

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