锐客网

  1. 首页 > 生活百科 > it技术 > >

Python定义素数函数 python定义函数输出素数( 三 )

IT技术起随


下面的代码是算法的体现，其中包含一些特别的逻辑 。如果我们正在求逆的集合中包含零，那么它会将这些零的逆设置为 0 并继续前进 。
def multi_inv(self, values): partials = [1] for i in range(len(values)): partials.append(self.mul(partials[-1], values[i] or 1)) inv = self.inv(partials[-1]) outputs = [0] * len(values) for i in range(len(values), 0, -1): outputs[i-1] = self.mul(partials[i-1], inv) if values[i-1] else 0 inv = self.mul(inv, values[i-1] or 1) return outputs
这部分算法接下来会验证称为非常重要的东西，特别是当我们开始和不同阶的多项式进行计算的时候 。
现在我们来看看一些多项式计算 。我们把多项式当做一个数据集，其中的i是第i阶（例如，x3 + 2x + 1变成[1, 2, 0, 1]） 。下面就是在一个点进行多项式估算的方法：
# Evaluate a polynomial at a point def eval_poly_at(self, p, x): y = 0 power_of_x = 1 for i, p_coeff in enumerate(p): y += power_of_x * p_coeff power_of_x = (power_of_x * x) % self.modulus return y % self.modulus
困难和挑战
f.eval_poly_at([4, 5, 6], 2)的输出是多少？模是31吗？
下面的解释就是答案
.其实也有代码是多项式加法，减法，乘法和除法；这是很长的加减乘除运算 。有一个很重要的内容是拉格朗日插值，它将一组 x 和 y 坐标作为输入 ， 并返回通过所有这些点的最小多项式（你可以将其视为多项式求值的逆）：
# Build a polynomial that returns 0 at all specified xs def zpoly(self, xs): root = [1] for x in xs: root.insert(0, 0) for j in range(len(root)-1): root[j] -= root[j+1] * x return [x % self.modulus for x in root] def lagrange_interp(self, xs, ys): # Generate master numerator polynomial, eg. (x - x1) * (x - x2) * ... * (x - xn) root = self.zpoly(xs) # Generate per-value numerator polynomials, eg. for x=x2, # (x - x1) * (x - x3) * ... * (x - xn), by dividing the master # polynomial back by each x coordinate nums = [self.div_polys(root, [-x, 1]) for x in xs] # Generate denominators by evaluating numerator polys at each x denoms = [self.eval_poly_at(nums[i], xs[i]) for i in range(len(xs))] invdenoms = self.multi_inv(denoms) # Generate output polynomial, which is the sum of the per-value numerator # polynomials rescaled to have the right y values b = [0 for y in ys] for i in range(len(xs)): yslice = self.mul(ys[i], invdenoms[i]) for j in range(len(ys)): if nums[i][j] and ys[i]: b[j] += nums[i][j] * yslice return [x % self.modulus for x in b]
相关数学知识请参见此文的M-N部分 。需要注意，我们也会有特别的方法lagrange_interp_4和lagrange_interp_2来加速次数小于 2 的拉格朗日插值和次数小于 4 的多项式运算 。
快速傅立叶变换
如果你仔细阅读上面的算法，你也许会发现拉格朗日插值和多点求值（即求在N个点处次数小于N的多项式的值）都需要耗费2次时间，例如对于1000个点求拉格朗日插值，需要几百万个步骤，而且100万个点的拉格朗日插值需要万亿个步骤 。这是不可接受的低效率，所以我们需要使用更加有效的算法，快速傅立叶变换 。
FFT只需要花费O(n * log(n))的时间（也就是说，1000个点的计算需要10,000步，100万个点的计算需要2000步），虽然它的范围更受限制；x坐标必须是单位根部的完全集合 ， 必须满足N = 2k 阶 。也就是说 ， 如果有N个点 ， 那么x坐标必须某个P值的连续幂 ， 1, p, p2, p3… ， 其中pN = 1 。这个算法能够用来进行多点计算和插值计算，而且只需要调整一个小参数 。
下面就是算法详情（这是个简单的表达方式；更详细内容可以参阅此处代码）
def fft(vals, modulus, root_of_unity): if len(vals) == 1: return vals L = fft(vals[::2], modulus, pow(root_of_unity, 2, modulus)) R = fft(vals[1::2], modulus, pow(root_of_unity, 2, modulus)) o = [0 for i in vals] for i, (x, y) in enumerate(zip(L, R)): y_times_root = y*pow(root_of_unity, i, modulus) o[i] = (x+y_times_root) % modulus o[i+len(L)] = (x-y_times_root) % modulus return o def inv_fft(vals, modulus, root_of_unity): f = PrimeField(modulus) # Inverse FFT invlen = f.inv(len(vals)) return [(x*invlen) % modulus for x in fft(vals, modulus, f.inv(root_of_unity))]

推荐阅读


上一篇：狗狗跑步拍摄用什么，狗狗跑步机制作图

下一篇：html5存储方式csdn，html5的web存储对象