Rand function Method

Being curious about such things, I could not help but take a look. To do so, just compile a very simple program such as:

#include <stdlib.h>

void tst_rand (void)  {
  int i;
  data int r;

  for (i = 0; i < 100; i++)
  {
	r = rand();

  }

}

main()
{
  tst_rand();
}

Being curious about such things, I could not help but take a look. To do so, just compile a very simple program such as:

#include <stdlib.h>

void tst_rand (void)  {
  int i;
  data int r;

  for (i = 0; i < 100; i++)
  {
	r = rand();

  }

}

main()
{
  tst_rand();
}

The rand() functions is not a random function,since the value in the same order is the same.
I mean,the start value is the same every time you execute the program.
I think the real random function should be able to generate different value when you start the program every time.

There is a special check for the LFSR being in the all-ones state, although I am not clear why that is required.

Hm. Isn't that to avoid the LFSR getting trapped into a degenerate state where it will keep producing the same output forever? LFSRs work fine until they happen to generate a random all-1s, and then they're stuck producing that all-1s forever?

I thought C libraries were usually linear congruential. Interesting.

Pseudo-random number generators (RNG) in software typically are designed to allow for a "seed" value which determines the sequence of random numbers that are generated. This is useful for many tasks (testing, simulation) where you want to be able to test random input, but you also need to repeat tests with the exact same "random" input. You set the seed value for the RNG with the srand() function. If you don't call srand(), then you'll have the default seed value (1) every time you start your program, and thus have the same series of random numbers, without having to store them all.

To generate "really" random numbers, you also have to randomize the seed. Typical methods for doing so are to use low-order bits of a fast clock as the seed. Other methods are to use the time(s) of user key input or network packet arrival as a source of randomness for the seed value. Thus, you can get repeatable or non-repeatable sequences of random numbers, depending on whether you know what your seed value is.

If you're really dead serious about the randomness of your RNG (say, you're building a slot machine), you won't use a software function at all, but will design some dedicated hardware that generates truly random numbers, say by amplifying noise. Any software function is going to be ultimately deterministic, even if it's really complicated; the only truly random number generators we know of are quantum events.

Read all about pseudo-random number generators:
http://www.wikipedia.org/wiki/Pseudo-random_number_generator

If you're really dead serious about the randomness of your RNG (say, you're building a slot machine), you won't use a software function at all, but will design some dedicated hardware that generates truly random numbers, say by amplifying noise
If a button press or other human interaction tahes place for each need of a random number, the read of a free running timer will do just fine for true randomness.

Erik

The sequence of numbers produced by an algorithm (especially the common ones like LCG and LFSR) have some statistical correlation. They all involve state that ties them to previous results.

The button press / timer is a reasonable way to get a seed for most purposes. But, as I said, if you're really concerned about producing an uncorrelated stream of numbers, you'll need some hardware support. There are relatively few applications that need to obsess over the randomness of their numbers in this detail, though. Do you really need to go to this much trouble (http://www.fourmilab.ch/hotbits/)? Well, maybe if you're doing cryptography, or generating lotto numbers, or doing some heavy duty Monte Carlo simulation.

A nice summary of the topic:
http://www.faqs.org/rfcs/rfc1750.html

Run in the simulator, set a breakpoint r = rand(); and then use the disassembly window. Single set into the library function


This step already used(to check the coding in disassembly window)to see what they are doing for generating random function.I could able to understand assembly coding and able to decode it.

But still I am not clear which method they used to generate the random values.

To give a more complete answer, you first need to understand a little more about Linear Feedback Shift Registers. Start here: http://www.newwaveinstruments.com

LFSRs can be implemented in either hardware or software, obviously the Keil random function is in software, but it is easier to conceive it as a bit of hardware.

The Keil random function uses a Fibonacci 32-bit shift register. Looking back at the hurried notes I took when looking at rand(), the Keil LFSR seems to have just two taps: at g2 and g30.

LFSRs are usually designed to be of maximum length - ie the maximum number of times the LFSR can be clocked before it will return to the same state - for an LFSR of n bits the maximum length will be (2^n)-1. In many cases, this means that the length of the sequence will be conveniently prime. The web-site referenced above gives tap lists for LFSRs that produce the maximum possible length sequences from LFSRs of various sizes, but the Keil choice of taps is not listed. So, I dont know what the length of Keil's LFSR is. It may be that the LFSR will generate several sequences of different lengths - depending on the initial state determined by the seed.

Another feature of a maximum length LFSR is that once initialised correctly, it will never get "stuck" in a particular state - so checking the state of the LFSR is unnecessary.

For each call of rand(), the LFSR is clocked 15 times so that rand(). I guess that the reason being that the application may make use of up to 16 bits returned by rand().

Generally speaking, more taps is better (up to half the number of LFSR bits). All LFSRs are eqully deteministic of course, but more taps stirs the LFSR in more "unexpected" ways.

A better rand()? My choice would be a 31-bit LFSR (because (2^31)-1 is prime) and a Galois implementation because it is easy to implement many taps with no extra software overhead. The new rand() would take a parameter that indicates the required number of bits; rand() will then clock the LFSR the required number of times and the application should n least significant bits. I don't see any reason why rand() should not return 31 bits.

"I don't see any reason why rand() should not return 31 bits."

I don't know anything about random numbers but I can answer this: ANSI defines rand() as returning an int, and Keil seem to try and be compliant wherever possible.

Stefan

See: http://www.keil.com/forum/docs/thread3202.asp

Hi Graham Gole,


Thanks for your kind reply!
Need your email ID to keep in touch.


Regards,
Gopi