#include <chrono>
#include <iostream>
#include <vector>

// Calcule 1500 digits de PI avec l'algorithme "spigot".
// Le benchmark valide le calcul avec un checksum pour ne pas mesurer
// l'assemblage d'une grande chaine de caracteres.

int main() {
	const auto begin = std::chrono::steady_clock::now();

	const int decimalCount = 1500;

	// On calcule 1 chiffre entier + les decimales demandees.
	// On ajoute une iteration de marge car l'algorithme emet les chiffres avec retard.
	const int iterations = decimalCount + 2;
	const int boxes = iterations * 10 / 3;

	std::vector<int> remainders(static_cast<std::size_t>(boxes + 1), 2);
	std::vector<int> digitsOut(static_cast<std::size_t>(iterations + 2), 0);

	int outCount = 0;
	int predigit = 0;
	int heldNines = 0;

	for (int digitIndex = 0; digitIndex < iterations; ++digitIndex) {
		int q = 0;

		for (int i = boxes; i > 0; --i) {
			const int x = 10 * remainders[static_cast<std::size_t>(i)] + q * i;
			const int denominator = 2 * i - 1;

			remainders[static_cast<std::size_t>(i)] = x % denominator;
			q = x / denominator;
		}

		remainders[1] = q % 10;
		q /= 10;

		if (q == 9) {
			++heldNines;
		} else if (q == 10) {
			digitsOut[static_cast<std::size_t>(outCount++)] = predigit + 1;

			while (heldNines > 0) {
				digitsOut[static_cast<std::size_t>(outCount++)] = 0;
				--heldNines;
			}

			predigit = 0;
		} else {
			digitsOut[static_cast<std::size_t>(outCount++)] = predigit;
			predigit = q;

			while (heldNines > 0) {
				digitsOut[static_cast<std::size_t>(outCount++)] = 9;
				--heldNines;
			}
		}
	}

	digitsOut[static_cast<std::size_t>(outCount++)] = predigit;

	// Le premier chiffre produit est un zero technique.
	long long checksum = 0;
	for (int i = 1; i < decimalCount + 2; ++i) {
		checksum += digitsOut[static_cast<std::size_t>(i)];
	}

	std::cout << (decimalCount + 1) << " digits\n";
	std::cout << "checksum = " << checksum << "\n";

	const auto end = std::chrono::steady_clock::now();
	const auto durationMs = std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count();
	std::cout << "Duration = " << durationMs << " ms\n";

	return 0;
}
