如何使用多項式而不是位來提高性能？

我有一個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

如何使用多項式而不是位來提高性能？

回答

相關問題