Random number generator

[Thisisnotanid]

Hi all, I was experimenting with techniques of generating random numbers and eventually decided on the following. I realize there's a big discussion in computing circles about "randomness" and as such am not trying to make any claims here. What do you think? Thoughts, comments, suggestions, discussion of underlying theories, and even your own version of random generators are welcome! Here's the code:

def primes(n):

    s = range(3, n+1, 2) 

    i = 1 

    a = len(s) - 1

    for l in xrange(0, a + 1): 
	    a1 = i
	    j = (l + (s[l]*i))
	    while (j <= a) and s[l] != 0: 
		    s[j] = 0
    		    i += 1 
		    j = (l + (s[l]*i)) 
	    i = a1 + 1

    s = list(set(s))
    s.sort()
    if 0 in s:
        s.remove(0)
    s = [2] + s
    return s


import time as t

a = t.time() - int(t.time())

b = "%.6f" % a


b = b.split('0.')[1]

n = int(b)

s = primes(n)


l = len(b) + 1

S = 0

for k in range(1, l):

    if b[:k] not in s:

        S += int(b[:k])


print "The non-prime sum 'S' --> ",S

k = 1
l = int(b[:1])
n = int(b[0])
while S > 100:

    S = float(S/(s[l] + n*k))

    k += 1


print "S -->", S, "|", "Decimal part of S -->", S - int(S), "|", "Decimal part of time when program began -->", a

[vegaseat]

On first look you committed a major crime here, you mixed spaces and tabs for indentation. A good way to ruin any Python program.

[griswolf]

for my purposes (actually need to use some pseudo random things from time to time), I have been quite happy to simply
import random

Of course, if you want to write your own that's different.

The "bestest" random function I ever read about: Get bits from the microphone input. There may be no need to actually hook up a microphone: You are after noise, and the circuit may make enough noise on its own. However random.org does use actual input (atmospheric noise gotten by tuning radio receivers between stations). As you will find if you do some reading, this kind of TRNG (True Random Number Generator) has some good and bad features compared to a PRNG (Pseudo...).

[Thisisnotanid]

On first look you committed a major crime here, you mixed spaces and tabs for indentation. A good way to ruin any Python program.

Original Post: Whoops sorry, missed that. I'll have it fixed soon.

Turns out I can't edit it now, but thanks for pointing it out! :D

[bumsfeld]

Could you add some comments to your code and tell us what you are doing?

[Thisisnotanid]

Could you add some comments to your code and tell us what you are doing?

Sure, I'll have that up in a while. However, I can't edit my original post so I'll make a new post.

[Thisisnotanid]

Hi all, this is the code from my original posts with comments and mixed indentation fixed:

"""The following is an implementation of Euler's Sieve. I will not explain this much here, but the basic idea is to remove multiples of odd numbers in a way that the program doesn't try to remove multiples it has already and it only works its way up-to sqrt(n), here n is the input."""


def primes(n):      

    s = range(3, n+1, 2) 

    i = 1 

    a = len(s) - 1

    for l in xrange(0, a + 1): 
        a1 = i
        j = (l + (s[l]*i))
        while (j <= a) and s[l] != 0: 
            s[j] = 0
            i += 1 
            j = (l + (s[l]*i)) 
        i = a1 + 1

    s = list(set(s))
    s.sort()
    if 0 in s:
        s.remove(0)
    s = [2] + s
    return s


"""My approach for this random generator is to take the decimal part of time (only the first 6 digits as the prime lister only works sufficiently fast for n <= 1e6. For faster prime listers search the forums.) and determine if linear sequences of the numbers obtained are not prime. In an earlier approach, the program was designed to determine whether those sequences are prime; however, this didn't work very well has the probability of that happening turns out to be low (You can refer to works on number theory to verify this, the prime number theorem in particular, or you can test it yourself). By linear sequences I mean the following. Let's say I have a decimal part of time as follows: '.abcdef', I wanted to determine if 'a' is not prime, then determine if 'ab' is not prime, then if 'abc' is not prime, and so on. Then, the program sums whatever sequences are not prime. The while loop at the end just brings the number down to the range you're interested. Especially, since now you have a decimal which can range from 0 to 1, you can scale the number to whatever the situation calls for. That being said, the implementation is rather short:"""


import time as t

a = t.time() - int(t.time()) # Decimal part of time

b = "%.6f" % a # Limit to first 6 digits.


b = b.split('0.')[1] # This and the following line get the time in the form we are     interested in.

n = int(b)

s = primes(n) # To check if the linear sequences are not prime.


l = len(b) + 1 # l is incremented by 1 to accommodate the range function below.

S = 0 # The sum of non-prime sequences.

for k in range(1, l):

    if b[:k] not in s: # Generates sequences as k iterates through values in range.

        S += int(b[:k])


print "The non-prime sum 'S' --> ",S

k = 1
l = int(b[:1])
n = int(b[0])
while S > 100:

    S = float(S/(s[l] + n*k))

    k += 1


print "S -->", S, "|", "Decimal part of S -->", S - int(S), "|", "Decimal part of time when program began -->", a

[Thisisnotanid]

Interesting aside to whoever's interested: The CODE tags don't work if there is a bold tag in the text. For example:

print "This highlighting does indicate Python syntax."

[B]This sentence is not bold.[/B]

I don't know if this known or not or if the issue persists for other tags/tag combinations as well.

[Thisisnotanid]

for my purposes (actually need to use some pseudo random things from time to time), I have been quite happy to simply
import random

Of course, if you want to write your own that's different.

The "bestest" random function I ever read about: Get bits from the microphone input. There may be no need to actually hook up a microphone: You are after noise, and the circuit may make enough noise on its own. However random.org does use actual input (atmospheric noise gotten by tuning radio receivers between stations). As you will find if you do some reading, this kind of TRNG (True Random Number Generator) has some good and bad features compared to a PRNG (Pseudo...).

Nice! Great stuff they have.

[vegaseat]

Interesting aside to whoever's interested: The CODE tags don't work if there is a bold tag in the text. For example:

print "This highlighting does indicate Python syntax."

[B]This sentence is not bold.[/B]

I don't know if this known or not or if the issue persists for other tags/tag combinations as well.

Valid Python code wouldn't allow bold tags in code lines, just inside strings.

All in all, one more interesting approach to the creation of random numbers. However, speed is not a premium here. How does it compare in randomness with Pythons built-in random module (Mersenne Twister)?

BTW, many many moons ago, I was still using C and explored some random generators using the floating-point calculation errors (CPU noise?).
http://www.daniweb.com/software-development/c/code/216329

[TrustyTony]

The good randoness is sometimes little counterintuitive though, and I would not bet on uniformity of your random numbers. the Art of Computer Programming by Knuth is thing to read if you want scientific understanding about things.

As example while getting to know about facts on Sudoku I ran accross in fact that numbers from Sudoku solutions are especialy good in randomness, which is not probably your first intuition.

[Thisisnotanid]

Valid Python code wouldn't allow bold tags in code lines, just inside strings.

All in all, one more interesting approach to the creation of random numbers. However, speed is not a premium here. How does it compare in randomness with Pythons built-in random module (Mersenne Twister)?

BTW, many many moons ago, I was still using C and explored some random generators using the floating-point calculation errors (CPU noise?).
http://www.daniweb.com/software-development/c/code/216329

Seems like good stuff. Although, if you have any idea, what's the prevalent random generator in computing circles as of now? I have no idea how to compare the randomness of my generator to others out there. I'm guessing the one I posted about is a TRNG. How would you rate it? I'm not very familiar with C yet, so I wasn't able to get much from your link but thanks!

[Thisisnotanid]

The good randoness is sometimes little counterintuitive though, and I would not bet on uniformity of your random numbers. the Art of Computer Programming by Knuth is thing to read if you want scientific understanding about things.

As example while getting to know about facts on Sudoku I ran accross in fact that numbers from Sudoku solutions are especialy good in randomness, which is not probably your first intuition.

Thanks Tony. Would generators that provide uniform numbers be truly random? I'm not very experienced with this stuff, this was just my initial take at randomness (it was kinda random lol).

[vegaseat]

Most popular computer languages come with a pseudo random number generator. It produces a sequence of numbers that seems to be random. However, the sequence will eventually repeat, making it predictable.

[TrustyTony]

Algorithm M (Randomizing by shuffling). Given methods for generating two
sequences <Xn> and <Yn>, this algorithm will successively output the terms of a
"considerably more random" sequence. We use an auxiliary table V[O], V[l],
. . . , V[k - 1], where k is some number chosen for convenience, usually in the
neighborhood of 100. Initially, the V-table is filled with the first k values of the
X-sequence.
MI. [Generate X,Y.] Set X and Y equal to the next members of the sequences
(Xn) and (Yn), respectively.
M2. [Extract j] Set j <-⌊kY/m⌋, where m is the modulus used in the sequence
<Yn>; that is, j is a random value, 0 <= j < k, determined by Y.
M3. [Exchange.] Output V[j] and then set V[j] <- X.

As an example, assume that Algorithm M is applied to the following two
sequences, with k = 64:
Xo = 5772156649,
Xn+l = (3141592653Xn + 2718281829) mod 235;
Yo = 1781072418,
Yn+l = (2718281829Yn + 3141592653) mod 235.
(12)
On intuitive grounds it appears safe to predict that the sequence obtained by
applying Algorithm M will satisfy virtually anyone's requirements for random-
ness in a computer-generated sequence, because the relationship between nearby
terms of the output has been almost entirely obliterated. Furthermore, the time
required to generate this sequence is only slightly more than twice as long as it
takes to generate the sequence (X,)
alone.

Knuth. TACP, Vol. 2, Seminumerical Algorithms p.30 or 32 depending on edition

⌊ ⌋ in M2 should have lines only down ie floor.

[vegaseat]

Just for kicks, here is a manual random number generator ...

import time

def get_random_number():
    """a manual random number generator"""
    start = time.time()  
    #print(start)  # test
    raw_input("Press Enter ...")
    #print(time.time())  # test
    # returns a number from 0 to 99
    return int((time.time() - start) * 1000) % 100
    
random_number = get_random_number()
print(random_number)

[Thisisnotanid]

@ Tony: Thanks Tony, interesting approach. Though I'm not very informed about implementation of such algorithms, how would it actually take place? Seems to be rather resource heavy.

@ Vegaseat: Nice random generator. It's also very concise and would run well without holding down a lot of resources. It's also truly random, I believe, unlike (as I think is the case) the generator I provided.

I was looking at my code again and realized that in certain scenarios the code would not at all produce random numbers. In fact, we could always determine the output of the generator in those situations (in theory). My reasoning is as follows. Since the generator depends on the time the program was started, we could write a program to execute the generator at a given time, and if everything went according to plan we would know beforehand what the number generated would be.

Of course, real world scenarios present the algorithm a different implementation. Even if we asked the program to be executed at a particular time, there is no guarantee the program will be executed at that exact time. Furthermore even if the code was executed at the time scheduled, the time the CPU got to the instruction:

a = t.time() - int(t.time())

would almost entirely depend on local variables. However, since my code depends on only the first 6 digits of decimal time, the above workaround may successfully be implemented as most computers today are fast enough to accomplish such a task. In such a light, this generator may be deemed not at all random owing to a complete lack of the need of "user input". The code I had in mind was the following; this particular implementation waits till the decimal part of time is 0:

import time as t

a = t.time() - int(t.time())

while a != 0 or a == 0:

    a = t.time() - int(t.time())

    if a == 0:
        print "Ha ha, fooled you! ;-)"
        break

A simple fix is to ask a user for "input". Taking from Vegaseat a bit we have:

#... the code before the following line has been omitted:

raw_input("Press Enter") # Prevents the aforementioned workaround.

a = t.time() - int(t.time())

# The code then continues as it did before...

Finally, I was thinking about implementing something along the lines of getting the average of the current temperature in a city in Sweden, the stock price of a S&P 500 tech company at 8:35 this morning, the exchange rate of the British Pound and the Japanese Yen yesterday at 4:15 in the morning as a random generator. However, I lack the programming know-how to implement such a program at the moment (hehe) :)

[TrustyTony]

Interesting information on choosing the random seed, including info why only using time as seed, can be found in document: http://docstore.mik.ua/orelly/networking/puis/ch23_08.htm (includes the details of using sound input noise).

[TrustyTony]

Here my implementation of the two generators in Knuth's example, with seeding from time, even it is less than ideal (without seed flag allways the same sequence from given x0 and y0)

from __future__ import print_function

import math
import time
k, modulo = 64, 2**35


def x(nx=5772156649):
    while True:
        nx = (3141592653*nx + 2718281829) % modulo   
        yield nx
    

def random_generator(n=0, seed=False):
    if seed:
        # seed x and y start values with time based start
        #print(time.time())
        ny = int(time.time() * modulo) % modulo / (1<<16)
        #print('ny start: %i, %s' % (ny, bin(ny)))
    else:
        ny = 1781072418

    nx_gen, count = x(ny**2) if seed else x(), 0
    v = [next(nx_gen) for c in range(k+1)]
    while True:
        j = k * ny // modulo
        yield v[j]
        if n:
            count+=1
            if count >= n: return
        v[j] = next(nx_gen)
        ny = (2718281829*ny + 3141592653) % modulo

if __name__ == '__main__':
    for r in random_generator(100, True):
        print(r, end= ',')

[Schol-R-LEA]

Is there any specific application for this, or are you simply trying to understand PRNGs better? Different applications can have very different requirements, above and beyond randomness, such as needing the result to be random within a given range (simply using a modulo isn't a very good solution, as it can introduce a bias).

I might add that it is often suggested that you not use a HRNG directly, but rather to use it as a source for seeds. The reasoning there is that a) not all platforms will have a HRNG, and those which do may have very different ones, so separating the source of randomness from the final generated value can be a good idea; b) even 'truely random' sources can have biases, such as the range over which the random input varies, and external interactions could potentially bias the results (a cosmic-ray shower or sunspot activity, for example, could cause a radiological detector to show a consistently higher value than background or even a fixed source); and c) you to change the pseudo-random number generator for different specifics.

One possible approach is to have a list of pseudo-random generators, and take at least three different readings from the HRNG: one for a seed value, one to select the algorithm to use, and one to set a timer for when to next re-seed the generator. This may be a bit too elaborate for practical use, as it doesn't give that much more randomness in and of itself.