我一直收到错误"对于参数类型,运算符%是未定义的整数,整数"我不太确定为什么会发生这种情况.我认为,因为模块化除法不能返回具有整数值的小数.
这是在我正在创建的程序中的方法中发生的.代码如下:
public void addToTable(Integer key, String value)
{
Entry<Integer, String> node = new Entry<Integer, String>(key, value);
if(table[key % tableSize] == null)
table[key % tableSize] = node;
}
该方法未完成但错误发生在
if(table[key % tableSize] == null)
和
table[key % tableSize] = node;
任何帮助或建议将不胜感激.
作为一个业余爱好项目,我正在努力寻找真正庞大的素数.对此的素性测试包含模幂运算,即a ^ modn.让我们称之为modpow操作,以使解释变得简单.我想加快这个特定的计算.
目前我正在使用GMP的mpz_pown函数,但是,它有点慢.我认为它太慢的原因是因为对GMP的modpow的函数调用比对相同大数字的PFGW软件的完整素性测试要慢.(所以要清楚,这只是GMP的modpow部分,而不是我正在比较的整个自定义素性测试程序).PFGW被认为是其领域中最快的,对于我的用例,它使用了Brillhart-Lehmer-Selfridge素性测试 - 它也使用了modpow程序 - 所以不是因为数学上的聪明,PFGW在这方面更快(请纠正我,如果我错了.)看起来GMP的瓶颈是modpow操作.数字的示例运行时间略超过20,000个数字:GMP的modpow操作大约需要45秒,而PFGW在9秒内完成整个素数测试(包括一个modpow).对于更大的数字,差异变得更加令人印象深刻.GMP使用FFT乘法和蒙哥马利减少进行此测试比较,请参阅下面这篇文章的评论.
我做了一些研究.到目前为止,我理解modpow算法通过平方,整数乘法和模数减少使用取幂 - 这些对我来说都非常熟悉.几种辅助方法可以改善整数乘法的运行时间:
为了通过平方部分来改善取幂的运行时间,可以使用有符号的数字表示来减少乘法的数量(即,比特表示为0,1或-1,并且比特串以这样的方式表示,使得它包含的零比原始的base-2表示更多 - 这通过平方减少了求幂的运行时间.
为了优化操作的模数部分,我知道这些方法:
所以这是150,000美元的问题:有一个软件库可以在给定非常大的基数,指数和模数的情况下有效地进行modpow操作吗？(我的目标是数百万的数字).如果您想建议一个选项,请尝试解释算法的内部工作原理,包括基数,模数和指数的数百万位数,因为有些库根据位数使用不同的算法.基本上我正在寻找一个支持上述技术的库(或者可能更聪明的技术),并且它在运行算法时应该运行良好(至少比GMP好).到目前为止,我已经搜索,发现并尝试了GMP和PFGW,但没有发现这些令人满意(PFGW很快,但我只对modpow操作感兴趣并且没有直接的编程接口).我希望可能是该领域的专家可以建议具有这些功能的库,因为似乎很少有能够处理这些要求的库.
编辑:使问题更简洁,因为它标记得太宽泛.
在我的项目中,问题的一部分就在那里.但为了简化,这里的问题正在制定中.有两个正的共素整数:a和b,其中a < b.列出a从1到1的倍数,b-1然后是模数运算b.
a mod b,2*a mod b,3*a mod b,...,(b-1)*a mod b
现在,还有另一个整数n ( 1 <= n < b).通过n列表中的第一个数字,我们必须找到多少数字,比如说m(1 <= m < b).这可以用蛮力方法完成,从而给出一个 O(n).
一个例子:
a=6, b=13, n=8, m=6
清单是:
6, 12, 5, 11, 4, 10, 3, 9, 2, 8, 1, 7
这是从1到12的数字的排列,因为如果我们包括另一个数,即任何两个共素的模运算产生数字的排列,即0.如果我们采取a= 2, b=13,那么列表将是2, 4, 6, 8, …
我正在尝试用Mersenne prime(2 31 -1)作为模数来实现随机数生成器.以下工作代码基于几个相关的帖子:
然而,
它不起作用uint32_t hi, lo;,这意味着我不理解问题的签名与未签名方面.
基于上面的#2,我期待答案是(hi + lo).这意味着,我不明白为什么需要以下声明.
if (x1 > r)
x1 += r + 2;
有人可以澄清我的困惑的来源吗？
代码本身可以改进吗？
发电机应该避免0或2 31 -1作为种子吗？
如何为一个素数(2 p -k)改变代码？
#include <inttypes.h>
// x1 = a*x0 (mod 2^31-1)
int32_t lgc_m(int32_t a, int32_t x)
{
printf("x %"PRId32"\n", x);
if (x == 2147483647){
printf("x1 %"PRId64"\n", 0);
return (0);
}
uint64_t c, r = 1;
c = (uint64_t)a * (uint64_t)x;
if (c < 2147483647){
printf("x1 …最近我发现mod('%')运算符非常慢.所以我创建了一个像%b一样工作的函数.但它比mod运算符更快吗？
这是我的功能
int mod(int a, int b)
{
int tmp = a/b;
return a - (b*tmp);
}
我想用以下约束计算 nCk mod m：
n<=10^18
k<=10^5
m=10^9+7
我读过这篇文章：
但是这里m的值为1009。因此使用卢卡斯定理，我们只需要计算aCb的1009*1009个不同值，其中a,b<=1009
如何在上述约束下做到这一点。我无法在给定的约束下制作 O(m*k) 空间复杂度的数组。
帮助！
c++ algorithm binomial-coefficients modulus modular-arithmetic
我看到很多有竞争力的程序员用((a + b) % d + d) % dC++ 编写代码.他们为什么不使用(a + b) % d？+ d括号里面有什么用？它与负数有关吗？
谢谢
这是我在学校做的一项任务.我在生成私钥时遇到问题.我的主要问题是理解我的方程式之间的关系.为了设置一切,我们有:
p = 61
q = 53
n = p * q (which equals 3233)
从这里我们得到n(phi(n))的总数等于3120,现在我们可以选择素数e; 其中1 <e <3120
e = 17
好的很容易.
对于我的任务,我们已经意识到d = 2753,但是我仍然需要能够任意生成这个值.
现在这里是我遇到麻烦的地方.我一直在仔细阅读维基百科以及某些东西没有连接.我知道,我需要找到模反元素的e (mod phi(n)),这将是d我们的私人指数.
通过维基百科阅读告诉我们找到mmi我们需要使用扩展欧几里德算法.我在python中实现了如下算法:
def egcd(a, b):
x, lastX = 0, 1
y, lastY = 1, 0
while (b != 0):
q = a // b
a, b = b, a % b
x, lastX = lastX - q * x, x …-当 x 是二进制数时如何找到 x mod 3？不允许使用转换为十进制然后使用 % 运算符。
-eg- 如果 x 是 1101 那么输出应该是 1 但不要将 1101 转换为 13 然后通过 % 3 找到
模逆可以计算如下（来自Rosetta Code）：
#include <stdio.h>
int mul_inv(int a, int b)
{
int b0 = b, t, q;
int x0 = 0, x1 = 1;
if (b == 1) return 1;
while (a > 1) {
q = a / b;
t = b, b = a % b, a = t;
t = x0, x0 = x1 - q * x0, x1 = t;
}
if (x1 < 0) x1 += b0;
return x1;
}
但是，ints如您所见，输入为 。上面的代码是否也适用于无符号整数（例如 …
math integer-overflow greatest-common-divisor modular-arithmetic