344
правки
Изменения
английские термины, <tex>
{{Определение
|definition=
Длинная арифметика (англ. ''arbitrary-precision arithmetic'', или ''bignum arithmetic'') — это набор программных средств (структуры данных и алгоритмы), которые позволяют работать с числами гораздо больших величин, чем это позволяют стандартные типы данных.
}}
правильного результата, однако неплохое приближение все же получится.
Пусть очередной шаг представляет собой деление некоторого <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><tex> </tex> '''BASE''' <tex>+ \ u_{n-1}) / b_{n-1}</tex> , то '''qGuess'''<tex>-2 \le q \le</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 q \le</tex> '''qGuess''', причем вероятность события '''qGuess''' <tex> = q + 1 </tex> приблизительно равна <tex>2 / </tex> '''BASE'''.Таким образом, если <tex>b_{n-1} \ge</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> слишком мало, чтобы пользоваться таким способом?
Например, можно домножить делитель и делимое на одно и то же число '''scale'''<tex> =</tex> '''BASE'''<tex> / ( 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=
