展示 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 等函数,或在密码学、哈希及编码理论中进行多项式求值。只需在下方输入多项式并选择域,我们就会为你进行预处理。

抱歉。
相关文章

原文

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