在科學運算、圖形學、游戲等很多領域中，開方是很常見卻又非常耗時的運算，因此必須使用快速（有時還要求準確）的開方演算法，
說起開方演算法我們一般想到的是牛頓迭代法，這里我介紹一種更好的方法——逐位元確認法，
逐位元確認法從數字的本質出發，關注結果的每一位元位，它從最高位開始，向低位逐一確認某位是0還是1，在數字很大時這種方法的速度比牛頓法快不少，
要理解這種方法，得先了解二進制乘法，例如，對于數字10（二進制為0b1010），平方為100（二進制為1100100），它的二進制平方運算程序為：
1010
X 1010
___________
1010x1000
+ 1010x 10
===========
1000x1000 (*1)
+ 10x1000 (*2)
+ 1000x 10 (*3)
+ 10x 10 (*4)
===========
1000000
+ 10000
+ 10000
+ 100
===========
= 1100100開方則需要我們反過來，已經有結果N = 1100100，判斷根sqrt的二進制：
首先1100100有8位，可以判斷sqrt起碼有4位且不超過4位，如果sqrt有5位，那么僅最高位10000*10000 = 1 0000 0000就已經大于N；如果sqrt只有3位，即使sqrt為111結果110001也不超過6位，
現在判斷sqrt的第4位：如果第4位為1 , sqrt平方運算中有上面（*1）這項
1000
X 1000
==========
1000x1000 (*1)
==========
= 1000000 (n4) < 1100100 (N)結果 n4 < N ，容易判斷，第4位一定為1，不然乘不出N這么大的數，
現在判斷sqrt的第3位：如果第3位為1，則sqrt為1100，它的平方為
1100
X 1100
==========
1000x1000 (*1)
100x1000
1000x 100
100x 100
==========
= 10010000 (n43) > 1100100 (N)結果n43 > N，所以這一位不是1，只能是0，
到目前為止其實都是二分法的思路，先是2^3，然后是2^3 – (2^3 + 2^2)，這樣逐次將范圍減半，
但是這里有個問題，后面每次都求了sqrt的平方，其實重復求了之前求過的一部分，例如在第二步中，我們算了 1000x1000(*1)，這其實就是第一步中的算的，如果我們每次算完平方，確認了這一位為1后，就從N中減去這一部分的平方，那么下次比較大小的時候就可以少算這一位，
我們從第二步重新開始:
我們第一步確認了1000, 從N中減去它的平方 N = 1100100 - n4，結果為N = 1000100，
如果第3位為1, 那么sqrt = 1100, 已確認的為1000, 正在確認的為100, 平方為:
1100
X 1100
===========
(1000x1000)(已確認部分從N減去了,不計算)
+ 100x1000 (正在確認的*已確認的)
+ 1000x 100 (已確認的*正在確認的)
+ 100x 100 (正在確認的*正在確認的)
===========
2*(1000<<2) (1000*100 等于將1000左移2位)
+ 100<<2
===========
= 1010000 (n3) > 1000100 (N*)和之前結果一樣, 大了,所以第3位為0. 因為是0, 所以沒必要從N*里減去.
現在判斷第2位: 如果為1 則sqrt = 1010.
1010
X 1010
===========
(1000x1000)(已確認部分從N減去了,不計算)
+ 10x1000 (正在確認的*已確認的 = 將已確認部分前移1位)
+ 1000x 10 (已確認的*正在確認的 = 將已確認部分前移1位)
+ 10x 10 (正在確認的*正在確認的 = 將正在確認的前移1位)
===========
2*(1000<<1)
+ 10<<1
===========
= 1000100 (n2) = 1000100 (N*)n2 = N*, 也就是說若這一位為1, sqrt就是N的根. 后面應該都是0,無需繼續判斷.
但我還想繼續探究, 繼續把N減去新確認的部分: N* = 1000100 – n2 = 0，
如果第1位為1，則sqrt= 1011, 平方運算為：
1011
X 1011
===========
(1000x1000) (已確認部分從N減去了,不計算)
( 10x1000) (已確認部分從N減去了,不計算)
(1000x 10) (已確認部分從N減去了,不計算)
( 10x 10 ) (已確認部分從N減去了,不計算)
+ 1x1010 (正在確認的*已確認的 = 將已確認部分前移0位)
+ 1010x 1 (已確認的*正在確認的 = 將已確認部分前移0位)
+ 1x 1 (正在確認的*正在確認的 = 將正在確認的前移0位)
===========
2*(1010<<0)
+ 1<<0
===========
= 10101 (n2) > 0 (N*)所以這一位肯定只能為0. 最終結果為sqrt = 1010.
這就是逐位元確認法，
說了這么多，其實代碼很簡單：
1 int sqrt_bv(int n)
2 {
3 int sqrt = 0;
4 int shift = 15;
5 int sqrt2; //已確認部分的平方
6 while (shift >= 0)
7 {
8 sqrt2 = ((sqrt << 1) + (1 << shift)) << shift;
9 if (sqrt2 <= n)
10 {
11 sqrt += (1 << shift);
12 n -= sqrt2;
13 }
14 shift--;
15 }
16 return sqrt;
17 }
此文章首發于我的個人網站：三種高效的整數開平方演算法
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/103926.html
標籤：其他