Python Programming - IX. On Randomness

50 %
50 %
Information about Python Programming - IX. On Randomness
Technology

Published on February 4, 2014

Source: slideshare.net

IX. ON RANDOMNESS Engr. RANEL O. PADON

PYTHON PROGRAMMING TOPICS I •Introduction to Python Programming II •Python Basics III •Controlling the Program Flow IV •Program Components: Functions, Classes, Packages, and Modules V •Sequences (List and Tuples), and Dictionaries VI •Object-Based Programming: Classes and Objects VII •Customizing Classes and Operator Overloading VIII •Object-Oriented Programming: Inheritance and Polymorphism IX •Randomization Algorithms X •Exception Handling and Assertions XI •String Manipulation and Regular Expressions XII •File Handling and Processing XIII •GUI Programming Using Tkinter

ON RANDOMNESS Randomization Algorithms * Random numbers are used for testing the performance of programs, creating scientific simulations, and so on. * A pseudorandom number generator (PRNG) is an algorithm for generating a sequence of numbers that approximates the properties of random numbers. * The sequence is not truly random in that it is completely determined by a relatively small set of initial values (random seed)

ON RANDOMNESS Randomization Algorithms Early Algorithm Middle-Square Method * take any number, square it, remove the middle digits of the resulting number as the "random number", then use that number as the seed for the next iteration. * squaring the number "1111" yields "1234321", which can be written as "01234321", an 8-digit number being the square of a 4-digit number. This gives "2343" as the "random" number. Repeating this procedure gives "4896" as the next result, and so on.

ON RANDOMNESS Randomization Algorithms 1.) Blum Blum Shub (cryptographically sound, but slow) 2.) Mersenne Twister - fast with good statistical properties, - used when cyptography is not an issue - used in Python 3.) Linear Congruential Generator - commonly-used in compilers and many, many others

ON RANDOMNESS Randomization Algorithms 2.) Mersenne Twister Algorithm is based on a matrix linear recurrence over a finite binary field provides for fast generation of very high-quality pseudorandom numbers, having been designed specifically to rectify many of the flaws found in older algorithms. used in PHP, Ruby and Python name derives from the fact that period length is chosen to be a Mersenne prime

ON RANDOMNESS Mersenne Twister Algorithm 2.) Mersenne Twister Algorithm It has a very long period of 219937 − 1. While a long period is not a guarantee of quality in a random number generator, short periods (such as the 232 common in many software packages) can be problematic. It is k-distributed to 32-bit accuracy for every 1 ≤ k ≤ 623 It passes numerous tests for statistical randomness, including the Diehard tests. It passes most, but not all, of the even more stringent TestU01 Crush randomness tests.

ON RANDOMNESS Mersenne Twister Algorithm 2.) Mersenne Twister Algorithm (as used in the random module of Python) # Create a length 624 list to store the state of the generator MT = [0 for i in xrange(624)] index = 0 # To get last 32 bits bitmask_1 = (2 ** 32) - 1 # To get 32. bit bitmask_2 = 2 ** 31 # To get last 31 bits bitmask_3 = (2 ** 31) - 1

ON RANDOMNESS Mersenne Twister Algorithm 2.) Mersenne Twister Algorithm def initialize_generator(seed): "Initialize the generator from a seed" global MT global bitmask_1 MT[0] = seed for i in xrange(1,624): MT[i] = ((1812433253 * MT[i-1]) ^ ((MT[i-1] >> 30) + i)) & bitmask_1

ON RANDOMNESS Mersenne Twister Algorithm def extract_number(): ""“ Extract a tempered pseudorandom number based on the indexth value, calling generate_numbers() every 624 numbers ""“ global index global MT if index == 0: generate_numbers() y = MT[index] y ^= y >> 11 y ^= (y << 7) & 2636928640 y ^= (y << 15) & 4022730752 y ^= y >> 18 index = (index + 1) % 624 return y

ON RANDOMNESS Mersenne Twister Algorithm def generate_numbers(): "Generate an array of 624 untempered numbers" global MT for i in xrange(624): y = (MT[i] & bitmask_2) + (MT[(i + 1 ) % 624] & bitmask_3) MT[i] = MT[(i + 397) % 624] ^ (y >> 1) if y % 2 != 0: MT[i] ^= 2567483615 if __name__ == "__main__": from datetime import datetime now = datetime.now() initialize_generator(now.microsecond) for i in xrange(100): "Print 100 random numbers as an example" print extract_number()

ON RANDOMNESS Linear Congruential Generator 3.) Linear Congruential Generator represents one of the oldest and best-known pseudorandom number generator algorithms. the theory behind them is easy to understand, and they are easily implemented and fast.

ON RANDOMNESS Linear Congruential Generator 3.) Linear Congruential Generator

ON RANDOMNESS Randomization Algorithms 3.) Linear Congruential Generator The basic idea is to multiply the last number with a factor a, add a constant c and then modulate it by m. Xn+1 = (aXn + c) mod m. where X0 is the seed.

ON RANDOMNESS Random Seed Random Seed * a number (or vector) used to initialize a pseudorandom number generator * crucial in the field of computer security. * having the seed will allow one to obtain the secret encryption key in a pseudorandomly generated encryption values

ON RANDOMNESS Random Seed Random Seed * two or more systems using matching pseudorandom number algorithms and matching seeds can generate matching sequences of non-repeating numbers which can be used to synchronize remote systems, such as GPS satellites and receivers.

ON RANDOMNESS Linear Congruential Generator a=3 c=9 m = 16 xi = 0 def seed(x): global xi xi = x Random Number Generator def rng(): global xi xi = (a*xi + c) % m return xi for i in range(10): print rng()

ON RANDOMNESS Linear Congruential Generator LCG (Standard Parameters) Good One

ON RANDOMNESS Linear Congruential Generator Using java.util.Random parameters a = 25214903917 c = 11 m = 2**48 xi = 1000 def seed(x): global xi xi = x def rng(): global xi xi = (a*xi + c) % m return xi def rng_bounded(low, high): return low + rng()%(high - low+1) for i in range(10): rng_bounded(1, 10)

ON RANDOMNESS Minimal Standard MINSTD by Park & Miller (1988) known as the Minimal Standard Random number generator a very good set of parameters for LCG: m = 231 − 1 = 2,147,483,647 (a Mersenne prime M31) a = 75 = 16,807 (a primitive root modulo M31) c=0 often the generator that used for the built in random number function in compilers and other software packages. used in Apple CarbonLib, a procedural API for developing Mac OS X applications

ON RANDOMNESS Linear Congruential Generator Using MINSTD parameters a = 7**5 c=0 m = 2**31 - 1 xi = 1000 def seed(x): global xi xi = x def rng(): global xi xi = (a*xi + c) % m return xi def rng_bounded(low, high): return low + rng() % (high - low+1) for i in range(10): rng_bounded(1, 2)

ON RANDOMNESS Linear Congruential Generator Tossing 1 Coin using LCG MINSTD (1 million times) from __ future__ import division if __name__ == '__main__': main() a = 7**5 c=0 m = 2**31 - 1 xi = 1000 def seed(x): global xi xi = x def rng(): global xi xi = (a*xi + c) % m return xi

ON RANDOMNESS Linear Congruential Generator Tossing 1 Coin using LCG MINSTD (1 million times) def rng_bounded(low, high): return low + rng() % (high - low+1) (heads, tails, count) = (0, 0, 0) for i in range (1, 1000001): count += 1 coin rng_bounded(1,2) if coin == 1: heads += 1 else: tails += 1

ON RANDOMNESS Linear Congruential Generator Tossing 1 Coin using LCG MINSTD (1 million times) print "heads is ", heads/count print "tails is ", tails/count

ON RANDOMNESS Linear Congruential Generator Tossing 1 Coin using Python randrange() (1 million times) from __ future__ import division import random if __name__ == '__main__': main() (heads, tails, count) = (0, 0, 0) random.seed(1000) for i in range (1,1000001): count +=1 coin = random.randrange(1,3)

ON RANDOMNESS Linear Congruential Generator Tossing 1 Coin using Python randrange() (1 million times) if coin == 1: heads += 1 else: tails += 1 print "heads is ", heads/count print "tails is ", tails/count

ON RANDOMNESS Linear Congruential Generator Tossing 2 Coins using LCG MINSTD (1 million times) from __ future__ import division if __name__ == '__main__': main() a = 7**5 c=0 m = 2**31 - 1 xi = 1000 def seed(x): global xi xi = x def rng(): global xi xi = (a*xi + c) % m return xi

ON RANDOMNESS Linear Congruential Generator Tossing 2 Coins using LCG MINSTD (1 million times) def rng_bounded(low, high): return low + rng() % (high - low+1) (heads, tails, combo, count) = (0, 0, 0, 0) for i in range (1,1000001): count += 1 coin1 = rng_bounded(1,2) coin2 = rng_bounded(1,2) sum = coin1 + coin2 if sum == 2: heads += 1 elif sum == 4: tails += 1 else: combo += 1

ON RANDOMNESS Linear Congruential Generator Tossing 2 Coins using LCG MINSTD (1 million times) print "head is ", heads/count print "tail is ", tails/count print "combo is ", combo/count

ON RANDOMNESS Linear Congruential Generator Tossing 2 Coins using Python randrange() (1 million times) from __ future__ import division import random if __name__ == '__main__': main() (heads, tails, combo, count) = (0, 0, 0, 0) random.seed(1000) for i in range (1,1000001): count +=1 coin1 = random.randrange(1,3) coin2 = random.randrange(1,3) sum = coin1 + coin2

ON RANDOMNESS Linear Congruential Generator Tossing 2 Coins using Python randrange() (1 million times) if sum == 2: heads += 1 elif sum == 4: tails += 1 else: combo += 1 print "head is ", heads/count print "tail is ", tails/count print "combo is ", combo/count

ON RANDOMNESS Results Summary Almost Similar Results Tossing 1 Coin using LCG MINSTD vs Python randrange() (1 million times) Tossing 2 Coins using LCG MINSTD vs Python randrange() (1 million times)

ON RANDOMNESS Linear Congruential Generator Tossing 1 Coin using LCG MINSTD (1000 times) More Elegant Way (Using List)

ON RANDOMNESS Linear Congruential Generator Tossing 2 Coins using LCG MINSTD (1 million times) More Elegant Way (Using List) from __future__ import division if __name__ == '__main__': main() xi = 1000 def seed(x): global xi xi = x def rng(a=7**5, c=0, m = 2**31 - 1): global xi xi = (a*xi + c) % m return xi def rng_bounded(low, high): return low + rng() % (high - low+1)

ON RANDOMNESS Linear Congruential Generator Tossing 2 Coins using LCG MINSTD (1 million times) More Elegant Way tosses = [] for i in range (1, 1000001): tosses += [rngNiRanie(1, 2) + rngNiRanie(1, 2)] print "heads count is ", tosses.count(2) / len(tosses) print "tails count is ", tosses.count(4) / len(tosses) print "combo count is ", tosses.count(3) / len(tosses)

ON RANDOMNESS a = 25214903917 c = 11 m = 2**48 xi = 1000 def seed(x): global xi xi = x def rng(): global xi xi = (a*xi + c) % m return xi def ranie(lowerBound, upperBound): #ano laman nito? # for i in range(10): ranie(1,10)

REFERENCES  Deitel, Deitel, Liperi, and Wiedermann - Python: How to Program (2001).  Disclaimer: Most of the images/information used here have no proper source citation, and I do not claim ownership of these either. I don’t want to reinvent the wheel, and I just want to reuse and reintegrate materials that I think are useful or cool, then present them in another light, form, or perspective. Moreover, the images/information here are mainly used for illustration/educational purposes only, in the spirit of openness of data, spreading light, and empowering people with knowledge. 

 User name: Comment:

Related presentations

Neuquén y el Gobierno Abierto

October 30, 2014

Presentación que realice en el Evento Nacional de Gobierno Abierto, realizado los ...

Decision CAMP 2014 - Erik Marutian - Using rules-b...

October 16, 2014

In this presentation we will describe our experience developing with a highly dyna...

Schema.org: What It Means For You and Your Library

November 7, 2014

Presentation to the LITA Forum 7th November 2014 Albuquerque, NM

WearableTech: Una transformación social de los p...

November 3, 2014

Un recorrido por los cambios que nos generará el wearabletech en el futuro

O Impacto de Wearable Computers na vida das pessoa...

November 5, 2014

Um paralelo entre as novidades & mercado em Wearable Computing e Tecnologias Assis...

All you need to know about the Microsoft Band

November 6, 2014

Microsoft finally joins the smartwatch and fitness tracker game by introducing the...

Related pages

Python Programming Tutorial 17: Randomness and Time - YouTube

Python Programming Tutorial 17: Randomness and Time Tek Union. Subscribe Subscribed Unsubscribe 14 14. ... Python Programming Tutorial - 17: ...

nistbeacon 0.9.1 : Python Package Index - PyPI - the ...

Python NIST Randomness Beacon. WARNING: DO NOT USE BEACON GENERATED VALUES AS SECRET CRYPTOGRAPHIC KEYS. ... Python; Programming Language :: Python :: 3.3;

View 4775 Randomness posts, presentations, experts, and more. Get the professional knowledge you need on LinkedIn. LinkedIn Home What is LinkedIn?

9.6. random — Generate pseudo-random numbers — Python ...

Python uses the Mersenne Twister as the core ... If randomness sources are provided by the operating ... Returns a Python integer with k random bits.

Randomness in Python Lesson by Carter Sande - YouTube

Carter Sande, young coauthor of the Python ... Randomness in Python Lesson by Carter Sande ... Briccetti's Python programming class ...

random - Randomness in Python - Stack Overflow

Ask programming questions ... Randomness in Python. up vote 6 down vote favorite. ... Understanding “randomness ...