标签: modulo

在32位整数数学中,add和multiply的基本数学运算隐式计算mod 2 ^ 32,这意味着你的结果将是add或multiply的最低位.

如果要使用不同的模数计算结果,您当然可以使用不同语言的任意数量的BigInt类.对于值a,b,c <2 ^ 32,您可以计算64位长整数的中间值,并使用内置的%运算符减少到右侧的答案

但是我被告知,当C的形式为(2 ^ N)-1或(2 ^ N)+1时,有一些特殊的技巧可以有效地计算a*b mod C,它们不使用64位数学或一个BigInt库,非常高效,比任意模数评估更有效,并且还可以正确计算在包含中间乘法时通常会溢出32位int的情况.

不幸的是,尽管听说这种特殊情况有快速的评估方法,但实际上我还没有找到该方法的描述."那不是在Knuth吗？" "这不就是维基百科上的某个地方吗？" 是我听到的咕噜声.

它显然是随机数生成器中的常用技术,其执行a*b mod 2147483647的乘法,因为2147483647是等于2 ^ 31 -1的素数.

所以我会问专家.什么是这个聪明的特殊情况乘法与mod方法,我找不到任何讨论？

当我在Objective-C中进行模运算时,我得到的结果让我有点吓坏了.-1%3现在是-1,这不是正确的答案:根据我的理解,它应该是2. -2%3出现-2,这也是不对的:它应该是1.

除了%运算符之外,我还应该使用另一种方法来获得正确的结果吗？

我有计算和S =(a*x + b*y + c)%N.是的,它看起来像一个二次方程但不是因为x和y有一些属性,必须使用一些递归关系计算.因为总和超过了无符号long long的限制,我想知道如何使用模运算的属性来计算总和,这些属性允许写入类似的总和(我说的是因为我不记得确切这些属性如何):( a*x)%N +(b*y)%N + c%N,因此避免超过无符号长long的限制.

提前感谢您的关注!:)

我需要优化一些代码,其中我将一个int(32位)的向量乘以标量模p(其中p是素数(2 ^ 32)-5),然后从另一个向量模p中减去该向量.

代码如下所示:

public static void multiplyAndSubtract(long fragmentCoefficient, long[] equationToSubtractFrom, long[] equationToSubtract) {
    for (int i = 0; i < equationToSubtractFrom.length; i++) {
        equationToSubtractFrom[i] =  modP(equationToSubtractFrom[i] - multiplyModP(fragmentCoefficient, equationToSubtract[i]));
    }
}

我使用longs因为Java不支持无符号整数但两个向量都是mod p所以你可以期望每个数字都是0 <= x <(2 ^ 32)-5

有什么想法来优化这个？mod p操作占用了大部分执行时间,因此优化这种方法的一种方法可能是在乘法后不知道怎么做modP并且只在减法后做.有关如何做到这一点的任何想法？

我正在使用OpenCV 2.2运行Ubuntu 11.10(联想T400)(我相信导入是作为cv导入cv2.cv完成的).如果我只是'导入cv',也会发生这个问题.

我最近开始遇到这个问题,这有点奇怪.我不知道我做了什么重要的事情,自从它开始发生以来我已经重新启动了.我安装了几个程序,但我不认为这会影响到这一点.

当我使用人工图像显示(只是一个黑色图像)时,我尝试轮询cv.WaitKey(10).它吐回垃圾.

这是我的OpenCV代码:

import cv2.cv as cv
import time

cv.NamedWindow("camera", 1)
img = cv.CreateImage((400,400), 8, 3)
valkeys = range(1,255)
f = open('/home/andrew/webuploads/keyboardtest', 'wb')
while True:
    cv.ShowImage("camera", img)
    k = cv.WaitKey(10)
    if k is -1:
        pass
    else:
        print 'writing %s' %str(k)
        f.write((str(k)+' '))

f.close()

这是我从程序中得到的输出:

1048678 1048676 1048673 1048691 1048676 1048678 1048689 1048695 1048677 1048688 1048687 1048681 1048677 1048677 1048695 1048624 1048633 1048690 1048633 1048624 1048695 1048677 1048690 1048624 1048633 1048681 1048677 1048681 1048688 1048687 1048677 1048681 1048692 …

Python中的模数令人困惑.

在Python中,%运算符正在计算余数:

>>> 9 % 5
4

然而:

>>> -9 % 5
1

为什么结果1？不是-4吗？

为什么:

int test() {
    return 00101 % 10;
}

返回5,同时:

int test() {
    return 101 % 10;
}

回来了1？我想不出一个解释.

从"编程珍珠"一书中解释(关于旧机器上的c语言,因为本书是从90年代后期开始的):

整数算术运算(+,-,*),而可能需要大约10纳秒%操作员最多需要100毫微秒.

• 为什么会有这么大的差异？
• 模数运算符如何在内部工作？
• /在时间方面它与division()相同吗？

我试图按升序排序任何长度的整数的数字,而不使用字符串,数组或递归.

例:

Input: 451467
Output: 144567

我已经弄清楚如何用模数除法得到整数的每个数字:

int number = 4214;

while (number > 0) {
    IO.println(number % 10);
    number = number / 10;
}

但我不知道如何在没有数组的情况下订购数字.

不要担心IO上课; 这是我们教授给我们的定制课程.

我是一名计算机科学专业的学生；我正在独立学习算法课程。

在课程中，我看到了这样一个问题：

\n

给定一个n位整数N，找到一个多项式（n）时间算法来决定N是否为幂（即，存在整数a和k> 1，使得a^k = N）。

\n

我想到了第一个选项，它是 n 的指数：\n对于所有 k ， 1<k<N ，尝试将 N 除以 k 直到得到结果 1。

例如，如果 N = 27，我将从 k = 2 开始，因为 2 不能整除 27，我将转到下一个 k =3。\n我将除以 27 / 3 得到 9，然后再次除以直到我将得到 1。这不是一个好的解决方案，因为它是 n 的指数。

我的第二个选择是使用模算术，如果 gcd(a, k+1 ) = 1 （欧拉定理），则使用^{k \xe2\x89\xa1 1 mod (k+1) 。}我不知道a和k是否互质。

我正在尝试编写一个算法，但我很难做到：

function power(N)\nInput: Positive integer N\nOutput: yes/no\nPick positive integers a_1, a_2, . . . , a_k < N …