Fibonacci and Randomness

Anyone who considers arithmetical methods of producing random bits is, of course, in a state of sin.

Hey all,

I am sure most of you have heard of Fibonacci numbers. For those who don’t I’ll quickly revise them,

nth Fibonacci no. is defined as Fn = Fn-1 + Fn-2  with F0 = 0, F1 = 1. May be the following sequence will help : 0,1,1,2,3,5,8,13,21,34,55,89,144……….. and so on.

Fibonacci numbers have some of the coolest properties and find applications in variety of fields. But the post is not to discuss it all. (Rather one post is not sufficient for it 😉 ) What I will be discussing how they are applied in real world. One example might be lagged Fibonacci generator.

In computer science one of the areas of research have been random number generation. Pseudo Random Number Generators(PRNG) or also known as Deterministic Random Bit Generators(DRBG) are algorithms which generate sequence of numbers which approximate properties of random numbers. Mind well the sequences are not truly random as with a relatively small set of initial values the sequence can be entirely determined. Best words of caution for misinterpretation are by John Von Neumann with which the post starts. Although they are so close to being truly random, and given their excellent speed of generation and reproducibility, they find themselves central in simulations, cryptography and procedural generations. #I’ll cover random numbers in some other post.

One of the class of PRNG is based on Fibonacci Numbers which is Lagged Fibonacci generator(LFG). Let’ see how.

            Fibonacci sequence proceeds with addition of last two numbers in the sequence. Lets say I don’t want to add the last two for next entry. For example I am adding 22nd last and 44th last for next. In other words I am introducing a lag in the sequence. This is what LFG is all about. Simple but beautiful idea! Lets define it in a precisely

Sn = Sn-j * Sn-k (mod m) 0 < j < k;

Here j and k are the specified lags. This depends upon the one who is designing one such LFG for his purpose. * is a general binary operation – addition, subtraction, multiplication or bitwise XOR. m is generally of the form 2Mdepending upon your size often 232 or 264.

#If * is XOR then for sufficient randomness any j and k are not allowed. Involves complex theory so skipping it.

Depending upon * they are Additive LFG or Multiplicative LFG.

Clearly the generator has to remember past k values. Thus comes the approximation in randomness. The sequence can be shown to have a period. The period depends on values of j,k,m and *. But we can determine the maximum period for it. LFGs have a maximum period of (2k – 1)*2M-1 if * is addition or subtraction, (2k-1)*k if * is XOR and if * is multiplication the maximum period is (2k – 1)*2M-3 i.e. 1/4 of period of the additive case. Greater the period more random the sequence will be. A possible pair where maximum value is achieved is {j,k} = {24,55}.

So where it is used? Well a particular application which comes to my mind is in game engines. I know one engine which uses it, Freeciv. It is a turn-based strategy game released under GNU general public license. Boost library for C++ used for enhancing functionality uses LFG. Also Oracle database implements this in DBMS_RANDOM package.

Actually there is a lot more to discuss on this alone. But I don’t want to stretch the post even longer, so may be in some other post I’ll cover the rest of the stuff.

– Payas

Advertisements

4 responses to “Fibonacci and Randomness

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s