标签: modular-arithmetic

我有3个大的64位数字:A,B和C.我想计算:

(A x B) mod C

考虑到我的寄存器是64位,即写入a * b实际产生(A x B)mod2⁶⁴.

最好的方法是什么？我在C编码,但在这种情况下不认为语言是相关的.

在获得指向此解决方案的评论之后:

(a * b) % c == ((a % c) * (b % c)) % c

让我具体一点:这不是一个解决方案,因为((a%c)*(b%c))可能仍然大于2⁶⁴,寄存器仍会溢出并给我错误的答案.我会:

(((A mod C)x(B mod C))mod2⁶⁴)mod C.

在Rust中,我需要一个数字类型,其属性具有大约为0的域.如果数字n是有效值,则数字-n也必须有效.如何在初始化和算术期间确保类型安全？如何在类型上实现模块化和饱和算法？

最简单的问题示例是:

type MyNumber = i8; // Bound to domain (-100, 100)

fn main() {
    let a = MyNumber(128); // Doesn't panic when 128 > 100
}

需要考虑一些因素,我尝试了不同的解决方案.我将在下面的示例中避免泛型编程:

• 基于类型关闭枚举确保仅有效值是可能的值.这变得非常快:

  enum MyNumber {
      One,
      Two,
      ...
  }
  impl MyNumber {
      fn convert(i8) -> MyNumber {
          match {
              1 => MyNumber::One,
              2 => MyNumber::Two,
              ...
          }
      }
  }
  

  Run Code Online (Sandbox Code Playgroud)

• 在设置字段之前公开一种检查参数的方法,即教科书相关功能.这不会阻止使用struct构造函数进行赋值.

• 每当操作发生时,验证操作数(并强制纠正它们).这似乎是合理的,但要求每种方法重复验证代码.

  extern crate num;
  
  use num::Bounded;
  use std::cmp;
  struct MyNumber {
      val: i8,
  }
  
  impl Bounded for …

  Run Code Online (Sandbox Code Playgroud)

所以我遇到了这个需要计算的问题:

1 ^k +(1 + p)^k +(1 + 2*p)^k + ..... +(1 + n*p)^k%p

其中p是素数,k是严格小于p的某个数.

p小于500,n*p的范围可达10 ⁹

我能想到的唯一解决方案是从第一个术语到最后一个术语进行迭代,并使用取幂来计算模数,但这样做太昂贵了我正在寻找更快的算法.

是否可以更快地完成？

我想计算P _s mod K，其中P _s是集合S中元素的唯一排列的总数。问题是，集合S可以有重复，所以P _s = n！/（f ₁！f ₂！... f _n！），其中n是元素的数量，分母是S中每个元素的频率阶乘的乘积。

可以假设整数n很大，例如，大约10^6不大可能适合a uint64_t。甚至可以在不借助任意精度库的情况下计算P _s mod K？如果是，是否有任何快速方法可以计算出来？

我有一个由 M 个整数组成的数组。我必须找到所有可能的整数 K（假设至少有 1 K），使得：

1) K > 1
2) arr[0]%K = arr[1]%K = arr[2]%K = ... = arr[M-1]%K 

这个问题的最佳算法是什么？

我的代码的瓶颈是对非常大的整数重复调用 pow(base,exponent,modulus)（numpy 不支持这么大的整数，大约 100 到 256 位）。但是，我的指数和模数始终相同。我可以以某种方式利用它来通过自定义函数加速计算吗？我尝试定义一个函数，如下所示（下面的函数用于一般模数和指数）。

然而，即使我在没有 while 循环和 if 语句的情况下对固定指数和模数的每个操作进行硬编码，它也比 pow 慢。

def modular_pow(self, base, exponent, modulus):
    result = 1
    base = base % modulus
    while exponent > 0:
        if (exponent % 2 == 1):
            result = (result * base) % modulus
        exponent = exponent >> 1
        base = (base * base) % modulus
    return result

另一种选择是如果我能以某种方式“矢量化”它。我必须计算大约 100000000 个不同基值的 pow。虽然这些值在我的脚本运行之间经常发生变化（因此查找表没有用），但我在运行时就会知道这些值（我可以立即计算它们）。

有任何想法吗？我通过使用 gmpy2 中的 mpz 数据类型获得了一些加速，但它仍然太慢。

我试图计算大数字的下面的表达式.

由于这个表达式的值会非常大,我只需要这个表达式的值为一些素数.假设这个表达式的值是x,我选择素数1000000007; 我在找x % 1000000007.

这是我的代码.

#include<iostream>
#define MOD 1000000007
using namespace std;
int main()
{
    unsigned long long A[1001];
    A[2]=2;
    for(int i=4;i<=1000;i+=2)
    {
        A[i]=((4*A[i-2])/i)%MOD;
        A[i]=(A[i]*(i-1))%MOD;

    while(1)
    {
        int N;
        cin>>N;
        cout<<A[N];
    }
}

但是即使这么多的优化也没有大的N值.例如,如果N是50,正确的输出是605552882,但这给了我132924730.如何进一步优化以获得正确的输出？

注意:我只考虑N为偶数.

我正在阅读以下有关如何使用Intel Westmere和AMD Bulldozer中引入的PCLMULQDQ指令有效实现CRC32的文章:

V. Gopal等."使用PCLMULQDQ指令对通用多项式进行快速CRC计算." 2009. http://www.intel.com/content/dam/www/public/us/en/documents/white-papers/fast-crc-computation-generic-polynomials-pclmulqdq-paper.pdf

我理解算法,但我不确定的一件事是如何计算常数$ k_i $.例如,它们为IEEE 802.3多项式提供常量值:

• k1 = x ^(4*128 + 64)mod P(x)= 0x8833794C
• k4 = x ^ 128 mod P(x)= 0xE8A45605
• mu = x ^ 64 div P(x)= 0x104D101DF

等等.我可以使用这些常量,因为我只需要支持一个多项式,但我很感兴趣:他们是如何计算这些数字的？我不能只使用典型的bignum实现(例如Python提供的实现),因为算法必须在GF(2)中进行.

我正在研究这个看似简单的问题,我需要在数字的每个数字上加一个.示例:number = 1234; 输出= 2345

这很简单,但当9是其中一个数字时,那么根据加法则,9将被0替换,1将被添加到左边的数字(9 + 1 = 10,因此,地方值= 0 &carry over = 1)例如:number = 1239; 输出= 2350

number = 1234
s = str(number)
l = []

for num in s:
    num = int(num)
    num += 1
    if num > 9:
        num = 0
        l.append(num)
    else:
        l.append(num)

print int(''.join(str(v) for v in l))

有人可以向我解释一下,我应该使用什么逻辑？我可以看到模块化算术的一些东西,但不确定如何实现它.谢谢 :)

如何找到0到n模数10 ⁹ + 7 的数字总和，其中n≤10 ¹⁸？

我只想将结果存储在long long int中，而不是存储在数组或字符串中。我的代码导致运行时错误。

const unsigned int m = 1000000007;

long long int n;
cin >> n;
long long int s = 0;
for (long long int i = 0; i < n; i++) {
    s = ((s % m) + (i % m)) % m;
}
cout << s << endl;