Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling
 
PerlMonks  

PRNG/TRNG Cesaro's theorem

by CDCozy (Novice)
on Oct 08, 2017 at 00:29 UTC ( #1200924=perlquestion: print w/replies, xml ) Need Help??
CDCozy has asked for the wisdom of the Perl Monks concerning the following question:

Alright so I have a project where I have to have two prngs and one TPRNG and generate 1000 numbers and estimate pie using Cesaro's theorem. I have created a prng that generates a list of numbers , but I need them as a list paired in two's to accomplish this. I am very new and inexperienced. I am currently taking a programming class, but the project is for intro to cryptography.

I am pretty stuck on how to write this program, and have looked through the internet for the information I seek but could not find it. So Now I am asking here in hopes I can get put in the right direction to write this program. Is there any Perl mods that would be useful/helpful? I have about 3 days to get this done. Any help would be appreciated! I have to have two PRNG's and one TPRNG with random.org being at least 1000 numbers

Replies are listed 'Best First'.
Re: PRNG/TRNG Cesaro's theorem
by danaj (Friar) on Oct 08, 2017 at 08:13 UTC

    Of course you will want to do it differently, but here is something I wrote to play with this. I used the ntheory module because it has different RNGs as well as gcd and Pi.

    #!/usr/bin/env perl use warnings; use strict; use ntheory ":all"; cesaro("drand48", sub { int(rand(1<<32)) } ); cesaro("ChaCha20", sub { irand64 } ); cesaro("/dev/urandom", sub { unpack("Q",random_bytes(8)) } ); sub cesaro { my($name, $rng) = @_; print "Using $name:\n"; for my $e (1..7) { my $n = 10**$e; my $t = 0; for (1..$n) { $t++ if gcd( $rng->(), $rng->() ) == 1; } printf "%8d %10.8f\n", $n, sqrt(6*$n/$t); } print " Pi ", Pi(), "\n\n"; }

    I saved cut-n-paste by passing in the RNG code. One for Perl's default rand (which is drand48 on modern Perl), one for ntheory's CSPRNG, and one that gets data from /dev/urandom. You could replace that with something that got data from random.org. There are even a couple modules that do it automatically (Math::RandomOrg and Data::Entropy). Since we expect t/n ~ 6/Pi^2, a little algebra gives us Pi ~ sqrt(6n/t). I don't believe we can read anything into what the results might mean for the different RNG methods. The results will be different every time unless we seed (and the last can't be seeded since it is O/S collected entropy (long technical discussion of /dev/random vs. /dev/urandom vs. hardware could be had here)).

    Using drand48: 10 2.73861279 100 3.06186218 1000 3.15964572 10000 3.14632429 100000 3.13988122 1000000 3.14035598 10000000 3.14143144 Pi 3.14159265358979 Using ChaCha20: 10 3.16227766 100 3.18896402 1000 3.17287158 10000 3.15675816 100000 3.14329189 1000000 3.13978836 10000000 3.14138726 Pi 3.14159265358979 Using /dev/urandom: 10 3.46410162 100 3.03821810 1000 3.11588476 10000 3.14217962 100000 3.13643021 1000000 3.14020372 10000000 3.14130744 Pi 3.14159265358979

      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

        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

      Notice that the number of correct digits of π is roughly half of the number of digits in $n, because this is basically a random walk process.
Re: PRNG/TRNG Cesaro's theorem
by wjw (Priest) on Oct 08, 2017 at 04:45 UTC
    I would approach the problem of programming this as follows: (I understand you have your random number generator already written from previous posting?)
    1. Start by using warning and strict
    2. Look up the perl data stucture called a 'array of arrays' (LoL) perldsc
    3. Crate your LoL  my @lori (lori acronym for lists of random integer)
    4. Populate the array items in each array in the LoL using your random integer generator

      (probably use something like

      for $i ( 1 .. 1000) { $AoA[$i] = [ somefunc($i) ]; }
      taken from ARRAYS OF ARRAYS

    5. Create a scalar to hold the results of your analysis(where you apply your gcd(x, y) = 1) my $result=0;
    6. Examine each pair of random integers in the LoL for meeting the gcd(x, y) = 1 criteria and increment $result when true
      foreach my @pair (@lori) { if( my_gcd_func(@pair) = 2) { $result++; }; }
    7. Check that value in $result against the 6/(Pi^2) .
      if( $result = 6/(3.1415926 * 3.141596) ) { do whatever you need to do to meet assignment requirements }

    The code shown here is not tested, and there are parts which are obviously missing, but those will become obvious as you work your way through the above sequence I think. Perldocs are your friend in this endeavor I think. The basic foreach loop and if statement covered in perldoc along with the other noted perl docs above should give you a place to start.

    It seems to me that your main issue is that you're new to programming and sitting fine in your understanding of the theory. I have zero understanding of the theory which is probably reflected in the way I approached it above, but that is not really important to you right now. So I hope that the basic breakdown above gets you started in the direction that you want to go on the programming end. Best of luck to you on that assignment.

    ...the majority is always wrong, and always the last to know about it...

    A solution is nothing more than a clearly stated problem...

Re: PRNG/TRNG Cesaro's theorem
by Anonymous Monk on Oct 08, 2017 at 01:10 UTC
      There's also this Cesaro's theorem: mathworld.wolfram.com/CesarosTheorem.html
      But I'm going to need a picture before I can figure out what that page is even talking about.
        to make sure the instructions in my project has this. Cesaro's theorem states that given two random integers, x and y, the probability that gcd(x, y) = 1 is 6/(Pi^2).
      Yes I meant TRNG, sorry was typing fast. and yes It is Stolz-Cesaro theorem. I understand the theorem but I have to write two differnt prng's that have pairs of at least 1000 numbers and estimate pie through the theorem. I dont know how to write it so it generates the numbers in pairs however... I also have to use random.org for the TRNG.
        ... not sure what a TPRNG is ... I meant TRNG ...

        You can correct your OP. Please see How do I change/delete my post? for site etiquette and protocol regarding changing a post.


        Give a man a fish:  <%-{-{-{-<

        Well, the Stolz-Cesaro theorem is about convergence of series. There are a lot of series that converge to pi, did you have a specific one in mind? And I don't see where random numbers come into the picture at all.
        I dont know how to write it so it generates the numbers in pairs however.

        In your loop, call the RNG twice:

        for (1 .. 500) { my $x = rng(); my $y = rng(); ... }
Re: PRNG/TRNG Cesaro's theorem
by Anonymous Monk on Oct 08, 2017 at 02:08 UTC
    Summary so far: The probability that two uniformly-distributed randomly chosen integers between 1 and n are relatively prime approaches 6/π² for large n. This was established by Ernesto Cesaro in 1885, but nobody seems to refer to it by the name "Cesaro's theorem."

    For anyone who's interested, there's a nice explanation here: aperiodical.com/2013/06/cushing-your-luck-properties-of-randomly-chosen-numbers/

    I'm out for now, peace.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://1200924]
Approved by haukex
Front-paged by haukex
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (8)
As of 2017-12-14 15:34 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    What programming language do you hate the most?




















    Results (396 votes). Check out past polls.

    Notices?