展示 HN:多项式计算速度提升两倍
Show HN: Compute polynomials twice as fast

原始链接: https://thomasahle.com/fast-polynomials/

你可能听说过霍纳法则(Horner's method),它能在 $n$ 次乘法内求出一个 $n$ 次多项式的值(如果是首一多项式则需 $n-1$ 次)。但你知道吗?通过对系数进行预处理,任何首一多项式仅需 $\lfloor n/2 \rfloor + 1$ 次乘法即可,一般多项式则只需多加一次。你可以利用这一方法来近似计算 exp、sin、cos 等函数,或在密码学、哈希及编码理论中进行多项式求值。只需在下方输入多项式并选择域,我们就会为你进行预处理。

```Hacker News 最新 | 过往 | 评论 | 提问 | 展示 | 招聘 | 提交 登录 Show HN:多项式计算速度提升两倍 (thomasahle.com) 18 分,thomasahle 发布于 1 小时前 | 隐藏 | 过往 | 收藏 | 1 条评论 几年前,我和合著者在思考是否能减少哈希算法中乘法的次数。我们当时有一个构建方案和一份 100 页的证明,但无法百分之百确定其正确性。现在我们有了完整的 Lean 证明,因此决定将其发布出来。 我制作了这个网站,方便任何需要求多项式值的人查看如何使用我们的方法进行计算,同时也涵盖了 Knuth 等人此前的多种方法。 帮助 aetherspawn 11 分钟前 | 下一条 [–] 我想这应该比使用 CRC8 表格快不了多少吧? 回复 指南 | 常见问题 | 列表 | API | 安全 | 法律 | 加入 YC | 联系 搜索: ```
相关文章

原文

You may have heard about Horner's method, which evaluates a polynomial of degree n in n multiplications (n−1 if it is monic). But did you know that with a bit of preprocessing of the coefficients, n/2⌋+1 multiplications suffice for any monic polynomial, one more for a general one? You can use this to approximate functions like exp, sin, cos, or to evaluate polynomials in cryptography, hashing, and coding theory. Simply type a polynomial below, pick your field, and we'll preprocess it for you.

联系我们 contact @ memedata.com