如何使用多项式而不是位来提高性能？

我有一个128位的字符串，我的主管要求我将这128位表示为一个多项式。这是他在论文中对写的扫描：如何使用多项式而不是位来提高性能？

Converting bits to a polynomial

他的想法是，既然我们消除这些位0，我们就可以进行下一个操作（其中大部分是XOR在比特/多项式之间）比如果我们处理所有比特要快得多。

我明白要求是什么，我可以在纸上做，也可以在应用程序中做。但我的方式不会达到他的目标，这是提高绩效。他实际上说有图书馆已经这样做了，但不幸的是我找不到任何图书馆。我唯一发现的是一个多项式类，它评估多项式，这不是我想要的。

那么你们知道我该如何实现这个来改善性能？任何代码/片段/文章非常感谢。

该应用程序是用Java编写的，如果有什么区别的话。

感谢，

莫塔

更新：

我的主管说，这C library会做的任务。我不知道它是如何工作的，以及它会如何工作。

来源

2011-12-17 Motasim

我已经看到这在加密库，特别是加利福尼亚领域完成。我不能比这更具体，这是我见过它的一段时间。 – 2011-12-17 20:44:22

http://en.wikipedia.org/wiki/Finite_field_arithmetic – 2011-12-17 20:46:37

问题是大多数机器处理位速度非常快，如果您尝试做其他任何事情（.e.g *，+，/），它仍然需要使用位。如果在所有原因中使用多项式的速度都比较快，那么可以将其分解为多个比特，然后在每次迭代时使其更快（但我怀疑它每次都会变慢）。可能会出现这样的情况，他所建议的是更快，但我想不出任何。 – 2011-12-17 21:06:18

您的主管是否熟悉BitSet？ 128位是16字节，可以存储为2 longs。但是，使用BitSet，您不必担心处理2 longs的组合。 BitSet还提供所有常用位操作的方法。我想你会很难找到比这更好的解决方案。

多项式方法是一个非常酷的想法，但我认为它比实际更理论。

来源

2011-12-17 20:40:45 ziesemer

他建议的是一个Monomial，你可以写成Polynomial - think composite pattern。定义所有通常的数学运算（加法，减法，乘法，除法）和你认为可能需要的任何其他操作（例如，区分和集成）。

多项式对于x^1000 + 1这样的情况来说真的很有用，因为你可以用两个项来捕获它。

真正的问题是：你的老板想象你在保存什么？几位？速度？开发时间？我同意ziesemer--你会很难比BitSet做得更好。他/她想到的储蓄似乎对我来说是一种微型优化，如果您对应用程序进行分析，这种事情就不会出现。

但是他/她是老板......这值得争辩吗？

也许你可以将这个细节抽象出来并描述两者。

来源

2011-12-17 20:47:28 duffymo

如果您有多个需要异或的字符串，它实际上会导致性能开销。这是因为你需要匹配权重。

这一切都取决于你与异或与多少次，你必须这样做来计算采取这种方法的优势。

我会去ziesemer的解决方案。

来源

2011-12-17 21:12:02

我非常怀疑你会从128位字符串中获得任何好处。 128位是16字节;任何对象至少需要40个，所以（几乎）任何支持结构都比它存储的数据更昂贵。

不过，这里的a good survey现有的方法 - 和一个新的，它可能（或可能不会）对你有利。不像这是对你的问题的回答，并且同意，但ziesemer的解决方案对于如此庞大的数字是最好的，但如果你想扩大你的视野，请看一看。

来源

2011-12-17 22:01:28 alf

如何使用多项式而不是位来提高性能？

回答

相关问题