Длинный алгоритм квадратного корня
Оказывается, существует алгоритм вычисления квадратных корней, который вы можете вычислить вручную, что-то вроде длинного деления. Каждая итерация алгоритма производит ровно одну цифру полученного квадратного корня, потребляя две цифры числа, квадратный корень которого вы ищете. В то время как «длинная рука» версия алгоритма указана в десятичной системе, она работает в любой базе, причем бинарность является самой простой для реализации и, возможно, самой быстрой для выполнения (в зависимости от базового представления bignum).
этот алгоритм работает с цифрами по цифрам, он дает точные результаты для произвольно больших совершенных квадратов, а для не-идеальных квадратов может потребоваться столько цифр точности (справа от десятичной точки), сколько желательно.
На сайте «Dr. Math» есть два замечательных отчета, которые объясняют алгоритм:
И вот реализация в Python:
def exact_sqrt(x):
"""Calculate the square root of an arbitrarily large integer.
The result of exact_sqrt(x) is a tuple (a, r) such that a**2 + r = x, where
a is the largest integer such that a**2 <= x, and r is the "remainder". If
x is a perfect square, then r will be zero.
The algorithm used is the "long-hand square root" algorithm, as described at
http://mathforum.org/library/drmath/view/52656.html
Tobin Fricke 2014-04-23
Max Planck Institute for Gravitational Physics
Hannover, Germany
"""
N = 0 # Problem so far
a = 0 # Solution so far
# We'll process the number two bits at a time, starting at the MSB
L = x.bit_length()
L += (L % 2) # Round up to the next even number
for i in xrange(L, -1, -1):
# Get the next group of two bits
n = (x >> (2*i)) & 0b11
# Check whether we can reduce the remainder
if ((N - a*a) << 2) + n >= (a<<2) + 1:
b = 1
else:
b = 0
a = (a << 1) | b # Concatenate the next bit of the solution
N = (N << 2) | n # Concatenate the next bit of the problem
return (a, N-a*a)
Вы можете легко изменить эту функцию, чтобы провести дополнительные итерации до вычислить дробную часть квадратного корня. Меня больше всего интересовали вычисления корней больших совершенных квадратов.
Я не уверен, как это сравнивается с алгоритмом «целочисленный метод Ньютона». Я подозреваю, что метод Ньютона быстрее, поскольку он может в принципе генерировать несколько бит решения на одной итерации, тогда как алгоритм «длинной руки» генерирует ровно один бит решения на итерацию.
Source repo: https://gist.github.com/tobin/11233492