The Computer Language
Benchmarks Game

pidigits C++ g++ #3 program

source code

/* The Computer Language Benchmarks Game
 * http://benchmarksgame.alioth.debian.org/
 *
 * contributed by Marcin Zalewski & Jeremiah Willcock
 */


#include <iostream>
#include <gmpxx.h>
#include <boost/lexical_cast.hpp>
#include <boost/tuple/tuple.hpp>
#include <algorithm>

using namespace boost;

class Digits {
private:
  unsigned int j;
  tuple<mpz_class, mpz_class, mpz_class> nad;
  mpz_class tmp1, tmp2;

public:
  Digits() { j = 0; get<0>(nad) = 1; get<1>(nad) = 0; get<2>(nad) = 1; }

  inline char operator()() {
    ++j;
    next_term();

    if(get<0>(nad) > get<1>(nad)) return (*this)();

    mpz_mul_2exp(tmp1.get_mpz_t(), get<0>(nad).get_mpz_t(), 1);
    tmp1 += get<0>(nad);
    tmp1 += get<1>(nad);

// "Uses only one bigint division instead of two when checking a produced digit's validity."

//    mpz_fdiv_qr(tmp1.get_mpz_t(), tmp2.get_mpz_t(), tmp1.get_mpz_t(), get<2>(nad).get_mpz_t());

    tmp2 += get<0>(nad);

    if(tmp2 >= get<2>(nad)) {
      return (*this)();
    } else {
      unsigned int d = tmp1.get_ui();
      eliminate_digit(d);
      return d + '0';
    }
  }

private:

  inline void next_term() {
    unsigned int y = j * 2 + 1;
    mpz_mul_2exp(tmp1.get_mpz_t(), get<0>(nad).get_mpz_t(), 1);
    get<1>(nad) += tmp1;
    get<1>(nad) *= y;
    get<0>(nad) *= j;
    get<2>(nad) *= y;
  }

  inline void eliminate_digit(unsigned int d) {
    mpz_submul_ui(get<1>(nad).get_mpz_t(), get<2>(nad).get_mpz_t(), d);
    get<0>(nad) *= 10;
    get<1>(nad) *= 10;
  }

};

void pi(unsigned int n) {
  unsigned int i = 0;
  Digits digits;

  while((i += 10) <= n) {
    for(int count = 0; count < 10; ++count) {
      std::cout << digits();
    }
    std::cout << "\t:" << i << '\n';
  }
  
  i -= 10;
  if(n > i) {
    for(int count = 0; count < n - i; ++count) {
      std::cout << digits();
    }
    i += 10;
    for(int count = 0; count < i - n; ++count) {
      std::cout << ' ';
    }
    std::cout << "\t:" << n << '\n';
  }
}

int main(int argc, char** argv) {
  std::cout.sync_with_stdio(false);
  unsigned int count = (argc >= 2 ? boost::lexical_cast<unsigned int>(argv[1]) : 10000);
  pi(count);
  return 0;
}
    

notes, command-line, and program output

NOTES:
64-bit Ubuntu quad core
g++ (Ubuntu 5.4.0-6ubuntu1~16.04.1) 5.4.0 20160609


Thu, 06 Oct 2016 18:40:16 GMT

MAKE:
/usr/bin/g++ -c -pipe -O3 -fomit-frame-pointer -march=native   pidigits.gpp-3.c++ -o pidigits.gpp-3.c++.o &&  \
        /usr/bin/g++ pidigits.gpp-3.c++.o -o pidigits.gpp-3.gpp_run -lgmp -lgmpxx 
rm pidigits.gpp-3.c++
1.80s to complete and log all make actions

COMMAND LINE:
./pidigits.gpp-3.gpp_run 2000

TIMED OUT after 300s


PROGRAM OUTPUT: