我的算法太慢

我有一個算法，對於一個整數x和起動整數i使得1 < i < x的i的下一個值是由計算i = floor(x/i) + (x mod i)。這一直持續到我們已經看到的i。我的算法太慢

在JavaScript（雖然這個問題是語言無關）：

function f(x, i) { 
    var map = {}; 
    while(!map[i]) { 
     map[i] = true; 
     i = Math.floor(x/i) + (x % i); // ~~(x/i) is a faster way of flooring 
    } 
    return i; 
}

我可以證明，我們最終會達到我們已經看到了i，但我想知道：

計算下一個i是否有更高效的方法？
（更重要的是）有沒有辦法計算第n i沒有運行循環n次？

只是爲了澄清 - 我知道有比使用JS哈希映射爲檢查更快的方法，那地板可以通過整數除法其他語言所取代。我已經完成了這兩種優化，但是我放棄了它們來嘗試使代碼更易於理解。對不起，有任何困惑。

在此先感謝！

來源

2016-04-27 winhowes

這是一些已知的數學問題，如Collatz猜想？ – MBo

@MBo不是我所知道的。它源自我正在研究的一個副項目。如果它涉及到一個已知的數學問題，那將是非常瞭解的！幾周前我做了一個類似的數學問題的搜索，但不能提出任何問題，並且在問題上沒有得到太多改進，決定向其他人求助。 – winhowes

我覺得主要的時間吃飯 - 地圖。它使用一些散列函數（可能不簡單）。如果i範圍受限於合理值，則最好使用位/布爾值數組（或Javascript模擬）

第二 - 二個分區。 Javascript中的浮點數和整數是不同的？它可以使一個整數除法，發現模與乘法和減法（由於/模數定義整數除法的基本性能）：

p = x \\ i 
i = p + (x - p * i) 
or 
i = x - (x \\ i) * (i - 1)

注：在大多數處理器整數除法計算在相同的兩個商和殘餘物時間

mov eax, 17   //dividend 
mov ecx, 3   //divisor 
xor edx, edx   //zero 
div ecx    //edx:eax pair divide by ecx 
//now eax contains quotient 5, edx contains residue (modulus) 2

如果你可以在C使用ASM，或有一個像德爾福DivMod一些功能，可以使計算速度更快一些。

來源

2016-04-27 06:42:06 MBo

對不起，在我的c實現中，我確實比JS'map'有更快的檢查，但是謝謝你指出！我應該澄清 - 我只是寫在JS中，使其易於閱讀。對不起，你可以澄清第二點。你是說「地板」是第二個分區，可以移除嗎？我的C實現中也包含這些內容，對不起，我將在問題 – winhowes

中澄清這兩點。是的，可以刪除一個分區，也可以刪除所有分區。 – MBo

太棒了我會去看看。謝謝！我會在這裏關閉它，並將其遷移到programmers.stackexchange.com，因爲這可能是更適合這類問題的平臺。 – winhowes

我的算法太慢

回答

相關問題