http://www.perlmonks.org?node_id=1189584

in reply to Re^7: solve cubic equations (Java)
in thread solve cubic equations

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);
}
[download]```
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%        --
[download]```
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.
```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**17-1) {
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) },
});
[download]```