Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??
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.
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) }, });

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

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • 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:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others meditating upon the Monastery: (5)
    As of 2019-07-21 02:35 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?
      If you were the first to set foot on the Moon, what would be your epigram?






      Results (7 votes). Check out past polls.

      Notices?