沒想到吧,? 這個系列居然會更新.

話不多說就直接開始正文罷.

首先說明一下平方的顯而易見的規(guī)律:? 無論在多少進(jìn)制下,? ?n?位整數(shù)平方后最多為 2n 位;? 并且如果整數(shù)以 m 個 0 結(jié)尾的話,? 平方后會以 2m 個 0 結(jié)尾.? 這里說明對一個數(shù)字開平方,? 可以把數(shù)字分割成一串 2 個數(shù)字組成的列表再進(jìn)行后續(xù)計算.

上面說到的第 2 點提供了一個從高位開始計算逐漸逼近答案的方法:

考慮數(shù)字 7,? 它的平方是 49,? 而 8 的平方是 64,? 那么 4900 開方是 70,? 6400 開方是 80,? 而區(qū)間 [4900, 6400) 里所有數(shù)字的開方都是 7x.xx,? 而后續(xù)的位可以使用類似的方法逐位算得.

用 207936?做例子:??1) 首先看到 20,? 小于 20 最大的完全平方數(shù)是 16,? 也就是說 207936 開方的第一位是 4.? 2) 然后看到 2079,? 設(shè) 2079 是一個數(shù)字的平方,? 由上一步可以設(shè)這個數(shù)字是 40+a,? 那么得到方程 (10×4+a)2?= 2079,? 解得 a=5.596?,? 因為這里 a 必為整數(shù),? 所以對 a 向下取整得 5.? 3) 最后看到 207936,? 因為這是 6 位數(shù),? 所以開方后是 3 位,? 由上面兩部得到前兩位是 45,? 那么又可以列出方程 (10×45+b)2?= 207936,? 這里可以直接解得 b=6,? 于是得出 207936 開方為 456.

在二進(jìn)制里也是類似的,? 用 25 做例子,? 25 的二進(jìn)制為 011001 (需要用 0 補充到偶數(shù)長度):? 01) 看到 01,? 開方即為 1.? 10) 看到 0110,? 列出方程 (10×1+a)1?=0110 (二進(jìn)制下),? 解得 a=0.011?,? 也就是 a 取 0.? 11) 類似地可以列出方程 (10×10+b)1?=011001 (二進(jìn)制下) 解得,? b=1,? 也就是說 011001 開方為 101.

剩下的問題就是如何用硬件計算上述過程里的方程了.

為了方便,? 記某一步需要"看到"的數(shù)字為 x?,??開方后前面已知的數(shù)字為 y?,??z = x? - 100×y?1??和 需要求的位為 a.? 以上面二進(jìn)制例子的第二步為例,? x?=0110, y?=1, z=0010.

那么方程可以寫為 (10×y?+a)1?=x?,? 展開括號為 100×y?1? + 100×y?×a + a1? = x?,? 使用上述約定可以化為?100×y?×a?+ a1??= z.? 因為 a 只能取 0 或 1,? 所以當(dāng) z ≥?100×y?×1 + 11? = 100×y?+1 時 a 取 1,? 否則 a 取 0.

當(dāng)已知這步的 z 時,? 如果 a = 1,? 那么下一步 z = 100×(z - (100×y?+1)) + p,? 否則 z = 100×z + p,? 這里 p 為 下一步比上一步需要"多看"的部分.? 比如上面二進(jìn)制例子的第二步的 p=10.? 并且使用加法器可以直接同時求得 a 和?z -?(100×y?+1)? (a 為加法器的進(jìn)位輸出).

特殊地,? 開始計算的第一步可以看作 y?=0?和上一步 z=0 的特殊情況,? 所以只需要不斷迭代這個步驟就可以求出數(shù)字的開方.? 另外,? 這個算法對小數(shù)也適用,? 所以控制迭代次數(shù)就可以以任意精度求得結(jié)果.??實際上,? 最后一步剩下的?z?可以用作判斷絕對誤差,? 不過這就是另外一個話題了?(主要是應(yīng)該不會有人在意).

下面是模擬硬件算法的 julia 函數(shù),? quotient 是 y?,? remainder 是 z,? carry 是 a.

如果對這個程序有興趣的可以去看看我的gayhub垃圾桶: https://github.com/nyasyamorina/trash-bin/blob/main/BinSqrt.jl

mc 里制造的開方器實體在前兩天的視頻里展示過了,? 這里也就不發(fā)了

這個開方器里,? 深藍(lán)是記錄 y? 和處理 -(100×y?+1);? 淺藍(lán)色是加法器;? 橙色是時鐘;? 紅色是清空寄存器;? 黃色是加法器進(jìn)位輸出 a 和判斷下一個 z 的取值;? 在加法器之前的淺綠是從輸入提取 p;? 加法器之后的淺綠是記錄 z;? 深綠是計算完成后保存結(jié)果并輸出到外部的.

日常推澀/雜圖群:?274767696