Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I recently saw this question over at math.SE. It got me thinking. Could Pi be used as a crude random number generator? I mean the results are well known(how long has pi been computed to now?) but, Pi does seem to be quite random when taken 1 digit at a time.

Does this make any sense at all?

share|improve this question
    
Where are these random numbers going to be used? –  NullUserException Oct 19 '12 at 16:58
2  
Theoretically it could be but it would probably be less optimal than the current methods. Just instincts on that but it seems the random pool is bigger in this way with less overhead. –  Rig Oct 19 '12 at 16:58
    
@NullUserException Not sure... I was just wondering if they could be used AT ALL. I assume this would definitely not be for cryptography though' –  Earlz Oct 19 '12 at 16:59
3  
@FrustratedWithFormsDesigner - its part of the ent package. It uses the random numbers to calculate the area of a circle inscribed within a square and from that, one can calculate pi. Using the bits of pi as the random numbers, there is a certain elegance to use that data to compute pi. –  MichaelT Oct 19 '12 at 18:30
1  
@FrustratedWithFormsDesigner ent is a suite of code for analyzing the pseudo randomness of bunch of bytes. One test within it is a Monte Carlo for calculating pi and comparing the random calculation against the actual value to see how random it is. –  MichaelT Oct 19 '12 at 19:31

4 Answers 4

up vote 43 down vote accepted
+150

Digging from http://www.befria.nu/elias/pi/binpi.html to get the binary value of pi (so that it was easier to convert into bytes rather than trying to use decimal digits) and then running it through ent I get the following for an analysis of the random distribution of the bytes:

Entropy = 7.954093 bits per byte.

Optimum compression would reduce the size of this 4096 byte file by 0 percent.

Chi square distribution for 4096 samples is 253.00, and randomly would exceed this value 52.36 percent of the times.

Arithmetic mean value of data bytes is 126.6736 (127.5 = random).

Monte Carlo value for Pi is 3.120234604 (error 0.68 percent).

Serial correlation coefficient is 0.028195 (totally uncorrelated = 0.0).

So yes, using pi for random data would give you fairly random data... realizing that it is well known random data.


From a comment above...

Depending on what you are doing, but I think you can use the decimals of the square root of any prime number as a random number generator. These should at least have evenly distributed digits. – Paxinum

So, I computed the square root of 2 in binary to undetake the same set of problems. Using Wolfram's Iteration I wrote a simple perl script

#!/usr/bin/perl
use strict;
use Math::BigInt;

my $u = Math::BigInt->new("2");
my $v = Math::BigInt->new("0");
my $i = 0;

while(1) {
    my $unew;
    my $vnew;

    if($u->bcmp($v) != 1) { # $u <= $v
        $unew = $u->bmul(4);
        $vnew = $v->bmul(2);
    } else {
        $unew = ($u->bsub($v)->bsub(1))->bmul(4);
        $vnew = ($v->badd(2))->bmul(2);
    }   

    $v = $vnew;
    $u = $unew;

    #print $i,"  ",$v,"\n";
    if($i++ > 10000) { last; }
}

open (BITS,"> bits.txt");
print BITS $v->as_bin();
close(BITS);

Running this for the first 10 matched A095804 so I was confident I had the sequence. The value vn as when written in binary with the binary point placed after the first digit gives an approximation of the square root of 2.

Using ent against this binary data produces:

Entropy = 7.840501 bits per byte.

Optimum compression would reduce the size
of this 1251 byte file by 1 percent.

Chi square distribution for 1251 samples is 277.84, and randomly
would exceed this value 15.58 percent of the times.

Arithmetic mean value of data bytes is 130.0616 (127.5 = random).
Monte Carlo value for Pi is 3.153846154 (error 0.39 percent).
Serial correlation coefficient is -0.045767 (totally uncorrelated = 0.0).
share|improve this answer
    
Exactly the type of answer I was looking for. I have no idea how to calculate all of this type of stuff –  Earlz Oct 19 '12 at 18:14
    
Even if the number distribution is fairly random, don't you have to find a way to randomly select a portion of it? –  Blumer Oct 19 '12 at 22:56
1  
@Blumer no. Randomness is measured on a sequence of numbers. The sequence of pi digits is said to be random. See en.wikipedia.org/wiki/Statistical_randomness –  Simon Oct 20 '12 at 10:28
9  
Absolutely right. And because it is well known random data, don't you ever dare to use that for cryptographic purposes. –  Falcon Jan 1 '13 at 11:18
3  
+1 for "well known random data". If you need random data that someone can't guess, pi is not for you, if just need a bunch of random numebers for some reason, it works just fine. –  jmoreno Mar 21 at 2:34

Such generator would be a pseudo number generator, i.e. given the same seed, the result would always be the same. This being said, in most frameworks, when you use the standard random number generator, there is the same issue of being pseudo-random.

The distribution of the digits seems to be quite similar to the standard random number generators¹, so the digits of π can be used for ordinary random number generation scenarios.

The issue is that the algorithm will probably be very slow, compared to the ordinary random number generators, so it's not very useful in practice.


¹ I believe it's true, but don't have any proof. It would be interesting (and not to complicate) to do a comparison based on a large quantity of numbers.

share|improve this answer
4  
@NullUserException: No, some random number generators use a source of entropy. This can be done either via specialized hardware (the approach taken by random.org) or by using existing sources of entropy (measurable fluctuations within existing hardware sensors, certain types of user interactions, micro-variations in certain types of performance tests, etc.). –  Brian Oct 19 '12 at 17:41
1  
@NullUserException: there are cryptographically secure PRNG, which are still pseudo-random. Then there are real RNG which are based on input from the real world: radioactive decay, noise, etc. –  MainMa Oct 19 '12 at 17:42
2  
@MainMa But even then, the randomness of radioactive decay, atmospheric noise, derived from user input, etc. is debatable. Just because we don't recognize a pattern doesn't mean one doesn't exist. –  NullUserException Oct 19 '12 at 18:44
1  
@NullUserException: Last year Colbeck/Renner published a paper which purports to prove: "No extension of quantum theory can have improved predictive power." Assuming this holds up, there may be a source of entropy which is truly unpredictable, rather than merely infeasible to predict. –  Brian Oct 19 '12 at 19:07
1  
@MainMa - you would still perform mathematical tests for randomness. Even though the underlying physics is random (to the best of our knowledge) it doesn't mean that measurement is. Detectors of all types have a lot of 'interesting' behaviour in the real world –  Martin Beckett Oct 21 '12 at 17:03

Well, among other properties of a random number generator, you probably want it to be a normal number. And several answers in the math.SE question that inspired your question point out that currently pi is believed to be normal, but it has not been proven.

share|improve this answer

The randomness of digits of pi (or for that matter any other sequence) can be arguably tested by so-called 'battery tests'. One popular battery test is George Marsaglia's Diehard Battery Test. There is also NIST Special publication 800-22 that describes a number of such tests and the results of applying these tests to a number of physical constants, including - lo and behold - pi for over a million bits. The result of pi is given in Appendix B of the report and looks like this:

Statistical Test                            P-value
Frequency                                   0.578211
Block Frequency (m = 128)                   0.380615
Cusum-Forward                               0.628308
Cusum-Reverse                               0.663369
Runs                                        0.419268
Long Runs of Ones                           0.024390
Rank                                        0.083553
Spectral DFT                                0.010186
Non-overlapping Templates (m = 9, B = 000000001)          0.165757
Overlapping Templates (m = 9)               0.296897
Universal                                   0.669012
Approximate Entropy (m = 10)                0.361595
Random Excursions (x = +1)                  0.844143
Random Excursions Variant (x = -1)          0.760966
Linear Complexity (M = 500)                 0.255475
Serial (m = 16, 2m∇Ψ )                      0.143005

Is pi a good random sequence generator? Look at the above results (or search the meanings of the left column variable, if you have no idea what they mean), and check if it satisfies your need.

share|improve this answer
1  
The read me for Diehard says that it needs about 10-12 megabytes of binary data (the best I could find is 32 kilobytes). If you ran it against the ascii data, the test would be quite a ways off from what the application is expecting. –  MichaelT Mar 21 at 2:53
    
My answer was for the OP question and the original question on Math.SE - neither of which mentioned anything about ascii versus binary data or the length of the sample. Without a large enough sample set, how can the statistical randomness of any sequence be determined? –  sm535 Mar 21 at 12:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.