---
title: 計算小數除法
tags: math, newton-method
---

# 計算小數除法
設有一變數除法為 $a/b$ ，可以改寫成 $a×(1/b)$，故只需要求 $1/b$ 的值再乘上 $a$ 即可求得其值

---

## 縮小問題規模

* 已知 $k$ 值，求 $1/k$ 的值為何？

套用牛頓法：$x=1/k \Rightarrow 1/x=k$

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

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

---

## 展開遞迴式並化簡(驗算用)

假設 $x=1/k$, $r=kx_n$

$x_n=x_n$
$x_{n+1}=x_n(2-r)$
$x_{n+2}=x_n(4-6r+4r^2-r^3)$
$x_{n+3}=x_n(8-28r+56r^2-70^3+56r^4-28r^5+8r^6-r^7)$
...

可利用遞迴關係得出結果趨近於

$x=x_n\cdot\sum_{i=1}(-1)^{i-1}C^n_ir^i$

即為巴斯卡三角形中 $(1-x)^n$ 的變化式，最終可得其簡化式為：

$x=x_n\cdot\cfrac{1-(1-r)^{2^t}}{r}$

$t$ 即為牛頓法的迭代次數

[參考源自 wiki](https://en.wikipedia.org/wiki/Division_algorithm#Fast_division_methods)

---

假設 $x=1/k$, $r=-kx_0$

$x_1=x_0(2-kx_0)=x_0(2+r)=2x_0+rx_0$
$x_2=x_1(2-kx_1)=(2x_0+rx_0)(2-k(2x_0+rx_0))=(2x_0+rx_0)(2-2kx_0+rkx_0)$
$\ \ \ \ =4x_0-4kx_0^2+2rkx_0^2+2rx_0-2rkx_0^2+r^2kx_0^2=4x_0+2rx_0-4kx_0^2+r^2kx_0^2$
$\ \ \ \ =$