Vibe News

霍纳法是算多项式最常用的办法，九次多项式要做九次乘法。现在有人证明，只要提前对系数做点预处理，九次多项式只需要五次乘法，差不多减半。这是Thomas Ahle和Knudsen刚发的一篇论文，还配了个网页，输入你的多项式就能看到各种算法的对比。评论区有人问，能不能给WyHash这类快速哈希提速。作者说这些哈希其实不是基于多项式的，反而正是论文想解决的问题：这类哈希靠走捷径而不是真正的乘法运算，容易被人设计出专门攻击它的输入。也有人问为什么不直接用快速傅里叶变换，作者回应说傅里叶变换要求提前知道所有取值点，但很多场景比如哈希表，输入是一条条流进来的，根本等不到提前规划。