---
title: 計算根號
tags: math, number theory
---

# 計算根號

* 已知 $k$ 值，求 $\sqrt k$ 的值為何？

$x=\sqrt k\Rightarrow x^2=k$

$f(x)=x^2-k, f'(x)=2x$

$x_{n+1}=x_n-\cfrac{x_n^2-k}{2x_n}=\cfrac{x_n^2-k}{2x_n}=0.5(x_n+k/x_n)$

---

一個更好的假設法 ── 倒數：

$x=\cfrac{1}{\sqrt k}\Rightarrow \cfrac{1}{x^2}=k$

$f(x)=\cfrac{1}{x^2}-k, f'(x)=\cfrac{-2}{x^3}$

$x_{n+1}=x_n-\cfrac{1/x_n^2-k}{-2/x_n^3}=\cfrac{1}{2} x_n(3-kx_n^2)$

> 建議可以先預處理成 $x_n(1.5-(0.5k)x_n^2)$

其牛頓法的結算值再乘回 $k$ 即可近似求得 $\sqrt k=kx_n$