153
правки
Изменения
→Подбор значения очередной цифры в алгоритме деления в столбик
Подбор следующей цифры <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, \cdots, b_{n-1})</tex>.
Если <tex>b_{n-1} \ge</tex> '''BASE''' <tex>/2</tex> ('''BASE''' — основание системы счисления), то можно доказать следующие факты:
*1. Если положить '''qGuess''' <tex> = (u_n \cdot </tex> '''BASE''' <tex>+ u_{n-1}) / b_{n-1}</tex> , то '''qGuess'''<tex>-2 \le q \le</tex> '''qGuess'''.
Иначе говоря, вычисленная таким способом “догадка” будет не меньше искомого частного,
но может быть больше на 1 или 2.
*2. Если же дополнительно выполняется неравенство '''qGuess'''<tex> \cdot b_{n-2} ></tex> '''BASE''' <tex>\cdot r + u_{n-2}</tex> , где r – остаток при нахождении '''qGuess''' и '''qGuess''' ≠ '''BASE''', то '''qGuess''' <tex>-1 \le q \le</tex> '''qGuess''', причем вероятность события '''qGuess''' = q + 1 приблизительно равна 2 / '''BASE'''.
Таким образом, если <tex>b_{n-1} \ge</tex> '''BASE'''<tex>/2</tex>, то можно вычислить '''qGuess''' <tex> = (u_n \cdot</tex>'''BASE''' <tex> + u_{n-1}) / b_{n-1}</tex> и уменьшать на единицу до тех пор, пока не станут выполняться условия. Получившееся значение будет либо правильным частным q, либо, с вероятностью 2/'''BASE''', на единицу большим числом.
Что делать, если <tex>b_{n-1}</tex> слишком мало, чтобы пользоваться таким способом?
Например, можно домножить делитель и делимое на одно и то же число '''scale'''='''BASE'''<tex> / ( b_{n-1} +1 )</tex>.
При этом несколько изменится способ вычисления остатка, а частное останется прежним. Такое домножение иногда называют нормализацией числа. На тот случай, если '''qGuess''' получилось все же на единицу большим q, будем использовать вычитание, которое вместо отрицательного числа даст дополнение до следующей степени основания. Если такое произошло, то последний перенос будет равен -1. Это сигнал, что необходимо прибавить одно B назад.
Заметим, что в конце сложения будет лишний перенос на единицу, о котором нужно забыть (он компенсирует последний перенос (-1)).
http://forum.sources.ru/index.php?showtopic=210512&hl=
