标签: modulo

我注意到Python和Java中模数运算符的不同实现.

例如,在Python中:

>>> print -300 % 800
>>> 500

在Java中:

System.out.println(-300 % 800);
-300

这让我措手不及,因为我认为像模数一样基本的东西被普遍解释为同样的方式.我喜欢Python的解释(我认为它是从C借用的),尽管我看到了Java实现背后的逻辑.

你通常更喜欢哪一个？有不同解释的具体原因吗？我无意开始语言大战,只是好奇.

如果这是一个简单的问题,我很抱歉,但是当第一个数字小于第二个数字时,我无法理解模数除法的概念.例如,当我的书中1%4表示余数为1.我不明白1是1%4的剩余部分
.1/4是0.25.我在考虑模数除法错误吗？

是否记录了确切的行为str.__mod__？

这两行代码按预期工作：

>>> 'My number is: %s.' % 123
'My number is: 123.'
>>> 'My list is: %s.' % [1, 2, 3]
'My list is: [1, 2, 3].'

此行也按预期运行：

>>> 'Not a format string' % 123
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: not all arguments converted during string formatting

但是这条线是什么以及为什么它不会引发任何错误？

>>> 'Not a format string' % [1, 2, 3]
'Not a format string'

聚苯乙烯

>>> print(sys.version)
3.3.2 (default, Aug 15 2013, …

所以我最近一直在努力实施Miller-Rabin素性测试.我将它限制在所有32位数字的范围内,因为这是一个非常有趣的项目,我正在做的是熟悉c ++,我不想使用64位的任何东西.一会儿.另外一个好处是该算法对于所有32位数字都是确定性的,因此我可以显着提高效率,因为我确切知道要测试的证人.

因此对于较低的数字,该算法工作得非常好.但是,该过程的一部分依赖于模幂运算,即(num ^ pow)%mod.所以,例如,

3 ^ 2 % 5 = 
9 % 5 = 
4

这是我用于此模幂运算的代码:

unsigned mod_pow(unsigned num, unsigned pow, unsigned mod)
{
    unsigned test;
    for(test = 1; pow; pow >>= 1)
    {
        if (pow & 1)
            test = (test * num) % mod;
        num = (num * num) % mod;
    }

    return test;

}

正如您可能已经猜到的那样,当参数都是特别大的数字时会出现问题.例如,如果我想测试数字673109的素数,我将在某一点上必须找到:

(2 ^ 168277)%673109

现在2 ^ 168277是一个特别大的数字,并且在过程的某个地方它溢出测试,这导致不正确的评估.

在反面,诸如的论点

4000111222 ^ 3%1608

由于同样的原因,也评估不正确.

有没有人对模块取幂有一些建议,可以防止这种溢出和/或操纵它产生正确的结果？(我看到它的方式,溢出只是模数的另一种形式,即num%(UINT_MAX + 1))

如何在Java中找到两个长值的模数(%)？我的代码说'整数太大'后跟我想要修改的数字.我尝试将它投入很长时间但它没有用.我是否必须将其转换为BigInteger并使用余数方法？谢谢.

我正在为一个非常有限的系统编写一些代码,其中mod运算符非常慢.在我的代码中,模数需要每秒使用大约180次,并且我认为尽可能地删除它会显着提高代码的速度,因为现在我的主循环的一个循环不会在1/60的情况下运行应该是第二个.我想知道是否有可能仅使用乘法和除法可能的位移来重新实现模数.所以这是我目前在c ++中的代码(如果我可以使用汇编执行模数,那就更好了).如何在不使用除法或乘法的情况下删除模数？

    while(input > 0)
{
    out = (out << 3) + (out << 1);
    out += input % 10;

    input = (input >> 8) + (input >> 1);
}

编辑:其实我意识到我需要每秒超过180次.看作输入值可以是一个非常大的数字,最多40位数.

我想检查一个浮点值是否"几乎"是32的倍数.例如64.1"几乎"可被32整除,因此是63.9.

现在我这样做:

#define NEARLY_DIVISIBLE 0.1f
float offset = fmodf( val, 32.0f ) ;
if( offset < NEARLY_DIVISIBLE )
{
    // its near from above
}
// if it was 63.9, then the remainder would be large, so add some then and check again
else if( fmodf( val + 2*NEARLY_DIVISIBLE, 32.0f ) < NEARLY_DIVISIBLE )
{
    // its near from below
}

有更好的方法来做到这一点？

此脚本语言没有%或Mod().我有一个Fix(),它可以删除数字的小数部分.我只需要积极的结果,所以不要太强大.

我最近一直试图实现模块化指数器.我正在用VHDL编写代码,但我正在寻找更具算法性质的建议.模幂运算器的主要组件是模块化乘法器,我也必须自己实现.我对乘法算法没有任何问题 - 它只是添加和移位而且我已经很好地弄清楚了所有变量的含义,以便我可以在相当合理的时间内繁殖.

我遇到的问题是在乘法器中实现模数运算.我知道重复减法会有效,但也会很慢.我发现我可以改变模数以有效地减去模数的大倍数,但我认为可能还有更好的方法来做到这一点.我正在使用的算法是这样的(奇怪的伪代码如下):

result,modulus : integer (n bits) (previously defined)
shiftcount : integer (initialized to zero)
while( (modulus<result) and  (modulus(n-1) != 1) ){
     modulus = modulus << 1
     shiftcount++
}
for(i=shiftcount;i>=0;i--){
     if(modulus<result){result = result-modulus}
     if(i!=0){modulus = modulus >> 1}
}

所以...这是一个很好的算法,或者至少是一个好的开始？维基百科并没有真正讨论用于实现模运算的算法,每当我尝试在其他地方搜索时,我发现它真的很有趣,但却非常复杂(通常是无关的)研究论文和出版物.如果有一种明显的方法可以实现这一点,我没有看到,我真的很感激一些反馈.

我试图从某些内部方法中获得尽可能多的性能。

Java代码是：

List<DirectoryTaxonomyWriter> writers = Lists.newArrayList();
private final int taxos = 4;

[...]

@Override
public int getParent(final int globalOrdinal) throws IOException {
    final int bin = globalOrdinal % this.taxos;
    final int ordinalInBin = globalOrdinal / this.taxos;
    return this.writers.get(bin).getParent(ordinalInBin) * this.taxos + bin; //global parent
}

在我的分析器中，我看到 1% 的 CPU 支出java.util.Objects.requireNonNull，但我什至不称之为。在检查字节码时，我看到了：

 public getParent(I)I throws java/io/IOException 
   L0
    LINENUMBER 70 L0
    ILOAD 1
    ALOAD 0
    INVOKESTATIC java/util/Objects.requireNonNull (Ljava/lang/Object;)Ljava/lang/Object;
    POP
    BIPUSH 8
    IREM
    ISTORE 2

所以编译器会生成这个（没用的？）检查。我在原语上工作，null无论如何都不能，那么编译器为什么会生成这一行？这是一个错误吗？还是“正常”行为？

（我可能会使用位掩码，但我只是好奇）

[更新]

1. 运营商似乎与它无关（请参阅下面的答案）

2. 使用 …