 "be consistent" PerlMonks

Re^8: solve cubic equations (Java)

by no_slogan (Deacon)
 on May 05, 2017 at 16:03 UTC ( #1189584=note: print w/replies, xml ) Need Help??

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); }
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) }, });

Create A New User
Node Status?
node history
Node Type: note [id://1189584]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (4)
As of 2019-10-19 05:35 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
In 2019 the site I miss most is:

Results (45 votes). Check out past polls.

Notices?