344
правки
Изменения
источники, см.также, знаки неравенств
правильного результата, однако неплохое приближение все же получится.
Пусть очередной шаг представляет собой деление некоторого <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} \gegeqslant </tex> '''BASE''' <tex>/ 2</tex> (где '''BASE''' — основание системы счисления), то можно доказать следующие факты:
*1. Если положить '''qGuess''' <tex> = (u_n \cdot</tex><tex> </tex> '''BASE''' <tex>+\ u_{n-1}) / b_{n-1}</tex> , то '''qGuess'''<tex>-2 \le leqslant q \leleqslant</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 \le leqslant q \leleqslant</tex> '''qGuess''', причем вероятность события '''qGuess'''<tex> = q + 1</tex> приблизительно равна <tex>2 / </tex> '''BASE'''.Таким образом, если <tex>b_{n-1} \gegeqslant </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''', на единицу большим числом.
Что делать, если <tex>b_{n-1}</tex> слишком мало, чтобы пользоваться таким способом?
http://forum.sources.ru/index.php?showtopic=210512&hl=
== Источники информации ==
* [http://e-maxx.ru/algo/big_integer e-maxx: Длинная арифметика]
== См. также ==
*[[Системы счисления | Системы счисления]]
*[[Разложение на множители (факторизация) | Разложение на множители (факторизация)]]
