Guest User

mersenne.cpp

a guest
Feb 9th, 2018
51
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // g++ -O3 -Wall -o mersenne mersenne.cpp --std=c++14 -lgmp -lpthread
  2. #include <iostream>
  3. #include <vector>
  4. #include <future>
  5. #include <boost/multiprecision/gmp.hpp>
  6.  
  7. using namespace boost::multiprecision;
  8.  
  9. // returns 2^exp - 1
  10. mpz_int power(const uint64_t exp)
  11. {
  12.     mpz_int number = 2;
  13.     for (uint64_t i = 1; i < exp; ++i) {
  14.         number *= 2;
  15.     }
  16.    
  17.     number--;
  18.    
  19.     return number;
  20. }
  21.  
  22. // Performs LL test for exp if exp is odd
  23. bool lucas_lehmer(uint64_t exp)
  24. {  
  25.     uint64_t res = exp;
  26.    
  27.     // corner cases
  28.     if (exp == 2) {
  29.         std::cout << "M" << res << " " << std::flush;
  30.         return true;
  31.     }
  32.     else if (exp%2 == 0) return false;
  33.    
  34.     // main calc
  35.     mpz_int s = 4;
  36.     mpz_int number = power(exp);
  37.    
  38.     while (exp > 2) {
  39.         s = (s*s - 2) % number;
  40.         exp--;
  41.     }
  42.    
  43.     if (s == 0) {
  44.         std::cout << "M" << res << " " << std::flush;
  45.         return true;
  46.     }
  47.     else return false;
  48. }
  49.  
  50. auto async_worker(const uint64_t n)
  51. {
  52.     std::vector<std::future<bool>> fut;
  53.     fut.reserve(n);
  54.    
  55.     for (uint64_t i = 1; i<=n; ++i) {
  56.         fut.push_back(std::async(lucas_lehmer, i));
  57.     }
  58.    
  59.     return fut;
  60. }
  61.  
  62.  
  63. int main(int argc, char* argv[])
  64. {
  65.     uint64_t n = 43112609;
  66.     if (argc > 1) n = std::stoul(argv[1]);
  67.    
  68.     auto vec = async_worker(n);
  69.    
  70.     for (auto& i: vec) {
  71.         i.get();
  72.     }
  73.    
  74.    
  75.     return 0;
  76. }
RAW Paste Data