### PRNG/TRNG Cesaro's theorem

by CDCozy (Novice)
 on Oct 08, 2017 at 00:29 UTC 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.

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?