Re^3: PRNG/TRNG Cesaro's theorem

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($_);
}
[download]

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
[download]

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

Comment on Re^3: PRNG/TRNG Cesaro's theorem Select or Download Code

Replies are listed 'Best First'.

Re^4: PRNG/TRNG Cesaro's theorem
by marioroy (Prior) on Oct 09, 2017 at 06:06 UTC

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");
[download]

stdout

Usage /dev/urandom:
  100000  3.14168852
       Pi 3.14159265358979
[download]

stderr

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

...
[download]

Regards, Mario

[reply]
[d/l]
[select]


Clear questions and runnable code get the best and fastest answer
	PerlMonks