执行时间：提升多精度与 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 Java。

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

Answer 1

您可以使用可用的内置时钟功能来检查比较。这是此 C++ 和 Java 代码

的比较

C++ -> https://ideone.com/oj07xQ

Java -> https://ideone.com/MsAgil

您可以看到 C++ 花费了 1933.19 毫秒，而 Java 花费了 2257.244454 毫秒

您无法比较不同 IDE 的速度，例如 CodeBlocks 和 Eclipse

#include<bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using boost::multiprecision::cpp_int;
using namespace std;

int32_t main() {
    int start = clock();
    int p = 8624;
    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--;         
    }
    // cout << S << endl;
    int end = clock();
    cout << "time: " << (end - start)/(double)(CLOCKS_PER_SEC)*1000 << " milliseconds\n";
}

import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        long startTime = System.nanoTime();
        int p = 8624;
        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--;        
        }
        // System.out.println(S);
        long endTime = System.nanoTime();
        System.out.println("Took "+(endTime - startTime) + " ns"); 

    }
}

Answer 2

我认为您不应期望这两个程序（Java 和 C++ 版本）是等价的。性能主要取决于所使用的算法而不是语言。运行分析器中的 C++ 版本显示除法（即 mod）是 bottle-neck。如果您随后查看鸿沟的来源 (/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 and/or BurnikelZiegler 的算法。似乎这些更适合更大的数字。如果性能真的很重要，您可以尝试使用 gnu multi-precision 库 (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;
}

Link 与 -lgmp

执行时间：提升多精度与 Java BigInteger

Execution Time: Boost Multi-precision vs Java BigInteger

c++

java

primes

boost

biginteger