大數字除法演算法——Newton 法 ê 變形
（開始寫 tī 2019-10-11，上新修改 tī 2023-07-26）
說明
設使汝干焦有整數乘法、整數加減法 kap 向正爿徙位 (>>)，而且任何變數無法度用小數 tiông (store) 入去，欲按怎實做除法演算法？
一个實做大數演算法 ê 方法，是用微積分 ê Newton 法：假使 $N$ 是被除數， $D$ 是除數（$N, D \in Z , Z = { x \mid x \in 𝑵 \bigcup x=0}$），攏是 $a$ 進位數，$length(x) $ 指整數 $x$ tī $a$ 進位數 ê 長度（例：$length(100_{10})=3,~length(89_{10}) = 2$）。
咱會當求一个數 $x = D^{-1}$，按呢 $N / D = Nx$ 。閣用 Newton 法 kā $f(x) = Dx - 1 $（tī $x=1/D$ 有解） 求伊ê近倚ê解 $x_k$，tiō 有 $nx_k \approx N / D$ ，mā 近倚商數矣。
但是有一个問題：$D^{-1}$是小數，欲按怎算 leh？
一个方法著是 kā $\frac{1}{D}$ 乘以 $a^p$（就是放大），算出 $\frac{a^p}{D}$ ê 近似數 $y_k$，按呢 $Ny_k \approx \frac{Na^p}{D}$。koh 設定 $ x 向正爿徙 p 位 := x_a \gg p = x // a^p$；其中$a // b = a 除以 b~ê 商數$），就通得著 $Ny_k \gg p \approx \frac{Na^p}{D} // a^p \approx N/D$。
$p$ ê
而且因為 $N < a^{length(N)}$，tī $N\neq 0$ ê 時，tiō 有
$$\frac{1}{D} - x < a^{-length{N}}$$
咱欲予 $\frac{a^p}{D} - xa^p $ tī $\frac{1}{D} \neq x$ ê 時，會當用整數加減計算，所以通 kā 設定做 $\frac{a^p}{D} - xa^p = a^p(\frac{1}{D}-x) < a^1$，按呢比較一下， $a^p = a^{1+length(N)}$。所以 $p$ 通設定做 $1+length(N）$。
Beh 揣 $y_k \approx \frac{a^p}{D}$，通用 $f(y) = \frac{1}{y} - \frac{D}{a^p}（其中 p = 1+length(N)）$ kap Newton 法計算伊 ê 近似解。
tiō有
$y_{k+1} = y_k - \frac{f(y)}{f’(y)} = y_k - \frac{\frac{1}{y_k} - \frac{D}{a^p}}{-y_k^{-2}} = 2y_k - \frac{y_k^2D}{a^p}$。
（拄開始通設定 $y_0=1$）
會當 kā $\frac{y_k^2D}{a^p}$ 用 $(y_k^2D)//a^p$ 近倚，tiō 有：
$$y_{k+1} = 2y_k - {y_k^2D} // {a^p}$$
範例
設定 $N=85965, D=457, a = 10$，愛算出 $N/D$ ê商。
$ y_0 = 1 $
$ y_1 = 2y_0 - y_0^2D // 10^{length(N)+1} = 2y_0 - {457{y_0^2}} // {10^{6}} = 2 $
$ y_2 = 2y_1 - {457{y_1^2}} // {10^{6}} = 4 $
$ 照按呢， y_3 = 8, y_4 = 16, y_5 = 32, y_6 = 64, y_7 = 127, y_8 = 247, y_9 = 467, y_{10} = 835, $
$ y_{11} = 1352, y_{12} = 1869, y_{13} = 2142, y_{14} = 2188, y_{15} = 2189, y_{16} = 2189$
因為 $y_{15} = y_{16} = 2189$，計算結束。所以
$Ny_{16} = 188177385, N//D \approx Ny_{16}//a^{1+length(N)} = 188。$
比較 $N/D \approx 188.10722100656454（所以N//D = 188）$，合結果。
毋過因為用求商符號代表整除符號會致到輸出出現誤差，使用 ê 時著注意。