小梦 在 民科吧 发了一个 帖 《民科编程大赛：用四则运算开平方》 https://tieba.baidu.com/p/6809881927 ，
标题 还是 红颜色 的 …… 哦 ……
早在 古代， 我们的 先人 根据 杨辉三角， 就已经 发明了 开任意次方 的 方法 。 So ？
ylyyjjlh2 ， 你们 的 插值法 、插花法 、二分法 、二叉树法 、树叶法， 效率 比不上 先人 的 方法 吧 ？
你在 《民科编程大赛：用四则运算开平方》 https://tieba.baidu.com/p/6809881927 的 19 楼 说 ： “小数后15位，这已经到极限了。” ，
如果 用 先人 的 方法 的 话， 小数点 后 几百位 也是 分分钟 啊 。
本吧开心死了 （绮梦璇） skywalkerwyj （青莲剑歌） 天辩阮幼台 （陈彼方）
本文 已 发到了 反相吧 《小梦 在 民科吧 发了一个 用 四则运算 开平方 的 帖》 https://tieba.baidu.com/p/6811112759 。
下面 记录 帖 里 的 一些 回复 。
2 楼
ylyyjjlh2 ： 浮点数精度多少啊？你编程编糊涂了？
K歌之王 ： 浮点双精度 嘛， 差不多 就是 15 位 到 18 位 的 样子， 不过 我们 完全 可以 用一个 数组 编写 一个 无限位数 的 开平方 程序 啊 。
ylyyjjlh2: 回复 K歌之王 :别尽吹牛，你来啊，不准用库，算它1000位试试。
K歌之王 :回复 ylyyjjlh2 :可以啊， 库 也是 人 写 的 啊， 我最喜欢 造 轮子 。
K歌之王 :回复 ylyyjjlh2 :当然， 我不打算 近期 写， 你们也不用等着， 我最近在学习研究 其它 东西 。
3 楼
K歌之王 ：
回复 2 楼 ylyyjjlh2 ，
数据 的 长度 不是 重点， 我想说的是， 如果 不利用 和平方 公式 的 话， 你们 的 那些 什么 插值法 二分法 等等 的 所谓 “数值计算” “数值分析” 方法 的 性能 都 存在问题 。
如果要 对 n 开平方， 当 n 的 位数 很多 时 ， 你们 的 时间复杂度 会 很大 。
ylyyjjlh2: 能不胡扯吗！
K歌之王 :回复 ylyyjjlh2 :你从 昨天晚上 到 今天早上 憋了 9 个小时， 就 憋出来 这么 一句话 ？
4 楼
80 年代 的 计算器 已经有了 开平方 的 功能， 那是 用 硬件电路 实现 的 。 只能说， 80 年代 的 水平 真的 高 啊 ！
我们现在 用 Power Shell 、Python 玩 这些 ……
我们可以 玩 个 升级版 的， 设计一个 算法， 用 硬件电路 实现 这个 算法， 硬件电路 的 部分 只要 设计 逻辑电路 就可以， 就是说， 画出 逻辑电路 的 设计图 。
小梦， 如何 ？
本吧开心死了 （绮梦璇） skywalkerwyj （青莲剑歌） 天辩阮幼台 （陈彼方） ylyyjjlh2
8 楼
回复 7 楼 ylyyjjlh2 ，
先用 byte 数组 实现一个 无限位数 的 浮点类型， 这个 浮点类型 只要求 有 加 操作， 主要 是 实现 进位 。
不要求 有 其它 操作， 比如 减 、乘 、除 等 。
这样 ， 这个 浮点类型 还是 容易 实现 的 。
然后， 再用 先人 的 开方法 。
ylyyjjlh2: Talk is cheap.Show me the code.
K歌之王 :回复 ylyyjjlh2 :Talk is great , code is cheap .
9 楼
别问是劫是缘 ： 其实以前有人用普通计算器的加减乘除就可以手动开平方
10 楼
回复 9 楼 别问是劫是缘 ，
我将 根据 杨辉三角 开任意次方 的 方法 称为 杨辉三角 开方法 。
我想了一下 杨辉三角 开方法 的 步骤， 还是有一点 繁琐 的 。 以 开平方 来说， 在 迭代开方 的 过程中 ， 除了有 余量， 还有一个 累积量 。
这个 累积量 会 增加 一些 步骤， 也就是 会 增加 一些 时间复杂度 。
但不管怎么说， 杨辉三角 开方法 是 一个 正统 的 方法 。 它 的 好处 是 它 是 一个 “级数” 。
虽然 累积量 会 增加 一些 时间复杂度， 但是， 总的来说， 当 开方结果 的 位数 很大 时， 它 的 效率 仍然 优于 一般 的 数值分析 方法 。
累积量 是 一个 级数， 开方结果 也是 一个 级数， 开方结果 级数 里 包含了 累积量 级数 。
在 开高次方 时， 杨辉三角 开方法 的 累积量 有 多个， 比如 开 n 次方， 则 有 n - 1 个 累积量， 从 n - 1 次方 到 1 次方， 每个 次方 有一个 累积量 。
此时， 累积量 的 计算步骤 （公式） 会 膨胀 变得 复杂， 累积量 的 数值 也会 膨胀 急剧 增大， 这会让 程序 变得 复杂， 也会 增加 时间复杂度， 但是， 理论上， 仍然 可以用 杨辉三角 开方法 写出 无限位数 开任意次方 的 程序 。
累积量 也是 余项系数 。
别问是劫是缘: 我没关注过杨辉三角形开方，但是N-1个累积量，一个数组不就解决了？
11 楼
回复 10 楼 别问是劫是缘 ，
比如 开三次方， a ³ 可以写成
a ³ = ( a1 + b ) ³
= a1 ³ + 3 a1 ² b + 3 a1 b ² + b ³ ，
a1 已知， b 未知 。
这里 产生了 一个 b 的 一次项 3 a1 ² b ， 一个 b 的 二次项 3 a1 b ² ，
开 n 次方 会 产生 n 个 余项， 最后一个 n 次方 的 余项 的 系数 永远 是 1， 不用管 。 需要 累积 系数 的 余项 是 前面 的 n - 1 个 。
开三次方 会 产生 3 - 1 = 2 个 需要 累积 系数 的 余项， 这里 是 第一次 迭代， 3 a1 ² b 、3 a1 b ² 就是 第一次 迭代 时 产生 的 这 2 个 余项 。
令 b = b1 + c ， 则，
a1 ³ + 3 a1 ² b + 3 a1 b ² + b ³
= a1 ³ + 3 a1 ² ( b1 + c ) + 3 a1 ( b1 + c ) ² + ( b1 + c ) ³
= a1 ³ + 3 a1 ² ( b1 + c ) + 3 a1 ( b1 ² + 2 b1 c + c ² ) + b1 ³ + 3 b1 ² c + 3 b1 c ² + c ³
= a1 ³ + 3 a1 ² b1 + 3 a1 ² c + 3 a1 b1 ² + 3 a1 * 2 b1 c + 3 a1 c ² + b1 ³ + 3 b1 ² c + 3 b1 c ² + c ³
可以看到，
3 a1 ² ( b1 + c ) 中 产生了 c 的 一次项 3 a1 ² c ，
3 a1 ( b1 + c ) ² 中 也 产生了 c 的 一次项 3 a1 * 2 b1 c ，
( b1 + c ) ³ 中 也 产生了 c 的 一次项 3 b1 ² c ，
这 3 个 一次项 可以 合并为 一个， 这个项 就是 本次 迭代 产生 的 一次余项 。
同理，
3 a1 ( b1 + c ) ² 中 也 产生了 c 的 二次项 3 a1 c ² ，
( b1 + c ) ³ 中 也 产生了 c 的 二次项 3 b1 c ² ，
这 2 个 二次项 可以 合并为 一个， 这个项 就是 本次 迭代 产生 的 二次余项 。
接下来 的 开方过程 是 令 c = c1 + d ， 重复 上述过程 。
所以， n - 1 个 累积量， 也就是 余项系数， 可以用 一个 长度 为 n - 1 的 数组 保存， 但 每一个 余项系数 都 是 由 上述 的 迭代过程 计算产生， 这个 迭代计算 过程 比较 繁琐， 如果 能将 这个 迭代过程 归纳为 公式， 大概 是 一个 数列 的 通项公式 。
如果 不能 把 余项系数 的 计算过程 归纳 为 通项公式， 那么， 每 迭代一次， 余项系数 的 公式 就会 ”膨胀“ 一点， 当然， 这只是一个 形象 的 比喻 。
另一方面， 从上面的 计算过程 可以看出， 余项系数 是 相乘 一个 倍数 之后 再 相加， 得到 新的 余项系数 。 这可以看作是 成倍增长， 也差不多是 几何级数 。 这是 数值 上 的 ”膨胀“ 。
余项系数 膨胀 的 速度 和 开方 的 次方 有关， 次方 越大， 余项系数 膨胀 的 越快 。
另外， 次方 越大， 余项 越多， 一个 余项 需要 合并 的 项 也 越多 。
12 楼
小梦 在 《民科编程大赛：用四则运算开平方》 https://tieba.baidu.com/p/6809881927 的 20 楼 说 这是 “用泰勒级数进行逼近运算” ：
这是 泰勒级数 ？ 这不像是 泰勒级数， 这像是 一个 有 二分性质 的 迭代逼近 算法 。
这个 算法 是， 设 b 为 被开方数， 任取一个 正数 a， 令 c = ( b - a ² ) / ( 2 a ) ， 令 a = a + c ， 重复若干次 这个过程， a 就 很接近 b 的 平方根 了 。
这个 算法 适合 在 计算器 上 使用， 简单， 容易 由 程序 或者 逻辑电路 实现 。
本吧开心死了 （绮梦璇） ylyyjjlh2
绮梦璇: 傻子 [ 滑稽 ] 到现在都没看出一阶泰勒展开式？
绮梦璇: 回复 K歌之王 :傻子 [ 滑稽 ] 到底看懂了泰勒展开式没
K歌之王: 回复 绮梦璇 :我看到的是 “小梦级数” 。 [ 滑稽 ]
13 楼
ylyyjjlh2 ：
废话那么多，等到花儿都谢了，还没做出来，真的让人着急。下面看看，我对2开方700位，刚好一屏。
ylyyjjlh2: 没有金刚钻，就别揽瓷器活。不会做也没人说你是傻瓜，偏要吹牛。
14 楼
回复 12 楼 本吧开心死了 （绮梦璇）
一阶泰勒展开式 ？ 就是 泰勒级数 的 第一项 吧 ？ ( b - a ² ) / ( 2 a ) 这个式子 看起来 像 泰勒级数 第一项 ， 但 这只是 “形似”， 实际上 和 本题 没有关系 。
第二， 你 利用 ( b - a ² ) / ( 2 a ) 循环迭代， 这不是 泰勒级数， 可以叫做 “小梦级数”， 你的 滑稽 表情 说明了 这一点 。
第三， 你能 证明 这个 迭代 的 极限 是 根号 b 吗 ？ [ 滑稽 ]
15 楼
回复 13 楼 ylyyjjlh2 ，
Congratulations ! But, Talk is great , believe me ...
设 a 为 中间结果， 也是 最终结果， 你的 这个算法 避免了 每次迭代 都要 计算 a ² 吗 ？
ylyyjjlh2: 楼主吵，你除了吹牛还眼瞎，在那个贴子中，1我已经贴出了一堆大数运算的例子，你还在说你们也没有动作，还要啥动作？2我也贴出了代码，你还同我计算问题。真是个憨豆先生？
K歌之王: 回复 ylyyjjlh2 :吵 is talk, Talk is great , believe me ...
16 楼
回复 15 楼 @ylyyjjlh2 ，
你们 在 《民科编程大赛：用四则运算开平方》 https://tieba.baidu.com/p/6809881927 里 提出了 不少 算法，
不过 我没细看， 因为 我想 留着 自己研究 。
不过 不看 也知道， 你们 没有 避免 每次 迭代 计算 a ² 。
小梦 的 算法 号称 “泰勒级数”， 明目张胆 的 在 每次 迭代 计算 a ² ， 你来 评论看看 。
ylyyjjlh2: 东拉两扯，就是不干正事，我到看看你后面还有什么花样？
K歌之王: 回复 ylyyjjlh2 :我的 花样 可多着 呢 。
我在 12 楼 说了， 小梦 的 算法 简单小巧， 适合 用在 计算器 上， 我们可以 设计一个 硬件电路 来 实现 它 。
先画 一个 逻辑电路图 ：
左边 的 a 、b 、c 、diff 、v1 、v2 、abs_c 、max_diff 是 存储单元， 也就是 内存， 也就是 内存单元， 假设 每个 存储单元 是 64 位 的， 可以 存储 64 位 浮点数 。
右边 的 F1 、F2 、F3 、F4 、F5 、F6 是 控制单元， 具体 的 控制 和 运算 逻辑 就在 控制单元 里 实现 。
橙色线 和 橙色箭头 是 控制信号线路 和 信号传递方向， 蓝色线 是 数据线路， 一根 线 在 实际中 可能是 多位 的 。
绿色线 和 绿色箭头 也是 控制信号线路， 表示 和 橙色 不同 的 控制分支 。
F1 、F2 、F3 、F4 、F5 、F6 都 会有 数据线 和 相关的 存储单元 相连， 图中 用 蓝线 简略 的 表示， 并没有 画出 具体 的 连接 线路 。
我们 定义 ： 有电压 为 1， 无电压 为 0 。
开始运算 时， 输入端 输入 一个 1 脉冲， 就可以 触发 电路 开始 进行 开平方 运算 。 注意 是 1 脉冲， 不是 持续 的 1 。
先介绍一下 存储单元，
a 存放 a， a 是 中间结果， 也是 最终结果
b 存放 b， 也就是 被开方数
v1 存放 a ²
diff 存放 b - a ²
v2 存放 2 * a
c 存放 diff / v2
abs_diff 存放 diff 的 绝对值
max_diff 存放 精度值， 当 b - a ² 的 绝对值 ， 也就是 abs_diff 小于 max_diff 时， a 为 达到 精度 的 开方结果 ， 可以输出 。
开始 运算 前， 先 把 被开方数 存到 b， 同时 任取一个 正数， 比如 1 ， 存到 a 。
然后， 向 输入端 输入 一个 1 脉冲， F1 接收 到 1 脉冲 后 接通电路， 开始工作 。 F1 的 工作 是 发信号 给 运算器， 让 运算器 计算 a ²， 运算器 计算 结束后， F1 把 计算结果 存放到 v1 ， 同时 发出 一个 1 脉冲， 触发 F2 开始工作 。
运算器 在 这个 图 里 没有 画出来， 运算器 是 一个 公共部件， F1 、F2 、F3 、F4 、F5 、F6 都会去调用 。
F1 的 内部电路 会 在 下文 画出来， 里面 会 画出 F1 调用 运算器 的 电路 和 逻辑 。
F1 的 内部电路 如下 ：
输入端 接收 到 1 脉冲， 这个 1 脉冲 会让 “让 寄存器 A 变成 写入状态” 电路 接通， 这个电路 会 向 寄存器 A 发出 信号， 告诉 寄存器 A 变成 写入状态，
同时， 输入端 的 1 脉冲 还会 让 “让 寄存器 B 变成 写入状态” 电路 接通， 这个电路 会 向 寄存器 B 发出 信号， 告诉 寄存器 B 变成 写入状态，
同时， 输入端 的 1 脉冲 会 触发 延时开关， 延时开关 在 一段时间 后 输出 一个 1 脉冲 ， 这个 1 脉冲 会 接通 下一个 操作 的 电路 。
这样 就可以 在 一个 操作 完成后 触发 下一个 操作 执行 。
为什么要用 延时开关 呢 ？ 是 为了 确保 上一个 操作 完成 后， 才 触发 下一个 操作 。 因为 电路 的 运行 需要时间， 每一段电路 运作 需要 的 时间 也 不完全相同， 所以 需要 延时开关 在 一段时间 后 发出 1 脉冲 触发 下一个 操作， 这段时间 应该 足够 完成 当前操作， 这样 来 确保 触发 下一个 操作时， 当前 操作 已经 完成 。
从 图上 可以看到， “让 寄存器 A 变成 写入状态” 和 “让 寄存器 B 变成 写入状态” 是 F1 的 第一个 步骤， 这 2 个 操作 是 同时执行 的， 也可以说是 并行 执行 的 。
第 1 个 步骤 有 一个 延时开关， 当 “让 寄存器 A 变成 写入状态” 和 “让 寄存器 B 变成 写入状态” 完成 后， 延时开关 发出 1 脉冲， 触发 下一个 步骤 。
第 2 个 步骤 包含 2 个 操作， “打开 a 和 寄存器 A 的 通路， 让 a 的 数据 写入 寄存器 A” 和 “打开 a 和 寄存器 B 的 通路， 让 a 的 数据 写入 寄存器 B” ，
这 2 个 操作 也是 同时执行 的， 第 2 个 步骤 也 有 一个 延时开关， 这 2 个 操作 完成 后， 延时开关 发出 1 脉冲， 触发 下一个 步骤 。
到 目前为止， 每一个 操作 是 一段 电路， 这一段 电路 在 输入端 输入 1 脉冲 时 工作， 1 脉冲 结束 后 电路 停止 。
1 脉冲 是 有电压， 这个 电压 使得 电路 接通 并 工作， 1 脉冲 结束 后， 无电压， 电路不工作 。 延时开关 被 触发 后， 即使 输入端 的 1 脉冲 结束， 也会 在 设定好 的 时间 后 在 输出端 发出 1 脉冲 。
当然， 我们需要 知道 每一个 步骤 完成 的 最大时间， 以此 来 设置 这个 步骤 的 延时开关 的 延迟时间， 延迟时间 应该 比 步骤 完成 的 最大时间 更大一点， 这样 有一点 冗余， 有利于 电路 的 稳定运行 。
延时开关 的 输出端 连接 了