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,

n^{th} Fibonacci no. is defined as F_{n} = F_{n-1} + F_{n-2 }with F_{0 }= 0, F_{1} = 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

S_{n} = S_{n-j} * S_{n-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 2^{M}depending upon your size often 2^{32} or 2^{64}.

#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 (2^{k} – 1)*2^{M-1} if * is addition or subtraction, (2^{k}-1)*k if * is XOR and if * is multiplication the maximum period is (2^{k} – 1)*2^{M-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

Like!! A good informative post!!

Thanks 🙂

Now this look more Payas-like than the old blog.

Good Stuff.

Hehe. I doubt no one reads the old one. Anyways there is lot more coming next week, stay subscribed 🙂