[Shootout-list] C++ pidigits

[Falk Hueffner]

--=-=-=

Hi,

here's a C++ version of pidigits. It uses libgmp and needs to be
linked with -lgmpxx -lgmp.

-- 
	Falk


--=-=-=
Content-Type: text/x-c++src
Content-Disposition: inline; filename=pidigits.cc

#include <gmpxx.h>
#include <iostream>
#include <cstdlib>

struct State {
    State(mpz_class nq, mpz_class nr, mpz_class ns, mpz_class nt)
	: q(nq), r(nr), s(ns), t(nt) { }
    mpz_class q, r, s, t;
};

static inline mpz_class extract(const State& z, int x) {
    return (z.q * x + z.r) / (z.s * x + z.t);
}

static inline State lfts(mpz_class k) {
    return State(k, 4 * k + 2, 0, 2 * k + 1);
}

static inline State compose(const State& a, const State& b) {
    return State(a.q * b.q,
		 a.q * b.r + a.r * b.t,
		 a.s * b.q + a.t * b.s,
		 a.s * b.r + a.t * b.t);
}

int main(int argc, char *argv[]) {
    State z(1, 0, 0, 1);
    int k = 1, n = 0, m = std::atoi(argv[1]);
    while (n < m) {
	mpz_class y = extract(z, 3);
	while (y != extract(z, 4)) {
	    z = compose(z, lfts(k++));
	    y = extract(z, 3);	    
	}
	z = compose(State(10, -10 * y, 0, 1), z);
	std::cout << y;
	if ((++n % 10) == 0)
	    std::cout << "\t:" << n << std::endl;
    }
}

--=-=-=--