Square root program on single chip microcomputer

Due to work needs , I need to implement square root operation on a single chip microcomputer. Currently, most of the methods for square root are Newton's iteration method. After checking some information, I found a method that is faster than Newton's iteration method. I dare not keep it to myself, so I introduce it to you, hoping it will be helpful.

1. Principle
For typesetting reasons, pow(X,Y) is used to represent X raised to the power of Y, and B[0], B[1], ..., B[m-1] is used to represent a sequence,
where [x] is the subscript.

Assumptions:
B[x], b[x] are both binary sequences, taking values ​​0 or 1.
M = B[m-1]*pow(2,m-1) + B[m-2]*pow(2,m-2) + ... + B[1]*pow(2,1) + B[0]*pow
(2,0)
N = b[n-1]*pow(2,n-1) + b[n-2]*pow(2,n-2) + ... + b[1]*pow(2,1) + n[0]*pow
(2,0)
pow(N,2) = M

(1) The highest bit b[n-1] of N can be directly obtained from the highest bit B[m-1] of M.
Assume m is known, since pow(2, m-1) <= M <= pow(2, m), then pow(2, (m-1)/2) <= N <=
pow(2, m/2)
If m is odd, let m=2*k+1,
then pow(2,k) <= N < pow(2, 1/2+k) < pow(2, k+1),
n-1=k, n=k+1=(m+1)/2If
m is even, let m=2k,
then pow(2,k) > N >= pow(2, k-1/2) > pow(2, k-1),
n-1=k-1,n=k=m/2So
b[n-1] is completely determined by B[m-1].
Remainder M[1] = M - b[n-1]*pow(2, 2*n-2)

(2) The second highest bit b[n-2] of N can be determined by trial and error.
Since b[n-1]=1, assuming b[n-2]=1, then pow(b[n-1]*pow(2,n-1) + b[n-1]*pow(2,n-2),
2) = b[n-1]*pow(2,2*n-2) + (b[n-1]*pow(2,2*n-2) + b[n-2]*pow(2,2*n-4)),
and then compare whether the remainder M[1] is greater than or equal to (pow(2,2)*b[n-1] + b[n-2]) * pow(2,2*n-4). This
comparison can be made based on B[m-1], B[m-2], ..., B[2*n-4], and the other lower bits are not compared.
If M[1] >= (pow(2,2)*b[n-1] + b[n-2]) * pow(2,2*n-4), then assume valid, b[n-2] =
1;
remainder M[2] = M[1] - pow(pow(2,n-1)*b[n-1] + pow(2,n-2)*b[n-2], 2) = M[1] -
(pow(2,2)+1)*pow(2,2*n-4);
if M[1] < (pow(2,2)*b[n-1] + b[n-2]) * pow(2,2*n-4), then assume invalid, b[n-2] =
0; remainder M[2] = M[1].

(3) Similarly, we can find each digit of the square root N of M from high to low.

When using this algorithm to calculate the square root of a 32-bit number, only 16 comparisons are required at most, and each comparison does not require
comparing each bit of M one by one, especially at the beginning when the number of bits to be compared is very small, so the time consumed is much lower than the Newton iteration method.

2. Flowchart
(under construction, to be uploaded later)

3. Implementation code
Here is the C language code to implement the square root of a 32-bit unsigned integer to get a 16-bit unsigned integer.

------------------------------------------------------------------------------- - /********************************************/ /*Function: Square root processing*/ /*Entry parameter: radicand, long integer*/ /*Exit parameter: square root result, integer*/ /********************************************/ unsigned int sqrt_16(unsigned long M) { unsigned int N, i; unsigned long tmp, ttp; // Result, loop countif (M == 0) // radicand, square root result is also 0 return 0; N = 0; tmp = (M >> 30); // Get the highest bit: B[m-1] M <<= 2; if (tmp > 1) // The highest bit is 1 { N ++; // The current bit of the result is 1, otherwise it is the default 0 tmp -= N; } for (i=15; i>0; i--) // Find the remaining 15 bits { N <<= 1; // Shift left one bit tmp <<= 2; tmp += (M >> 30); // Assume ttp = N; ttp = (ttp<<1)+1; M <<= 2; if (tmp >= ttp) // Assumption holds { tmp -= ttp; N ++; } } return N; }