1

我写了一个代码来绕过大数字：问题是，有一个小问题我似乎无法抓住它。它是准确的，直到指数或 b 为 2，然后是 3-4，稍微偏离，然后是 5-6，它才开始偏离真实答案。

#include <iostream>
#include <conio.h>
using namespace std;

unsigned long mul_mod(unsigned long b, unsigned long n, unsigned long m);

unsigned long exponentV2(unsigned long a, unsigned long b, unsigned long m);

int main()
{
    cout << exponentV2(16807, 3, 2147483647);
    getch();
}

unsigned long exponentV2(unsigned long a, unsigned long b, unsigned long m)
{
   unsigned long result = (unsigned long)1;
   unsigned long mask = b;    // masking

   a = a % m;
   b = b % m;

   unsigned long pow = a;

   // bits to exponent
   while(mask)
   {
     //Serial.print("Binary: ");  // If you want to see the binary representation,     uncomment this and the one below
     //Serial.println(maskResult, BIN);
      //delay(1000);  // If you want to see this in slow motion 
     if(mask & 1)
     {
            result = (mul_mod(result%m, a%m, m))%m;

           //Serial.println(result);  // to see the step by step answer, uncomment this
     }
     a = (mul_mod((a%m), (a%m), m))%m;
     //Serial.print("a is ");
     //Serial.println(a);
     mask = mask >> 1;          // shift 1 bit to the left

   }
   return result;
}

unsigned long add_mod(unsigned long a, unsigned long b, unsigned long m)
{
    a = a%m;
    b = b%m;
    return (a+b)%m;
}
4

1 回答 1

0

我只是看了你的代码，发现了几件事：

在功能上：

unsigned long exponentV2(unsigned long a, unsigned long b, unsigned long m);
  • 我知道这个函数返回 a^b mod m
  • 在初始化中，您销毁指数 (b=b%m) 这会使结果无效！！！删除该行

在功能上：

unsigned long add_mod(unsigned long a, unsigned long b, unsigned long m);
  • 你不处理溢出（如果 a+b 大于 long 怎么办？）
  • 在那种情况下 (a+b)%m 是错误的，...
  • 如果发生溢出，您应该从结果中减去 m*x 而不是取模。
  • x 必须一样大，所以 m*x 几乎是 long 的大小以消除溢出......
  • 所以 (a+b)-(m*x) 也适合长变量

要获得更多洞察力，请查看：模块化算法和 NTT（有限域 DFT）优化

希望能帮助到你

于 2013-09-03T13:55:50.337 回答