大數字除法演算法——Newton 法 ê 變形

目錄
  1. 說明
  2. 範例

(開始寫 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$ ê size[sài-suh] 著偌大?我認為參考這篇文章 (pdf),會 tàng 要求 $\frac{N}{D} - Nx \leq 1$,

而且因為 $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)$,合結果。

毋過因為用求商符號代表整除符號會致到輸出出現誤差,使用 ê 時著注意。