找到最小值，以满足模数

即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

找到最小值，以满足模数

回答

相关问题