找到最小值，以滿足模數

即16807k≡X（MOD 65536）

我需要計算k值知道X。到目前爲止，我的最大努力是蠻力。有沒有數學方法來計算k？如果沒有任何優化我當前的代碼將不勝感激。

t = x; 
while (t += 15115) // 16807k = 65536n + x - this is the n 
{ 
    if (t%16807 == 0) 
    return t/16807; 
} 
return x;

編輯：更改+ =到15115

來源

2014-02-20 Hector

X =（16807值X k）％65536和16807k =在x mod 65536的模逆是不等價的。 – Roecrew

除了@Roecrew評論：第一個方程有多個'k'作爲答案，第二個有'k'。你需要找到所有'k'嗎？ –

老兄對不起，但你沒有任何意義。你能告訴我們至少這個代碼的應用是什麼嗎？ – Roecrew

一個奇數具有乘法逆模的二的冪。

的16807模2 逆是22039.

這意味着，(16807 * 22039) % 65536 == 1，因此，該

(16807 * 22039 * x) % 65536 == x

而且

k = (22039 * x) % 65536

所以你不必嘗試任何事情，你可以直接計算k。

來源

2014-02-20 09:50:05 harold

如果它正確引用了源（Warren，Henry S.，Jr .. * Hacker's Delight *。Boston：Addison-Wesley，2003），這個答案會更好。「mulinv 「，第195-197頁），指出該代碼已針對特定情況進行了修改，闡述了對修改代碼的限制，並解釋了代碼工作的原因。這種軟件開發的麻煩是像這樣的代碼中隱藏的部分被傳遞並插入到程序中，導致代碼不可維護。此代碼僅限於兩個小功率。一個循環把它擴展到其他兩個冪，而擴展歐幾里得算法則支持任何數字。 –

如果你有反覆查找k針對不同x，你可以建立解決方案的表，你開始解碼之前：

uint16_t g = 16807u; 
uint16_t *mods = malloc(0x10000 * sizeof(*mods)); 
int i; 

for (i = 0; i < 0x10000; i++) { 
    uint16_t x = g * i; // x is effectively x mod 2**16 

    mods[x] = i; 
};

的在16位範圍內的yor方程的解是：

uint16_t k = mods[x];

假設x是一個16位無符號整數。完成後請不要忘記free(mods)。

來源

2014-02-20 09:29:10

如果k是一個解決方案，那麼k+65536也是一個解決方案。

直截了當的蠻力方法找到的前k個（K> = 0）將是：

for (k=0; k < 65536; k++) { 
    if ((k*16807) % 65536 == x) { 
     // Found it! 
     break; 
    } 
} 
if (k=65536) { 
    // No solution found 
} 
return k;

來源

2014-02-20 09:29:15

您解決使用的16807的GCD和擴展歐幾里德算法65536

其餘序列與

R0=65536 
R1=16807

發起和逆與

V0=0 (V0*16807 == R0 mod 65536) 
V1=1 (V1*16807 == R1 mod 65536)

計算這樣那樣的問題

然後使用整數長分割，

Q1=R0/R1=3, 
R2=R0-Q1*R1=15115 
V2=V0-Q*V1=-3 (V2*16807 == R2 mod 65536) 

Q2=R1/R2=1, 
R3=R1-Q2*R2=1692 
V3=V1-Q2*V2=4 

Q3=8, R4=1579, V4=-35 
Q4=1, R5=113, V5=39 
Q5=13, R6=110, V6=-542 
Q6=1, R7=3,  V7=581 
Q7=36, R8=2,  V8=-21458 
Q8=1, R9=1,  V9=22039

使得22039被發現爲15115 65536模

來源

2014-02-20 17:17:22 LutzL

找到最小值，以滿足模數

回答

相關問題