comment on

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]

In reply to Re^8: solve cubic equations (Java) by no_slogan
in thread solve cubic equations by no_slogan

Are you posting in the right place? Check out Where do I post X? to know for sure.
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
Want more info? How to link or How to display code and escape characters are good places to start.


Perl Monk, Perl Meditation
	PerlMonks