c++ - 固定小数点からの平方根の計算

Question

固定小数点データ型から平方根を計算しようとしています<24,8>。
残念ながら、何も機能していないようです。
C(++)でこれを高速かつ効率的に行う方法を知っている人はいますか?

Answer 1

これは、ニュートン法を使用して固定小数点で平方根を計算する方法を示す 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ビット ステップでオーバーフローします。//また、Python の整数除算であることにも注意してください。