java - 执行时间 : Boost Multi-precision vs Java BigInteger

Question

我正在尝试实现 Lucas–Lehmer 素性测试。

我有两个实现，一个用C++，另一个用Java，如下:

C++:

int p = 86243;
cpp_int M;

bit_set(M, p);
M = M-1; // M = 2^p - 1;

cpp_int S;
S = 4;

while(p>2) {
         S = pow(S, 2);
         S -= 2;

         S %= M;
         p--;         
}

Java:

int p = 86243;

BigInteger M = BigInteger.ZERO;
BigInteger Two = BigInteger.valueOf(2L);

M = M.setBit(p);
M = M.subtract(BigInteger.ONE); // M = 2^p - 1;

BigInteger S = BigInteger.valueOf(4L);

while(p>2) {
         S = S.pow(2).subtract(Two).mod(M);
         p--;        
}

Java 代码运行速度比 C++ 代码快得多，对于 C++，我使用 CodeBlocks 和 Eclipse for Java。

有什么理由吗？我是否遗漏了什么，特别是在 C++ 代码中？任何建议将不胜感激。

Answer 1

我认为您不应该期望这两个程序(Java 和 C++ 版本)是等价的。性能主要取决于所使用的算法而不是语言。在探查器中运行 C++ 版本表明鸿沟(即 mod)是瓶颈。如果您随后查看分界线的来源 (/boost/multiprecision/cpp_int/divide.hpp)，您会看到这条评论:

Very simple, fairly braindead long division. [...] Note that there are more efficient algorithms than this available, in particular see Knuth Vol 2. However for small numbers of limbs this generally outperforms the alternatives and avoids the normalisation step which would require extra storage.

然而，Java 中的 BigInteger 实现使用称为 Knuth 和/或 BurnikelZiegler 的算法。似乎这些更适合更大的数字。如果性能真的很重要，您可以尝试使用 gnu 多精度库 (gmp)。在我的机器上，gmp 版本大约比 Java/BigInteger 快 3 倍:

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

int main()
{
    int p = 86243;
    mpz_t M;
    mpz_init(M);
    mpz_set_ui(M, 0);
    mpz_setbit(M, p);
    mpz_sub_ui(M, M, 1); // M = 2^p - 1;

    mpz_t S;
    mpz_init(S);
    mpz_set_ui(S, 4);

    while(p > 2) {
        mpz_pow_ui(S, S, 2);
        mpz_sub_ui(S, S, 2);

        mpz_mod(S, S, M);

        p--;
    }
    int r = mpz_get_ui(S);
    cout << "Is mersenne prime: " << (r == 0 ? "yes" : "no") << endl;
    return 0;
}

与 -lgmp 链接