CODEWITHSUNDEEP
c++fixed-pointsquare-root
Alex van Rijs
Alex van Rijs

Reputation: 813

Computing square root from fixed point

I have been trying to compute the square root from a fixed point data-type <24,8>.
Unfortunately nothing seems to work.
Does anyone know how to do this fast and efficient in C(++)?

Upvotes: 0

Views: 3837

Answers (1)

Nick Craig-Wood
Nick Craig-Wood

Reputation: 54117

Here is a prototype in Python showing how to do a square root in fixed point using Newton's method.

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()

When converting this to C++ be really careful about the types – in particular n_one needs to be a 64 bit type or otherwise it will overflow on the <<8 bit step. Note also that // is an integer divide in python.

Upvotes: 3

Related Questions