标签: polynomial-math

整数可用于存储单个数字,但不能用于存储数学表达式.例如,假设我有以下表达式:

6x ^ 2 + 5x + 3

我如何存储多项式？我可以创建自己的对象,但我不知道如何通过成员数据表示多项式.我不想创建一个函数来评估传入的参数,因为我不仅需要对它进行求值,还需要操作表达式.

矢量是我唯一的选择还是有更合适的解决方案？

我正在尝试优化我的多项式实现.特别是我正在处理具有模数n(可能是>2^64)的多项式,并以形式x^r - 1(r是< 2^64)对多项式求模.目前我将系数表示为整数列表(*),并且我以最直接的方式实现了所有基本操作.

我希望取幂和乘法尽可能快,为了获得这个,我已经尝试了不同的方法.我目前的方法是将系数列表转换为大整数乘以整数并将系数解包.

问题是包装和拆包需要花费很多时间.

那么,有没有办法改善我的"打包/解包"功能？

def _coefs_to_long(coefs, window):
    '''Given a sequence of coefficients *coefs* and the *window* size return a
    long-integer representation of these coefficients.
    '''

    res = 0
    adder = 0
    for k in coefs:
        res += k << adder
        adder += window
    return res
    #for k in reversed(coefs): res = (res << window) + k is slower


def _long_to_coefs(long_repr, window, n):
    '''Given a long-integer representing coefficients …

我可以用python中的参数来解决非线性方程组吗？有示例或教程吗？我可以很容易地用枫木做到这一点,但我特定系统的表达式非常大,复制它们非常困难.

例:

sigma*(y-x) = 0
x*(rho-z)-y = 0
x*y-beta*z = 0

你应该得到解决方案:

[[x = 0, y = 0, z = 0], [x = sqrt(beta*rho-beta), y = sqrt(beta*rho-beta), z = rho-1],
[x = -sqrt(beta*rho-beta), y = -sqrt(beta*rho-beta), z = rho-1]]

我问的原因是:我有一个非常大的非线性ODE系统.我想解决固定点(这是可行的,它是用枫木完成的,但它们很大而且很难看).我想从固定点创建更多表达式,然后在scipy中使用优化包.我宁愿在python中完成所有工作而不是来回翻译,因为它效率很低而且可以犯错误.

Bairstow的根寻找方法需要对二次因子进行非常好的初始近似以便收敛.

我尝试了各种常数,随机数,尾随系数中的分数(-a1/a2,-a0/a2;林？)无效.

请问,有没有人知道选择这些因素的好方法？

例如:

1*x^8 + 118*x^7 + 1*x^6 + 2*x^5 - 2*x^4 - 3*x^3 + 3*x^2 + 2*x + 1

找到根的初始近似值为0.1,0.2需要3倍,而0.2,2.0.

要么:

1*x^8 - 36*x^7 + 546*x^6 - 4536*x^5 + 22449*x^4 - 67284*x^3 + 118124*x^2 - 109584*x + 40320

0.1,1.2比0.1,0.1略长(~50%)

尝试使用Cauchy的边界进行初始二次近似:

R=0
for i in range(1,n+1):
    R=max(abs(a[i]/a[0]),R)
R=1+R
phi=2*pi*random()
x1=complex(R*cos(phi),R*sin(phi))
x2=complex(x1.real,-x1.imag)
r=-x1.real-x2.real
s=(x1*x2).real

不幸的是,这并没有真正加速融合.

我正在寻找一个算法(或代码)来帮助我计算逆多项式,我需要它来实现NTRUEncrypt.一个容易理解的算法是我更喜欢的,有伪代码用于执行此操作,但它们令人困惑且难以实现,而且我无法真正理解伪代码单独的过程.

用于计算截断多项式环的多项式的逆的任何算法？

这对我来说似乎是一个显而易见的问题,但我无法在任何地方找到它.我有一个三次多项式,我需要找到函数的真正根源.什么是的这样做的方法是什么？

我找到了几个关于立方函数根的封闭形式公式,但它们都使用复数或大量的测角函数而我不喜欢它们(并且也不知道选择哪一个).

我需要简单的东西; 越快越好; 而且我知道我最终需要求解更高阶的多项式,因此使用数值求解器也许会有所帮助.我知道我可以使用一些图书馆来为我做艰苦的工作,但是我想说我想做这个练习.

我用C编码,所以不import magic_poly_solver,请.

额外问题:如何在给定间隔内仅找到根？

所以我有一组特殊的三次样条曲线,它的2d控制点总是会产生一条永远不会在x轴上交叉的曲线.也就是说,曲线看起来像是简单的多项式函数,使得y = f(x).我想有效地创建一个沿样条曲线的y坐标数组,这些坐标对应于运行样条线段长度的均匀间隔的x坐标.

我想有效地找到与Y沿花键坐标,其中,例如,X = 0.0,X = 0.1,X = 0.2,等,或接近的另一种方式,有效地变换˚F _的x,y(吨)风格的函数成f(x)函数.

我目前使用4x4常数矩阵和4个2d控制点来描述样条曲线,使用Hermite或Catmull-Rom样条曲线的矩阵常数,并将它们插入从0到1 的t的三次函数.

给定矩阵和控制点,在x轴上获得这些y值的最佳方法是什么？

编辑:我应该补充说,一个足够好的近似值就足够了.

多项式:a0x ^ 0 + a1x ^ 1 + a2x ^ 2 + a3x ^ 3 + ... + anx ^ n

数组:array_a [] = {a0,a1,a2,a3 ... an};

我写了一个函数来计算Java中的这个多项式:

public double cal(double x) {
    double y = 0.0;
    for (int index = array_a.length - 1; index >= 0; index--) {
        y = array_a[index] + y * x;
    }
    return y;
}

这似乎比循环快5倍 y += array_a[index] * Math.Pow(x, index);

但我想知道是否有更好的方法来计算这个多项式？

**对于任何人都认为这是一个不同的计算:我测试了上面的功能.它做同样的事情,y += array_a[index] * Math.Pow(x, index);他们计算相同的结果.

谢谢.

我试图将scikit-learn的PolynomialFeatures实现为tensorflow和Keras中的前馈神经网络中的一个层.为简单起见,我将举例说明使用NumPy数组.如果批次具有三个样本并且某个层的激活等于(3,2)形矩阵

>>> X = np.arange(0, 6).reshape(2, 3)
>>> X
array([[0, 1],
       [2, 3],
       [4, 5]])

然后我希望下一层中的激活等于2次多项式特征扩展X:

>>> from sklearn.preprocessing import PolynomialFeatures
>>> PolynomialFeatures(degree=2).fit_transform(X)
array([[  1.,   0.,   1.,   0.,   0.,   1.],
       [  1.,   2.,   3.,   4.,   6.,   9.],
       [  1.,   4.,   5.,  16.,  20.,  25.]])

也就是说,如果层i的激活是X(形状(batch_size, num_features))矩阵,那么对于参数选择,degree=2我希望层i + 1的激活是一个串联

1. batch_size许多1.人的专栏,
2. X 本身,
3. 和所有无序对的列的元素方面的产品X:X[:, 0] * X[:, 0],X[:, 0] * …

在此Code Review答案中:

https://codereview.stackexchange.com/a/59405/11633

我找到了以下内容(嵌套引用!):

让我引用精彩的C++数字食谱书(但也适用)

我们假设你知道永远不会以这种方式评估多项式:

p=c[0]+c[1]*x+c[2]*x*x+c[3]*x*x*x+c[4]*x*x*x*x;

Run Code Online (Sandbox Code Playgroud)

或者(甚至更糟!),

p=c[0]+c[1]*x+c[2]*pow(x,2.0)+c[3]*pow(x,3.0)+c[4]*pow(x,4.0);

Run Code Online (Sandbox Code Playgroud)

来(计算机)革命,所有被认定犯有此类犯罪行为的人将被即决处决,他们的计划将不会!

(您可以在分析索引中找到您的版本中的页面,在"puns,particullary bad"条目下.我喜欢这本书.)

不这样做有两个原因:准确性和性能.评估多项式的​​正确方法是这样的:

-t * (0.319381530  +  t * (-0.356563782 + t * (1.781477937 + t * (-1.821255978 + 1.330274429 * t))))

Run Code Online (Sandbox Code Playgroud)

我可以看到以任何沮丧的方式实施它的严重性能损失,但不是精确度惩罚.准确性有什么不好？

我找到了这本书,但在引用位的任何地方都找不到这些信息.