如何使用多项式代替位来提高性能？

Question

我有一个128位字符串,我的主管要求我将这128位表示为多项式.这是他正在写的论文的扫描:

他的想法是,由于我们从这些位中消除了0,我们将能够比我们处理所有位更快地执行下一个操作(大多数是位/多项式之间的XOR).

我理解要求是什么,我可以在纸上和应用程序中完成.但我的方式不会实现他的目标,即提高绩效.他实际上说有些图书馆已经这样做了,但遗憾的是我找不到任何图书馆.我发现的唯一一个是多项式类来评估多项式,这不是我想要的.

所以你们知道如何实现这一点来提高性能？任何代码/片段/文章非常感谢.

该应用程序是用Java编写的,如果这有任何区别的话.

谢谢,

莫塔

更新:

我的主管说这个C库将完成任务.我无法弄清楚它是如何工作的以及如何做到这一点.

Answer 1

你的主管熟悉BitSet吗？128位是16字节,可以存储为2 longs.但是,使用BitSet,您无需担心处理2的组合longs.BitSet还为所有常见位操作提供方法.我认为你很难找到比这更好的解决方案.

多项式方法是一个非常酷的想法,但我认为它更具理论性而非实际性.

Answer 2

他提议的是Monomial你可以构成的Polynomial- 想想复合模式.定义所有常用的数学运算(加法,减法,乘法,除法)和您认为可能需要的任何其他算法(例如,微分和积分).

多项式对于像这样的情况非常有用x^1000 + 1,因为你可以用两个术语捕获它.

真正的问题是:你的老板想象你在拯救什么？几点？速度？开发时间？我同意ziesemer - 你会很难做得比一个更好BitSet.他/她正在考虑的节省对我来说似乎是一种微观优化,如果你描述了你的应用程序就不会出现这种情况.

但他/她是老板......值得论证吗？

也许你可以抽象出这个细节并描述这两个细节.