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) も long 変数に適合します。

詳細については、これを参照してください:モジュラー演算と NTT (有限体 DFT) の最適化

それが役に立てば幸い

于 2013-09-03T13:55:50.337 に答える