Well, I hate to post a complete solution to one of their problems, so I've changed it around. The question is, given the first 10 outputs of this pseudo-random number generator:
for (1..10) {
$s = ($s*0x5deece66d + 0xb) % 2**48;
say(($s>>17)%1000);
}
Find the initial value of the seed $s, which is a randomly-chosen number less than 2**17. Here are the comparisons of a brute-force search using several different modules:
s/iter BigInt BigIntGMP GMP Perl
BigInt 25.0 -- -42% -94% -100%
BigIntGMP 14.4 73% -- -90% -99%
GMP 1.47 1605% 885% -- -93%
Perl 0.110 22701% 13070% 1238% --
I'm running perl 5.24.1 on an aging MacBook. I could make the Perl faster, but it would require a 64-bit perl build. You could probably get good performance with Math::Int64, but I'll leave that as an exercise for the reader. Python is running in time comparable to the pure-Perl, and PyPy smokes them all at under a millisecond. Full code is below. You don't need to tell me that my benchmarking methodology is bad.
| [reply] [Watch: Dir/Any] [d/l] [select] |