Created
July 31, 2015 16:12
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment