按年被提到
20232023 · 3 次2026
数学、逻辑与理论›趣味数学与奇思妙想·arXiv:2307.15600 · math.NA

Generalising the Fast Reciprocal Square Root Algorithm

推广快速平方根倒数算法
Mike Day · 2023

把快速平方根倒数推广到任意有理幂,并构造可证最优常数

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 4 人首次 2023-07-31 · 最近 2026-03-17
4不同的人
3活跃月份
4讨论串
0被引(OpenAlex)

快速平方根倒数算法分两步:先用整数指令操作浮点数的位模式得到粗略近似,再通过一步或多步迭代(传统上用牛顿迭代,也有他人用精心挑选常数的改进式)加以精修。本文把该算法推广到所有有理幂,并支持精修步骤中任意次数的多项式;在无限浮点精度的假设下,给出自动构造所有这些情形下可证最优常数的方法。文中还表明,在某些假设下,使用首一(monic)精修多项式在成本与精度的权衡上远好于一般多项式,并分析了其他扩展、给出若干新的最佳近似。

HN 为什么提它

输入未附评论摘录,具体引用语境不详;该主题围绕“快速平方根倒数”这类经典位技巧的推广,被多人在多个月份提及。

方法难度 4 / 5约 40 分钟经得起时间
读之前最好知道
1IEEE 754 浮点数表示
2牛顿迭代法(Newton's method)
3多项式逼近与极小化最大误差
4位操作与整数指令

HN 书评

没有评论直接链到它;下面是它被提交的讨论串里回复最多的评论(不计入统计)
讨论串评论adampunk · 2026-03

“Mike Day shows a novel attack on the FISR made famous by Quake 3 Arena, offering an optimal solution for all rational powers. The critical turn is one that doesn't really show up elsewhere: define z = x^a * y^b, which equals 1 exactly when y = x^{-a/b}. Since z = x * y^2 and y_exact^2 = 1/x, we have y / y_exact = sqrt(z). Relative error in y is now expre…”

Generalising the Fast Reciprocal Square Root Algorithm (2023)原评论 ↗
被提交为 story · 4 次