Programming Lab 11E Q16 Square Root

Programming Lab 11E
Q16 Square Root
Topics: Q16 fixed-point arithmetic, square root by abacus algorithm.
Prerequisite Reading: Chapters 1-11

Click to download
Lab11E-Main.c
Background: A real number 𝑋 is represented in Q16 format by an integer that
is the product of 𝑋 and 2
16
. Since the representation is actually an integer, a
simple modification of an integer square root algorithm may be used to compute
the Q16 square root:
Let 𝑋 and 𝑅 be real numbers, where:
𝑅 = √𝑋 (1)
In Q16 format, 𝑋 and 𝑅 are represented by integers 𝑁𝑥 and 𝑁𝑅, where:
𝑋 = 𝑁𝑋 2
16 ⁄ and 𝑅 = 𝑁𝑅 2
16 ⁄ (2,3)
Substituting (2) and (3) into (1) yields:
𝑁𝑅 2
16 ⁄ = √𝑁𝑋 2⁄ 16 (4)
Multiplying both sides by 2
16 gives:
𝑁𝑅 = 2
16√𝑁𝑋 2⁄ 16 = 2
8√𝑁𝑋 (5)
I.e., the square root of a Q16 real number 𝑋 may be computed as the integer square root of 𝑁𝑋, shifted left 8 bits.
Assignment: The main program includes two C functions that are modified versions of an “digit-by-digit” algorithm for
computing the integer square root that was originally developed for use with an abacus1
:
typedef int32_t Q16 ;
Q16 Q16GoodRoot(Q16 radicand) ; // Resolution: about ±.001 (implementation required)
Q16 Q16BestRoot(Q16 radicand) ; // Resolution: about ±.0001 (optional for extra credit)
Note: The main program may be compiled and executed without writing any assembly. However, your task is to create
faster assembly versions of these two functions using the C versions to guide your implementation. The original C functions
have been defined as “weak”, so that the linker will automatically replace them in the executable image by those you create
in assembly; there is no need to remove the C versions. Both C functions call an intrinsic function named __CLZ; your
assembly language version may replace each call by a CLZ instruction.
Suggestion: Code and test your replacement functions one at a time in the order shown above. If your code is correct, the
display should look like the image shown. The program displays square roots computed by the two Q16 functions as well
as that computed by the single precision sqrtf function from gcc’s floating-point library. The horizontal axis of each graph
covers the entire range of non-negative Q16 values, while the vertical axis is the square root. For comparison, each graph
also shows the numeric values computed for the square root of 2 and the square root of the maximum Q16 value.
1 https://web.archive.org/web/20120306040058/http://medialab.freaknet.org/martin/src/sqrt/sqrt.c