Last active
December 16, 2017 20:34
-
-
Save oupo/dc2b8c1281d20b9c359a75278eb4aa8e to your computer and use it in GitHub Desktop.
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 <cstdio> | |
#include <cstdint> | |
#include <cmath> | |
#include <algorithm> | |
#include <chrono> | |
#include <random> | |
typedef int64_t s64; | |
typedef uint64_t u64; | |
typedef __int128 s128; | |
const u64 A = 0x5d588b656c078965ll; | |
const u64 B = 0x269ec3ll; | |
const s128 M = (s128)1 << 64; | |
const int BITS = 64; | |
const int P = 11; | |
class LCGOperator { | |
public: | |
u64 a, b; | |
LCGOperator(u64 aa, u64 bb) : a(aa), b(bb) {} | |
LCGOperator o(LCGOperator y) { | |
LCGOperator x = *this; | |
LCGOperator res(x.a * y.a, x.a * y.b + x.b); | |
return res; | |
} | |
LCGOperator pow(u64 n) { | |
LCGOperator x = *this; | |
if (n == 0) { | |
return LCGOperator(1, 0); | |
} else if (n % 2 == 1) { | |
return x.o(x).pow(n / 2).o(x); | |
} else { | |
return x.o(x).pow(n / 2); | |
} | |
} | |
u64 apply(u64 s) { | |
return a * s + b; | |
} | |
}; | |
void search(u64 s0, u64 sy, u64 sz, u64 s1, u64 s2, u64 s3) { | |
LCGOperator op0(A, B); | |
LCGOperator opy = op0.pow(106); | |
LCGOperator opz = op0.pow(198); | |
const u64 xstep = 0xb1003bd; | |
const u64 ystep = (xstep * opy.a) % M; | |
const u64 zstep = (xstep * opz.a) % M; | |
const s128 xstart = (s128)s0 << (BITS - P); | |
const s128 xend = (s128)(s0 + 1) << (BITS - P); | |
const s128 ystart = (s128)sy << (BITS - P); | |
const s128 yend = (s128)(sy + 1) << (BITS - P); | |
const s128 zstart = (s128)sz << (BITS - P); | |
const s128 zend = (s128)(sz + 1) << (BITS - P); | |
u64 found_count = 0; | |
for (u64 i = 0; i < xstep; i ++) { | |
s128 x = xstart + i; | |
s128 y = opy.apply(x); | |
s128 z = opz.apply(x); | |
while (x < xend) { | |
while (ystart <= y && y < yend && zstart <= z && z < zend && x < xend) { | |
if ((y % M) >> (BITS - P) == sy && (z % M) >> (BITS - P) == sz && | |
op0.apply(x) >> (BITS - P) == s1 && op0.pow(2).apply(x) >> (BITS - P) == s2 && op0.pow(3).apply(x) >> (BITS - P) == s3) { | |
printf("found %016lx\n", (u64)x); | |
found_count ++; | |
} | |
x += xstep; | |
y = (y + ystep) % M; | |
z = (z + zstep) % M; | |
} | |
s128 ynext = std::max((y >= yend ? M : 0) + ystart - y, (s128)0); | |
s128 sy = ynext / ystep + (ynext % ystep ? 1 : 0); | |
s128 znext = std::max((z >= zend ? M : 0) + zstart - z, (s128)0); | |
s128 sz = znext / zstep + (znext % zstep ? 1 : 0); | |
//printf("sy = %016lx, sz = %016lx\n", (u64)sy, (u64)sz); | |
s128 s = std::max(sy, sz); | |
x += xstep * s; | |
y = (y + ystep * s) % M; | |
z = (z + zstep * s) % M; | |
} | |
} | |
printf("found_count=%ld\n", found_count); | |
} | |
int main() { | |
std::mt19937 rnd; | |
for (int i = 0; i < 10; i ++) { | |
u64 seed = (u64)rnd() << 32 | rnd(); | |
printf("seed=%016lx\n", seed); | |
LCGOperator op0(A, B); | |
LCGOperator opy = op0.pow(106); | |
LCGOperator opz = op0.pow(198); | |
u64 s0 = seed >> (BITS - P); | |
u64 s1 = op0.apply(seed) >> (BITS - P); | |
u64 s2 = op0.pow(2).apply(seed) >> (BITS - P); | |
u64 s3 = op0.pow(3).apply(seed) >> (BITS - P); | |
u64 sy = opy.apply(seed) >> (BITS - P); | |
u64 sz = opz.apply(seed) >> (BITS - P); | |
auto start = std::chrono::system_clock::now(); | |
search(s0, sy, sz, s1, s2, s3); | |
auto end = std::chrono::system_clock::now(); | |
printf("time=%ld\n", std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count()); | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment