The Music of the Algorithms

Thoughts on Computing, the Universe, and Everything

Introduction to Pseudo-Random Number Generators

Published on March 9, 2016. Random Numbers

Pseudo-random number gen­er­a­tors are an im­por­tant tool in Com­puter Sci­ence for a dif­ferent number of ap­pli­ca­tions. I re­cently pre­sented a little in­tro­duc­tion to the theory and the prac­tice of this very in­ter­esting field.

Random num­bers are needed very often in Com­puter Sci­ence. Ran­dom­ized al­go­rithms, sci­en­tific sim­u­la­tions, and cryp­tog­ra­phy, are just a few ap­pli­ca­tions where ran­dom­ness plays a cru­cial role. Pseudo-random number gen­er­a­tors, that is, al­go­rithms that pro­duce se­quences of values that can be used as random num­bers in these ap­pli­ca­tions, is an im­por­tant field. A few years ago I tried to un­der­stand the ba­sics of this field as part of the exam of an Ad­vanced Al­go­rithms course.

The re­sult is a little doc­u­ment (in Ital­ian, sorry) where I sum­ma­rize the basic con­cepts be­hind the dif­ferent pos­sible de­f­i­n­i­tions of ran­dom­ness and a couple of ex­am­ples of con­crete gen­er­a­tors. Re­cently I was asked to present again this ma­te­rial at a course and I took the op­por­tu­nity to re­fresh and up­date the slides.

Here you can find the doc­u­ment and the slides. Have a good read!

Up­date

Slides have been up­dated on De­cember 21, 2016.