Mathematics
Last update: 01/04/09 12:00 pm
Thoughts on Random Numbers
Often I find a need to make a binary choice of little significance based on limited information. In such situations I catch myself thinking: what if I had a fair coin in my pocket, so I could flip it and make a decision based on the outcome of the toss? Unfortunately I don't carry coins with me and my coin tossing skills are not very good. So I thought about designing an electronic device that would be able to generate a random number corresponding to the outcome of a virtual coin toss (or a die toss.) The major obstacle is the nature of computer based random number generators: they are pseudo-random. Back in the late 1940s, John von Neumann proposed a method to generate random numbers as follows: pick an integer of certain length, square it and extract an integer of the same length from the square. For example, pick 7339. Square of 7339 is 53860921. Now extract the middle 4 digits and obtain 8609. There is an infinite variety of methods like this one for random number process. If one was to record such sequence of numbers and present it to a person without prior knowledge of computer algorithm, it would be very hard to detect the underlying pattern.
However, a real coin toss is a truly random event and, luckily, there is a method to generate real random numbers for coin toss simulation. The idea is based on human involvement in the process: every time you need a random number, you have to request it from the algorithm. The time of your request is a random event. So, let's suppose that the program keeps switching a variable R between two different values (e.g. zero and one.) If the user requests coin toss, the program gives the current value of R. One may attack this method as follows. Suppose the user clocks each request down to a second so that the "coin tosses" are carried out with certain periodicity. Due to the alternating nature of the algorithm, there will be a time when the outcome of the next simulation could be predicted. Again, the key is human involvement. The sole fact that user places requests manually implies that human error factor is involved. Probably very few people on Earth can click on the button with regularity down to one millionth of a second. Due to the variation in timing between each subsequent call, this simulation process will produce truly random results.
As a demonstration of the proposed algorithm, I encourage you to download the simulation here. It is written in Visual Basic 2005 and executable file is included.
Fourier Series and Transform
The need to approximate functions of various form arises in a multitude of scientific disciplines ranging from physics to biology. Approximations provide mathematicians and computer programmers with an efficient means of evaluating a functional value at a desired point. While there are infinitely many ways to approximate a function, only few enjoy such popularity as Fourier series.
It is important to have a firm grasp of vector spaces in order to understand how Fourier series and transform work. To begin with, functions can be treated as vectors in finite dimensions and, consequently, they can be projected onto different vector spaces. One of the most useful spaces for such projection is spanned by the following vectors:
cos (0.0 x θ), sin (0.0 x θ), cos (1.0 x θ), sin (1.0 x θ), cos (2.0 x θ), sin (2.0 x θ) ... cos (n x θ) and sin (n x θ)
As you see, the basis vectors are formed by substituting a multiple of θ as an argument of trigonometric function cos and sin. The first vector is, in fact, 1.0 for all θ and the second vector is 0.0, so we omit it.
Vladimir I. Arnold's Cat Map
This is an image processing algorithm which can be easily implemented on computer. It involves relocating pixels on an image canvas according to transformed coordinates. Coordinate vector transformation is as follows:
Initial iterations of the algorithm will produce striped images (e.g. my photo at "About Me" page.) Subsequent iterations will result in partial convergence of the algorithm at some point (e.g. ghost images.)
My implementation of this algorithm in C++ is available here. Keep in mind that in order for this program to work, it has to receive an image of square dimensions. The image should be in bmp format and the resulting image is stored in bmp format as well. This program can be used for basic electronic image protection.
Bubble Tower Problem
This problem is my favorite one. For complete description, see this page.