"Square root is required in C language. You can add #include math. H to the header file. Then call sqrt (n). Function. However, calling this function in SCM will undoubtedly consume a lot of resources and time, which is extremely inappropriate. Here, we summarize four common square root algorithms of single chip microcomputer on the Internet:
For the single chip microcomputer with special multiplication and division instructions, the following two methods can be adopted:
1. Dichotomy
For a non negative number n, its square root will not be less than (n / 2 + 1) (thanks @linzhi-cs for reminding). In the range of [0, N / 2 + 1], the binary search can be carried out to find the square root of n.
-------------------------------------------------------------------------------
1 int sqrt（int x） { 2 long long i = 0; 3 long long j = x / 2 + 1; 4 while （i 《= j） 5 { 6 long long mid = （i + j） / 2; 7 long long sq = mid * mid; 8 if （sq == x） return mid; 9 else if （sq 《 x） i = mid + 1; 10 else j = mid - 1; 11 }12 return j; 13 }
-------------------------------------------------------------------------------
2. More commonly used Newton iterative method
-------------------------------------------------------------------------------
1 int sqrt（int x） { 2 if （x == 0） return 0; 3 double last = 0; 4 double res = 1; 5 while （res ！= last） 6 { 7 last = res; 8 res = （res + x / res） / 2; 9 }10 return int（res）; 11 }
-------------------------------------------------------------------------------
Newton iterative method can also solve multiple equations.
For the single chip microcomputer without multiplication and division instruction, the following two algorithms can be adopted:
Algorithm 3:
This algorithm only uses shift, addition and subtraction, judgment and loop, because it does not need floating-point operation, multiplication and division, so it can be easily applied to various chips.
Let's take a look at how to manually calculate the square under base 10:
Let's first look at the following two formulas:
x = 10*p + q （1）
After the left and right squares of formula (1), we get:
x^2 = 100*p^2 + 20pq + q^2 （2）
Now suppose we know x ^ 2 and P and want to find Q. if we find Q, we will find the square X of x ^ 2.
We rewrite formula (2) into the following format:
q = （x^2 - 100*p^2）/（20*p+q） （3）
This formula has Q on both sides, so it is impossible to calculate Q directly. Therefore, the manual square algorithm needs to guess the value in one step like the manual division algorithm.
Let's take an example of manual calculation: calculate the square of 1234567890
First, we divide the number into two digits and calculate that the highest bit is 3. That is, P in (3), 334 in the bottom line is the remainder, that is, the approximate value of (x ^ 2 - 100 * P ^ 2) in formula (3)
3 --------------- | 12 34 56 78 90 9 --------------- | 3 34
Next, we need to find a number Q of 0-9 to make it closest to satisfying formula (3). Let's multiply P by 20 and write it on the left of 334:
3 q --------------- | 12 34 56 78 90 9 --------------- 6q| 3 34
We see that when q is 5 (60 + Q * q), the value is closest to 334 and does not exceed 334. So we get:
3 5 --------------- | 12 34 56 78 90 9 --------------- 65| 3 34 | 3 25 --------------- 9 56
The next step is to repeat the above steps, so I won't be wordy here.
In fact, this manual algorithm has little to do with hexadecimal, so we can easily change it to binary. After changing it to binary, formula (3) becomes:
q = （x^2 - 4*p^2）/（4*p+q） （4）
Let's take an example to calculate the square of 100 (binary 1100100):
1 0 1 0 --------------- | 1 10 01 00 1 --------------- 100| 0 10 | 0 00 --------------- | 10 011001| 10 01 --------------- 0 00
Each step here is no longer to multiply P by 20, but to multiply P by 4, that is, to move P right by two digits. Since the value of Q can only be 0 or 1, we only need to judge the size relationship between the remainder (x ^ 2 - 4 * P ^ 2) and (4 * P + 1). If the remainder is greater than or equal to (4 * P + Q), then the previous 1, otherwise the previous 0.
The completed C language program is given below, where root represents P, REM represents the remainder after each step of calculation, and director represents (4 * P + 1). Take the highest 2 bits of a through a 30, and eliminate the highest 2 bits after calculation through a = 2. Root's twice "1" is equivalent to 4 * P. The program is completely rewritten according to manual calculation, which should not be difficult to understand.
-------------------------------------------------------------------------------
unsigned short sqrt（unsigned long a）{ unsigned long rem = 0; unsigned long root = 0; unsigned long divisor = 0; for（int i=0; i《16; i++）{ root 《《= 1; rem = （（rem 《《 2） + （a 》》 30））; a 《《= 2; divisor = （root《《1） + 1; if（divisor 《= rem）{ rem -= divisor; root++; } } return （unsigned short）（root）; }
-------------------------------------------------------------------------------
Algorithm 4
This method is faster than Newton iterative method.
1. Principle
Below, pow (x, y) is used to represent the Y power of X, and B [0], B [1] are used,..., B [M-1] represents a sequence,
Where [x] is the subscript.
Assumptions:
B [x] and B [x] are binary sequences, with values of 0 or 1.
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）
2、 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）
3、 pow（N，2） = M
(1) The highest bit B [n-1] of N can be obtained directly from the highest bit B [M-1] of M.
Let m be known, because pow (2, m-1) "= m" = pow (2, m), pow (2, (m-1) / 2) "= n"=
pow（2， m/2）
If M is an odd number, 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）/2
If M is an even number, let m = 2K,
Then pow (2, K) "n" = pow (2, k-1 / 2) "pow (2, k-1),
n-1=k-1，n=k=m/2
So 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 heuristic method.
Because B [n-1] = 1, assuming B [n-2] = 1, 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）），
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). such
The comparison only needs to be based on B [M-1], B [m-2] B [2 * n-4] can make judgment, and the other low positions are not compared.
If M [1] = (pow (2,2) * B [n-1] + B [n-2] * pow (2,2 * n-4), it is assumed to be 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), the assumption is invalid, B [n-2]=
0 Remainder m [2] = m [1].
(3) Similarly, the bits of the square root n of M can be found bit by bit from high to low.
When using this algorithm to calculate the square root of 32 bits, it only needs to compare 16 times at most, and it is not necessary to compare the bits of m one by one each time
A comparison, especially at the beginning, has few bits, so the time consumed is much lower than that of Newton iterative method.
2. Implementation code
Here is the C language code to square a 32-bit unsigned integer to get a 16 bit unsigned integer.
-------------------------------------------------------------------------------
/****************************************// * function: root opening processing * / / * entry parameters: the number of squares to be opened, long integer * / / * exit parameters: the result of square opening, integer * / ************************************************** / unsigned int sqrt_ 16（unsigned long M） { unsigned int N， i; unsigned long tmp， ttp; // Result: cycle count if (M = = 0) / / the number of squares to be opened, and the square 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// Move 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; }
-------------------------------------------------------------------------------
The above algorithms are collected online at the end. Although the principle may be difficult to understand, they can be used in MCU.
Editor in charge: CC, read the full text“
Our other product:
