标签: polynomial-math

我想出了一个新算法来解决子集求和问题,我认为它是在多项式时间内.告诉我,我要么是错的,要么是天才.

快速启动事实:

子集和问题是NP完全问题.在多项式时间内求解它意味着P = NP.
一组长度N中的子集的数量是2 ^ N.

在更有用的手上,长度为N 的唯一子集的数量最大为整个集合减去最小元素的总和,或者,任何子集可能产生的总和的范围在所有负面元素的总和之间和所有正元素的总和,因为没有和可能比所有正或负更大或更小,当我们添加额外元素时,它们以线性速率增长.

这意味着当N增加时,重复子集的数量呈指数增长,并且唯一有用子集的数量仅线性增加.如果可以设计出可以尽早移除重复子集的算法,我们将在多项式时间运行.一个简单的例子很容易从二进制中获取.仅从2的幂的数字,我们可以为任何积分值创建唯一的子集.因此,任何涉及任何其他数字的子集(如果我们拥有所有权力的两个)都是重复和浪费.通过不计算它们及其衍生物,我们几乎可以节省算法的所有运行时间,因为与任何整数相比,2的幂的数字是对数发生的.

因此,我提出了一个简单的算法,它将删除这些重复项,并节省必须计算它们及其所有衍生物.

首先,我们将对仅为O(N log N)的集合进行排序,并将其分为两半,正面和负面.负数的程序是相同的,所以我只勾勒出正数(现在的数字只是正半数,只是为了澄清).

想象一下由sum索引的数组,其中包含正面所有可能结果总和的条目(只记住线性,记住).添加条目时,该值是子集中的条目.就像,array [3] = {1,2}.

通常,我们现在移动到枚举集合中的所有子集.我们从一个长度的子集开始,然后添加到它们.当我们拥有所有独特的子集时,它们形成一个数组,我们只是按照Horowitz/Sahni中使用的方式迭代它们.

现在我们从"第一代"价值观开始.也就是说,如果原始数据集中没有重复的数字,则保证这些值中没有重复.也就是说,所有单值子集,以及集合的所有长度减去一个长度子集.这些可以通过对集合求和,并依次减去每个元素来轻松生成.此外,集合本身是有效的第一代和和子集,以及子集的每个单独元素.

现在我们做第二代价值观.我们循环遍历数组中的每个值,并且对于每个唯一子集,如果它没有它,我们添加它并计算新的唯一子集.如果我们有重复,就会发生乐趣.我们将它添加到碰撞列表中.当我们来添加新的子集时,我们检查它们是否在碰撞列表中.我们通过不太理想(通常更大,但可以是任意)相等的子集来键入.当我们添加到子集时,如果我们生成碰撞,我们什么都不做.当我们添加更理想的子集时,它会错过检查并添加,生成公共子集.然后我们重复其他几代人.

通过以这种方式删除重复的子集,我们不必将重复项与集合的其余部分保持组合,也不必继续检查它们是否存在冲突,也不必对它们求和.最重要的是,通过不创建非唯一的新子集,我们不会从它们生成新的子集,我相信,这可以将算法从NP转换为P,因为子集的增长不再是指数 - 我们丢弃绝大多数之前,他们可以在下一代"再现",并通过与其他非重复子集组合创建更多的子集.

我不认为我已经解释得太好了.我有照片......他们在我脑海里.重要的是,通过丢弃重复的子集,您可以删除几乎所有的复杂性.

例如,想象(因为我手工做这个例子)一个简单的数据集,它以-7到7(非零)为目标,为零.排序和拆分,所以我们留下(1,2,3,4,5,6,7).总和是28.但是2 ^ 7是128.所以128个子集适合1 ... 28的范围,这意味着我们事先知道100个集是重复的.如果我们有8,那么我们只有36个插槽,但现在有256个子集.因此,您可以很容易地看到欺骗的数量现在是220,比以前增加了一倍.

在这种情况下,第一代值是1,2,3,4,5,6,7,28,27,26,25,24,23,22,21,我们将它们映射到它们的组成部分,所以

1 = { 1 }
2 = { 2 }
...
28 = { 1, 2, 3, 4, 5, 6, 7 }
27 = { 2, 3, 4, 5, 6, 7 }
26 = { 1, 3, 4, 5, 6, 7 }
...
21 …

我正在寻找一个库或计算机代数系统,它将帮助计算环中多项式的运算

F_2[x_1, ..., x_n] / <f^2 - f>

其中F_2是2-元素的有限域,并且<f^2 - f>是从元件所产生的理想f^2 - f对所有f在F_2[...].(我认为/希望/我很确定这是使用xor作为+和*[ 维基百科 ] 的布尔代数环).

例如,

x_1 = poly_xn 1
x_2 = poly_xn 2
x_1 * x_2 * x_1 -- returns "x_1 * x_2"
x_1 + x_1 + x_2 -- returns "x_2"

我已经在Haskell中为此编写了代码,但不幸的是性能不是很好.

注意:标题"仿射k-代数"来自艾森伯德的交换代数,其中包含代数几何的观点.35; 如果有更好的名字请编辑问题,谢谢!

我正在为我正在处理的网站编写一些分析模块,我需要估算当前小时后的总观看次数.我有每分钟的数据直到当前分钟,所以如果时间是12:28,我将有一个看起来像这样的数组:

0: "21410"
1: "21886"
2: "21837"
3: "21895"
4: "21564"
5: "21714"
6: "21571"
7: "21324"
8: "21310"
9: "21390"
10: "21764"
11: "21598"
12: "21493"
13: "21352"
14: "21478"
15: "21058"
16: "20942"
17: "20825"
18: "21321"
19: "20950"
20: "21039"
21: "21117"
22: "20733"
23: "20773"
24: "20929"
25: "20900"
26: "20687"
27: "20999"

目前我正在预测小时的价值如下:

(60/minsSoFar)*totalSoFar

这样做效果相当不错,但我宁愿在数学上做得更多.我想计算出迄今为止我所拥有的数据的最佳拟合线,并计算到第60分钟.这将考虑加速和减速.

通过我目前正在使用的方法,我实际上假设趋势是一条直线.如何计算多项式或幂次数的公式？

我在NodeJS中写这个,所以JavaScript是理想的,但我也会采用伪代码!

如果您需要,这是一个更简单格式的数组:

[21410, 21886, 21837, 21895, 21564, 21714, 21571, 21324, 21310, 21390, 21764, 21598, 21493, 21352, 21478, 21058, 20942, …

我有一个五次函数(五次多项式),我想用C++解决它.是否有可以使用的实现或数学库才能继续？

我正在尝试使用 ZDD 实现单变量多项式，如另一个问题的评论中所建议的。

我读过 S. Minato 的论文（你可以在这里下载）），但我不明白如何在这些ZDD上实现操作。

论文中的想法是多项式可以用x^(2^i)变量来表示。例如，x^5 + x^3 + x可以重写为x^4x^1 + x^2x^1 + x^1，如果您为每个x^(2^i)变量创建节点并与相乘的“1-边”变量和相加的“0-边”变量连接，您可以轻松获得表示该多项式的图形. ZDD 是这种图形，它在图形上强制执行某些条件（有关更多信息，请阅读 Minato 的文章和维基百科关于 BDD的页面）

可以使用 2 的幂之和类似地表示系数（例如，5 = 2^2 + 2^0每个2^i都是变量并且节点以相同的方式与 1 和 0 边连接）。

现在，我的问题是添加两个 ZDD 的算法。算法看起来很简单：

如果 F 和 G (ZDDs) 没有共同的组合，只需将它们合并即可完成加法 (F + G)。当它们包含一些常见的组合时，我们计算以下公式：(F + G) = S + (Cx2)，其中 C = F ? G, S = (FUG) \ C …

这两个函数执行扩展欧几里德算法,然后找到乘法逆.这个顺序似乎是正确的,但它并没有按照悉尼大学的这个工具回复http://magma.maths.usyd.edu.au/calc/,因为这是在GF(2)完成的. )有限域,我想我错过了从基数10转换到这个字段的一些关键步骤.

这在基数10上进行了测试和处理,但是在这里可能无法接收具有二进制系数的多项式.所以我的问题是我错误地应用于这个算法的Python的哪些部分,例如// floor,可能无法承载基本10中的函数能够在GF(2)中执行此操作.

上面的工具可以像这样测试:

R<x>:=PolynomialRing(GF(2));
p:=x^13+x+1; q:=x^12+x;
g,r,s:=XGCD(p,q);

g eq r*p+s*q;

g,r,s;

功能:

def extendedEuclideanGF2(self,a,b): # extended euclidean. a,b are values 10110011... in integer form
    inita,initb=a,b;  x,prevx=0,1;  y,prevy = 1,0
    while b != 0:
        q = int("{0:b}".format(a//b),2)
        a,b = b,int("{0:b}".format(a%b),2);
        x,prevx = (int("{0:b}".format(prevx-q*x)), int("{0:b}".format(x,2)));  y,prevy=(prevy-q*y, y)
    print("Euclidean  %d * %d + %d * %d = %d" % (inita,prevx,initb,prevy,a))
    return a,prevx,prevy  # returns gcd of (a,b), and factors s and t

def modular_inverse(self,a,mod): # a,mod are integer values …

在此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)

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

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

我正在研究我的Elliptic Curve Cryptography项目,该项目需要在二进制字段上进行编程.它包括基本运算,如加法,乘法,反演等,这是一种不可约的二元多项式.

我正在寻找一种方法,通过这种方式可以将这些二进制多项式存储在程序中.我正在研究C和C++编程语言(使用gmp库)所以我想到的第一个想法是使用结构和位字段.但它们不是动态的,不能保持任意长的多项式.使用C++ Vector STL是可能的,但它不会有效,因为它在8位或更多位的单个字中存储单个位.

是否有任何有效的表达方式？

我正在尝试使用快速傅立叶变换(fft)实现快速多项式除法.

这是我到目前为止所得到的:

from numpy.fft import fft, ifft
def fft_div(C1, C2):
    # fft expects right-most for significant coefficients
    C1 = C1[::-1]
    C2 = C2[::-1]
    d = len(C1)+len(C2)-1
    c1 = fft(list(C1) + [0] * (d-len(C1)))
    c2 = fft(list(C2) + [0] * (d-len(C2)))
    res = list(ifft(c1-c2)[:d].real)
    # Reorder back to left-most and round to integer
    return [int(round(x)) for x in res[::-1]]

这适用于相同长度的多项式,但如果长度不同则结果是错误的(我对RosettaCode的 extended_synthetic_division()函数进行基准测试):

# Most signficant coefficient is left
N = [1, -11, 0, -22, 1]
D = [1, -3, 0, …

我正在尝试计算我正在使用的训练数据的错误率.

我相信我错误地计算错误.公式如下:

y 计算如下:

我fitPoly(M)在线上的函数中计算这个49.我相信我的计算不正确y(x(n)),但我不知道还能做什么.

以下是最小,完整和可验证的示例.

import numpy as np
import matplotlib.pyplot as plt

dataTrain = [[2.362761180904257019e-01, -4.108125266714775847e+00],
[4.324296163702689988e-01,  -9.869308732049049127e+00],
[6.023323504115264404e-01,  -6.684279243433971729e+00],
[3.305079685397107614e-01,  -7.897042003779912278e+00],
[9.952423271981121200e-01,  3.710086310489402628e+00],
[8.308127402955634011e-02,  1.828266768673480147e+00],
[1.855495407116576345e-01,  1.039713135916495501e+00],
[7.088332047815845138e-01,  -9.783208407540947560e-01],
[9.475723071629885697e-01,  1.137746192425550085e+01],
[2.343475721257285427e-01,  3.098019704040922750e+00],
[9.338350584099475160e-02,  2.316408265530458976e+00],
[2.107903139601833287e-01,  -1.550451474833406396e+00],
[9.509966727520677843e-01,  9.295029459100994984e+00],
[7.164931165416982273e-01,  1.041025972594300075e+00],
[2.965557300301902011e-03,  -1.060607693351102121e+01]]

def strip(L, xt):
    ret = []
    for i in L:
        ret.append(i[xt])
    return ret

x1 = strip(dataTrain, 0)
y1 = strip(dataTrain, 1)

# HELP HERE

def getY(m, w, D): …