Given a positive integer , design an algorithm for computing
.
取底符號定義：
給定n(n為正整數)，利用牛頓迭代法求n之平方根：。
- 首先任意定x的值(x只要介於1~n之間都可以)，例如我們可以定：
、
等
- 計算
- 如果
，由於y和x之間誤差超級小,那y和x整數部分一定一樣,取x的整數部分就是n開根號所要的答案，得到答案即可停止迴圈
否則就把，繼續重複步驟2
- 由於他的運算速度依照x初始值，所以沒有明確的時間複雜度(4位數以上的複雜度接近O(log N))。
- 適當的x初始值可以快速地把答案算出來