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 pseudorandom 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 randomlychosen number less than 2**17. Here are the comparisons of a bruteforce 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 64bit 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 purePerl, 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.
use strict;
use warnings;
use Benchmark qw( cmpthese );
use Math::GMP ();
use Math::BigInt ();
use Math::BigInt::GMP ();
sub tryclass {
my ($class, $nums) = @_;
my $a = $class>new('0x5deece66d');
my $b = $class>new('0xb');
my $m = ($class>new(1)<<48)1;
SEED: for my $seed (0 .. (1<<17)1) {
my $s = $class>new($seed);
for my $i (0 .. $#$nums) {
$s = ($s * $a + $b) & $m;
next SEED unless ($s >> 17) % 1000 == $nums>[$i];
}
print "$class $seed\n";
}
}
sub tryperl {
my ($nums) = @_;
SEED: for my $seed (0 .. 2**171) {
my $lo = $seed;
my $hi = 0;
for my $i (0 .. $#$nums) {
$hi = $hi * 0xe66d + $lo * 0x2ef76
+ ($hi * 0x2ef76 % 2**14)*2**17;
$lo = ($lo * 0xe66d + 0xb);
$hi = ($hi + int($lo/2**17)) % 2**31;
$lo %= 2**17;
next SEED unless $hi % 1000 == $nums>[$i];
}
print "Perl $seed\n";
}
}
my @nums;
{
my $a = Math::GMP>new('0x5deece66d');
my $b = Math::GMP>new('0xb');
my $m = (Math::GMP>new(1)<<48)1;
my $s = Math::GMP>new(int rand 2**17);
print "Seed $s\n";
for my $i (1..10) {
$s = ($s * $a + $b) & $m;
push @nums, (($s>>17) % 1000) . '';
}
print "Nums @nums\n";
}
cmpthese(0, {
GMP => sub { tryclass('Math::GMP', \@nums) },
BigInt => sub { tryclass('Math::BigInt', \@nums) },
BigIntGMP => sub { Math::BigInt>import(lib=>'GMP');
tryclass('Math::BigInt', \@nums) },
Perl => sub { tryperl(\@nums) },
});
Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
Read Where should I post X? if you're not absolutely sure you're posting in the right place.
Please read these before you post! —
Posts may use any of the Perl Monks Approved HTML tags:
 a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

For: 

Use: 
 &   & 
 <   < 
 >   > 
 [   [ 
 ]   ] 
Link using PerlMonks shortcuts! What shortcuts can I use for linking?
See Writeup Formatting Tips and other pages linked from there for more info.

