predict_dice.cpp

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <chrono>
#include <thread>
#include <mutex>
#include <iostream>

using namespace std;

#define A 214013
#define C 2531011

#define MOD 6

class MyRand {
public:
	int x;
	void srand(int n) {
		x = n;
	}

	int rnd(int n) {
		x = x * A + C;
		int b = ((x>>16)&32767);
		return b % n;
	}	
};

vector<int> candidates;
mutex m;

void search(int cpu, uint64_t s0, uint64_t s1,
			vector<int> sample) {
    auto start = chrono::system_clock::now();
	cout << "#" << cpu << " " << s0  << " .. " << s1 << endl;
	for (auto i = s0; i < s1; i++) {
		MyRand r;
		r.srand(i);
		bool found = true;
		for (int j = 0; j < sample.size(); j++) {
			int v = r.rnd(MOD);
			//cout << v << "  " << sample[j] << endl;
			if (v != sample[j]) {
				found = false;
				break;
			}
		}
		if (found) {
			cout << "found " << i << endl;
			lock_guard<mutex> l(m);
			candidates.push_back(i);
		}
		if (i % 0x1000000 == 0) {
			auto end = std::chrono::system_clock::now();
			auto elapsed_seconds = chrono::duration_cast<chrono::seconds>(end-start).count();
			cout << "#" << cpu << " " << elapsed_seconds << "sec " << (100.0 * (i - s0 + 1) / (s1 - s0)) << "% " << candidates.size() << endl;
		}
	}
}

const int num_samples = 20;
int main(int argc, char** argv) {
	int seed = 89756;
	if (argc == 2)
		seed = atoi(argv[1]);
	srand(seed);
	vector<int> sample;
	for (int i = 0; i < num_samples; i++) {
		sample.push_back(rand() % MOD);
		cout << " " << sample[sample.size() - 1];
	}
	cout << endl << endl;
	
    chrono::time_point<chrono::system_clock> start, end;
    start = chrono::system_clock::now();

	vector<thread> workers;
	int num_threads = 8;
	for (int cpu = 0; cpu < num_threads; cpu++) {
		workers.push_back(
			thread([=]() {
					uint64_t s0 = 0x100000000LL * cpu / num_threads;
					uint64_t s1 = 0x100000000LL * (cpu + 1) / num_threads;
					search(cpu, s0, s1, sample);
				}));
	}
	for (auto& w : workers) {
		w.join();
	}

    end = std::chrono::system_clock::now();
    int elapsed_seconds = chrono::duration_cast<chrono::seconds>
                             (end-start).count();
	cout << elapsed_seconds << "sec" << endl;
	for (auto c : candidates) {
		cout << c << " " << seed << endl;
		
		MyRand r;
		r.srand(c);
		srand(seed);

		bool diff = false;
		for (uint64_t i = 0; i < 0xffffff; i++) {
			int predict = r.rnd(MOD);
			int ref = rand() % MOD;
			if (predict != ref) {
				cout << "fail@" << i << " " << predict << "  " << ref << endl;
				diff = true;
				break;
			}
		}
		if (!diff)
			cout << "ok" << endl;
	}

	return 0;
}