Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses
 
PerlMonks  

Re^2: PRNG/TRNG Cesaro's theorem

by marioroy (Vicar)
on Oct 09, 2017 at 01:30 UTC ( #1200960=note: print w/replies, xml ) Need Help??


in reply to Re: PRNG/TRNG Cesaro's theorem
in thread PRNG/TRNG Cesaro's theorem

Hello brothers and sisters of the Monastery,

Seeing danaj's post made me think of passing arguments to workers for a parallel demonstration. But first, I need to check if random numbers are unique between workers. They are not for non-threaded workers, irand64 and random_bytes.

Here is the test code. Calling MCE::relay is a way to have workers display output orderly, starting with worker 1, 2, ..., 8. The init_relay value isn't used here, but the option tells MCE to load MCE::Relay and enable relay capability. Workers persist between each run.

use strict; use warnings; use ntheory ":all"; use MCE::Flow; my ( $name, $rng ); my %rand = ( "drand48" => sub { int(rand(1 << 32)) }, "ChaCha20" => sub { irand64() }, "/dev/urandom" => sub { unpack("Q", random_bytes(8)) } ); MCE::Flow::init( max_workers => 8, init_relay => 0, user_begin => sub { $name = MCE->user_args()->[0]; $rng = $rand{ $name }; } ); sub func { MCE::relay { print MCE->wid(), ": ", $rng->(), "\n"; }; } for my $name ( "drand48", "ChaCha20", "/dev/urandom" ) { print "Usage $name:\n"; mce_flow { user_args => [$name] }, \&func; print "\n"; }

Output.

Usage drand48: 1: 3498494761 2: 2506930441 3: 1515366121 4: 523801801 5: 3827204777 6: 2835640457 7: 1844076137 8: 852511817 Usage ChaCha20: 1: 4471005142860083063 2: 4471005142860083063 3: 4471005142860083063 4: 4471005142860083063 5: 4471005142860083063 6: 4471005142860083063 7: 4471005142860083063 8: 4471005142860083063 Usage /dev/urandom: 1: 15746895497052787399 2: 15746895497052787399 3: 15746895497052787399 4: 15746895497052787399 5: 15746895497052787399 6: 15746895497052787399 7: 15746895497052787399 8: 15746895497052787399

Later today will release MCE 1.831 and MCE::Shared 1.832 containing the fix.

Usage drand48: 1: 600074529 2: 3903477505 3: 2911913185 4: 1920348865 5: 928784545 6: 4232187521 7: 3240623201 8: 2249058881 Usage ChaCha20: 1: 8740887910466299010 2: 12948789762855324085 3: 7574729187958724006 4: 14608687740989597345 5: 10145950054018120246 6: 11767641523694169551 7: 5811941457879652367 8: 2397613489984096139 Usage /dev/urandom: 1: 14391656456731294109 2: 2750708286643159769 3: 10844675827853246458 4: 7920672879166021322 5: 16939013845838223421 6: 9482848646152826462 7: 11535629003375292447 8: 6903845178044907896

Once the release hits CPAN, I'd come back and post a parallel demonstration.

Regards, Mario

Replies are listed 'Best First'.
Re^3: PRNG/TRNG Cesaro's theorem
by marioroy (Vicar) on Oct 09, 2017 at 03:59 UTC

    MCE 1.831 and MCE::Shared 1.832 have been released containing the fix. What follows is the parallel demonstration for danaj's example. For sequence of numbers, the MCE bounds_only option is handy. Workers receive the begin and end values only.

    use strict; use warnings; use ntheory 0.67 ":all"; use MCE::Flow 1.831; my ( $name, $rng ); my %rand = ( "drand48" => sub { int(rand(1 << 32)) }, "ChaCha20" => sub { irand64() }, "/dev/urandom" => sub { unpack("Q", random_bytes(8)) } ); # Workers receive [ begin, end ] values. MCE::Flow::init( max_workers => MCE::Util::get_ncpu(), chunk_size => 10000, bounds_only => 1, user_begin => sub { $name = MCE->user_args()->[0]; $rng = $rand{ $name }; } ); sub func { my ( $beg_seq, $end_seq ) = @{ $_ }; my ( $t ) = ( 0 ); for ( $beg_seq .. $end_seq ) { $t++ if gcd( $rng->(), $rng->() ) == 1; } MCE->gather($t); } # The user_args option is how to pass arguments. # Workers persist between each run. sub cesaro { my ( $name ) = @_; print "Usage $name:\n"; for my $e ( 1..7 ) { my $n = 10 ** $e; my @ret = mce_flow_s { user_args => [$name] }, \&func, 0, $n - 1; my $t = 0; $t += $_ for @ret; printf "%8d %0.8f\n", $n, sqrt(6 * $n / $t); } printf "%9s %s\n\n", "Pi", Pi(); } for ( "drand48", "ChaCha20", "/dev/urandom" ) { cesaro($_); }

    Output.

    Usage drand48: 10 3.46410162 100 3.11085508 1000 3.12347524 10000 3.15335577 100000 3.14122349 1000000 3.14092649 10000000 3.14209456 Pi 3.14159265358979 Usage ChaCha20: 10 3.46410162 100 3.08606700 1000 3.11588476 10000 3.14606477 100000 3.14461263 1000000 3.14453748 10000000 3.14269499 Pi 3.14159265358979 Usage /dev/urandom: 10 3.16227766 100 3.13625024 1000 3.24727816 10000 3.13959750 100000 3.14238646 1000000 3.14247180 10000000 3.14023908 Pi 3.14159265358979

    The parallel code scales linearly. It runs about 4x faster on a machine with 4 "real" cores. A little faster with extra hyper-threads.

    Regards, Mario

      The OP mentioned (here) on marking down the number pairs whenever gcd(x, y) is equal to 1.

      Here, workers write the number pairs to a shared STDERR file handle. Locking is handled automatically by the shared-manager. For best performance, do not have workers write each pair individually to the shared file handle. Instead, have workers append to a local variable. Writing once per chunk/segment relieves pressure on the shared-manager process, which must keep up with many workers.

      To run, redirect STDERR to a file: perl demo.pl 2> pairs.txt

      use strict; use warnings; use ntheory 0.67 ":all"; use MCE::Flow 1.831; use MCE::Shared; mce_open my $err_fh, '>>', \*STDERR; my ( $name, $rng ); my %rand = ( "drand48" => sub { int(rand(1 << 32)) }, "ChaCha20" => sub { irand64() }, "/dev/urandom" => sub { unpack("Q", random_bytes(8)) } ); # Workers receive [ begin, end ] values. MCE::Flow::init( max_workers => MCE::Util::get_ncpu(), chunk_size => 10000, bounds_only => 1, user_begin => sub { $name = MCE->user_args()->[0]; $rng = $rand{ $name }; } ); sub func { my ( $beg_seq, $end_seq ) = @{ $_ }; my ( $t, $pairs, $r1, $r2 ) = ( 0, '' ); for ( $beg_seq .. $end_seq ) { ( $r1, $r2 ) = ( $rng->(), $rng->() ); if ( gcd($r1, $r2) == 1 ) { $pairs .= sprintf("%20s %20s\n", $r1, $r2); $t++; } } print $err_fh $pairs; MCE->gather($t); } # The user_args option is how to pass arguments. sub cesaro { my ( $name ) = @_; print "Usage $name:\n"; my $n = 10 ** 5; my @ret = mce_flow_s { user_args => [$name] }, \&func, 0, $n - 1; my $t = 0; $t += $_ for @ret; printf "%8d %0.8f\n", $n, sqrt(6 * $n / $t); printf "%9s %s\n\n", "Pi", Pi(); } cesaro("/dev/urandom");

      stdout

      Usage /dev/urandom: 100000 3.14168852 Pi 3.14159265358979

      stderr

      3287478503828099458 17020534165422626509 12874128583739175743 15858105624010204897 12114767169191945777 1381808520787800067 6217235583185614040 13880267056100467759 6095107227201871385 14484880859615821612 6023474899938562107 6188664627301334099 2843055836738994412 3086747352859159329 10461621510749606095 302140866635797242 11160050491040241465 8409335412227119072 3718439936437935345 5121716120103428116 ...

      Regards, Mario

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1200960]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (6)
As of 2019-12-09 11:02 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?