Because of the need to work, to achieve open radical operation in scm. Currently open square method is mostly used Newton. Iterative method. After looking up some information, I found a more rapid method than Newton iteration method. Not exclusive, medium Shao to everyone, hope will be some help.
- Principles - Because of the reasons for the layout, with pow (X, Y) that the power of the Y X, with B, B,..., B[m-1] said a sequence,
Where [x] is the subscript.
Hypothesis: B[x], B[x] is a binary sequence, the value of 0 or 1.
M = B[m-1]*pow (2, m-1) + B[m-2]*pow (2, m-2) + + B*pow (2,1) + B*pow (2,0)
N = b[n-1]*pow (2, n-1) + b[n-2]*pow (2, n-2) + + b*pow (2,1) + n*pow (2,0)
Pow (N, 2) = M
- The most high b[n-1] M can be directly obtained according to the highest B[m-1] N.
M known, because pow (2, M-1 < = M) < = pow (2, m), and pow (2, /2 (m-1) < < = N)
Pow (2, m/2)
If M is odd, set m=2*k+1,
Then the pow (2, K) (POW < 2, N < = 1/2+k) < pow (2, k+1),
N-1=k, n=k+1= (m+1) /2
If M is even, let m=2k,
Then the pow (2, K) > N > = pow (2, k-1/2) > pow (2, k-1),
So b[n-1] is completely determined by B[m-1].
The remainder of M = M - b[n-1]*pow (2, 2*n-2)
- The second high position of b[n-2] N can be determined by heuristic method. Because b[n-1]=1, assuming b[n-2]=1, then pow (b[n-1]*pow) + b[n-1]*pow (2, n-1) + (2, n-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 the remainder is greater than or equal to M (pow (2,2) *b[n-1] + b[n-2]) * pow (2,2*n-4). such
Compare only according to B[m-1], B[m-2],..., B[2*n-4] can make judgments, and the rest of the low do not compare.
If M > = (pow (2,2) *b[n-1] + b[n-2]) * pow (2,2*n-4), it is assumed that b[n-2] = effective.
The remainder of M = M - pow (pow (2, n-1) *b[n-1] + pow (2, n-2) *b[n-2], M = - 2)
(pow (2,2) +1 () *pow (2,2*n-4);
If M < (*b[n-1] (2,2) POW + b[n-2]) * pow (2,2*n-4), then the assumption is invalid, b[n-2] = 0; M = M.
- In the same way, we can find out the square root N of M from high to low bit by bit.
Using this algorithm to calculate the square root of the 32 digit when the maximum number of only 16 times, and each time you do not have to compare the M
A comparison, especially at the beginning of a relatively small number of bits, so the time consumption is much lower than the Newton iteration method.
- Flow Chart - (in the production, wait a minute)
- Implementation Code - Here are 32 bit unsigned integer square 16 bit unsigned integer code in C language.