PRNG/TRNG Cesaro's theorem

CDCozy has asked for the wisdom of the Perl Monks concerning the following question:

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"; }` [download] 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` [download]	[reply] [d/l] [select]
Re^2: PRNG/TRNG Cesaro's theorem by marioroy (Prior) on Oct 09, 2017 at 01:30 UTC
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"; } [download] 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 [download] 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 [download] Once the release hits CPAN, I'd come back and post a parallel demonstration. Regards, Mario	[reply] [d/l] [select]
Re^3: PRNG/TRNG Cesaro's theorem by marioroy (Prior) 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($_); } [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	[reply] [d/l] [select]
Re^4: PRNG/TRNG Cesaro's theorem by marioroy (Prior) on Oct 09, 2017 at 06:06 UTC
Re^2: PRNG/TRNG Cesaro's theorem by Anonymous Monk on Oct 08, 2017 at 13:45 UTC
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.	[reply]
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?) Start by using warning and strict Look up the perl data stucture called a 'array of arrays' (LoL) perldsc Crate your LoL `my @lori` (lori acronym for lists of random integer) 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) ]; }` [download] taken from ARRAYS OF ARRAYS Create a scalar to hold the results of your analysis(where you apply your gcd(x, y) = 1) `my $result=0;` 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++; }; }` [download] 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 }` [download] 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... wjw	[reply] [d/l] [select]
Re: PRNG/TRNG Cesaro's theorem by Anonymous Monk on Oct 08, 2017 at 01:10 UTC
Not sure if you mean Approximations of pi#Summing a circle's area or if you really want the Stolz�Ces�ro theorem. Also not sure what a TPRNG is, maybe you meant TRNG?	[reply]
Re^2: PRNG/TRNG Cesaro's theorem by Anonymous Monk on Oct 08, 2017 at 01:19 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.	[reply]
Re^3: PRNG/TRNG Cesaro's theorem by CDCozy (Novice) on Oct 08, 2017 at 01:22 UTC
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).	[reply]
Re^4: PRNG/TRNG Cesaro's theorem by Anonymous Monk on Oct 08, 2017 at 01:42 UTC
Re^2: PRNG/TRNG Cesaro's theorem by CDCozy (Novice) on Oct 08, 2017 at 01:19 UTC
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.	[reply]
Re^3: PRNG/TRNG Cesaro's theorem by AnomalousMonk (Archbishop) on Oct 08, 2017 at 03:25 UTC
... 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: `<%-{-{-{-<`	[reply] [d/l]
Re^3: PRNG/TRNG Cesaro's theorem by Anonymous Monk on Oct 08, 2017 at 01:24 UTC
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.	[reply]
Re^4: PRNG/TRNG Cesaro's theorem by marioroy (Prior) on Oct 09, 2017 at 06:35 UTC
Re^5: PRNG/TRNG Cesaro's theorem by Anonymous Monk on Oct 09, 2017 at 13:02 UTC
Some notes below your chosen depth have not been shown here
Re^4: PRNG/TRNG Cesaro's theorem by CDCozy (Novice) on Oct 08, 2017 at 01:31 UTC
Re^3: PRNG/TRNG Cesaro's theorem by RonW (Parson) on Oct 09, 2017 at 22:50 UTC
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(); ... }` [download]	[reply] [d/l]
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.	[reply]


Keep It Simple, Stupid
	PerlMonks