Вычисление квадратного корня из фиксированной точки

Вот прототип в Python, показывающий, как сделать квадратный корень в фиксированной точке используя метод Ньютона.

import math

def sqrt(n, shift=8):
"""Return the square root of n as a fixed point number.  It uses a
second order Newton-Raphson convergence.  This doubles the number
of significant figures on each iteration.

Shift is the number of bits in the fractional part of the fixed
point number.
"""# Initial guess - could do better than this
x = 1 << shift // 32 bit type
n_one = n << shift // 64 bit type
while 1:
x_old = x
x = (x + n_one // x) // 2
if x == x_old:
break
return x

def main():
a = 4.567
print "Should be", math.sqrt(a)
fp_a = int(a * 256)
print "With fixed point", sqrt(fp_a)/256.

if __name__ == "__main__":
main()

При преобразовании этого в C ++ будьте очень осторожны с типами — в частности n_one должен быть 64-битным типом, иначе он будет переполнен на <<8 немного шаг. Обратите внимание, что // целочисленное деление в питоне