Execution Time: Boost Multi-precision vs Java BigInteger

Question

I'm trying to Implement the Lucas–Lehmer primality test.

I've two implementations, one in C++ and other in Java, These are follows:

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--;        
}

The Java code runs much faster than C++ code, for C++ I'm using CodeBlocks and Eclipse for Java.

Any reason for that? Am I missing anything particularly in C++ code? Any suggestions will be appreciated.

Did you compile with optimizations turned on (release build)? — NathanOliver, Jul 18 '19 at 15:18
"much faster" is vague. Can you quantify? If yes, how do you quantify? Anyway, here is a part of the answer: those are different languages — jhamon, Jul 18 '19 at 15:20
Writing a micro benchmark in Java is non-trivial, see [How do I write a correct micro-benchmark in Java?](https://stackoverflow.com/q/504103/1602555). You definitely shouldn't benchmark this from IDE. — Karol Dowbecki, Jul 18 '19 at 15:23
Much faster means Java completed the execution one third of time than c++. — User_67128, Jul 18 '19 at 15:23
In C++ difference of executing speed of optimized and non optimized code is very significant, so it is quite pointless to measure speed of non optimized code. — Slava, Jul 18 '19 at 16:23
Later versions of Java use advanced algorithms for multiplication and division that perform substantially better than the usual O(n*n) algorithms that are normally used for cryptographic-sized numbers and below. For comparison, GMP also uses these advanced algorithms and would represent a better challenger. — President James K. Polk, Jul 18 '19 at 20:00

Aman Raj · Answer 1 · 2019-07-18T15:47:08.600

You can check the comparison by using inbuilt clock function available. Here is the comparison of this C++ and Java code

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

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

You can see C++ is taking 1933.19 milliseconds while Java is taking 2257.244454 milliseconds

You can not compare speed on different IDE's like CodeBlocks and 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"); 

    }
}

*You can not compare speed on different IDE's like CodeBlocks and Eclipse* Why not, we do it all of the time. You just need to make sure your compiling with the same/equivalent settings. — NathanOliver, Jul 18 '19 at 15:37
Also note that most likely IDEOne is not using the same compiler either for C++ and Java. — NathanOliver, Jul 18 '19 at 15:38
For smaller input (for p) both programs behaves almost same in my machine as well, I am interested only larger values of p, in million range. Where C++ runs very slow (3 to 4 times slower) compared with Java program. @Aman Raj. — User_67128, Jul 18 '19 at 15:43
I tried and run it and largest value I can run on my system was P = 10000. Even at this number C++ is working faster than Java. Take a look at this [cpp_int](https://www.boost.org/doc/libs/1_67_0/libs/multiprecision/doc/html/boost_multiprecision/tut/ints/cpp_int.html) and [BigInteger](https://coderanch.com/t/588080/java/BigInteger-Peformance) . As the number is larger and larger both will try to take exponential time. @Manoj Banik — Aman Raj, Jul 18 '19 at 21:31

score 3 · Accepted Answer · answered Jul 18 '19 at 17:40

I think you should not expect both programs (Java and C++ versions) to be equivalent. The performance depends mostly on the algorithms used rather than the language. Running the C++ version in a profiler shows that the divide (i.e. mod) is the bottle-neck. If you then look at the source of the divide (/boost/multiprecision/cpp_int/divide.hpp) you can see this comment:

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.

The BigInteger implementation in Java however uses algorithms called Knuth and/or BurnikelZiegler. Seems like these are better suited for larger numbers. If performance really matters you can try to use the gnu multi-precision library (gmp). On my machine the gmp version is roughly 3x faster than Java/BigInteger:

#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 with -lgmp

Execution Time: Boost Multi-precision vs Java BigInteger

2 Answers2