Fast Polynomial Evaluation: 多项式计算速度翻倍工具
Show HN: Compute polynomials twice as fast
Fast Polynomial Evaluation 是一款突破性的链式编译器，它利用有理数预处理技术，将任意首一多项式的求值乘法次数从传统的 n 次降低至 ⌊n/2⌋+1 次。无论是用于 exp、sin、cos 等函数的近似计算，还是在密码学、哈希及编码理论中的多项式求值，它都能提供极致性能。用户只需输入多项式并选择数域，系统即可自动生成优化的计算链。相比 Horner 法、Estrin 法及 Rabin–Winograd 等经典算法，该工具在保持精确有理数预处理的同時，显著减少了乘法深度和总运算量，为高性能计算场景带来了革命性的效率提升。
通过巧妙的系数预处理，任何首一多项式的求值仅需 ⌊n/2⌋+1 次乘法，让计算速度直接翻倍。
HN 评论区
41- huhtenberg
* "monic" = 首项系数为 1
- emil-lp
我昨天（或者是前天）读了你的 arxiv 论文。
你觉得这能用来加速 k-path 的代数方法吗？
如果可以的话，你应该参加明年的 PACE 挑战赛。
- pvillano
这太酷了。我在玩 demo 的过程中学到了很多。我之前只知道 Horner 和 Estrin 方法，但现在我觉得我已经掌握了其中大部分。
我有一个小建议：在图形可视化中，为每个使用的 x、x^2、x^4 设置一个独立的源节点。单个 x 源会让图形显得杂乱，掩盖了结构。
- IsTom
相当酷，特别是在有限域中。不过在 Q（有理数域）里，系数似乎会迅速膨胀？
- throwaway81523
如果你要对多项式进行预处理，也许你想在多个不同的点上进行求值。但既然如此，为什么不直接用 FFT 呢？