I don't think there are any reason to discuss how it should be changed without proper testing to confirm that there indeed is an issue. We might just end up making it worse than it was beforehand ; )
3) so the random series produced bei Random() is faked or manipulated in some way
In my previous post I explain how the functions are implemented in NXC. Just to make it clear, rand() is implemented this way:
So if Random(x) is manipulated or faked, rand() is too.
that's exactly what I'm trying to say why I don't use Lego-rand() any more:
the Lego-rand() does not produce statistically/stochastically independent usable random series.
This simply already shown by the fact, that all meantime Lego-rand() produced series modulo 16 or what ever are not equally distributed - even more: they are constantly in a similar way unequally distributed. So Lego-rand() can be sacrificed at any rate. We just will have to find a better (or far-better) substitute.
I just want to see an example where it is not possible to get enough random results from the internal random generator. Since you can change "rand() % 16" to "Random(16)" in your example to get results which are good enough, it doesn't require you to reimplement a better RNG.
A proper RNG implemented in NXC would be a lot slower than the internal (and it would increase the .rxe size). If there is no practical difference between the two in the application then there is no reason to use it.
So if Random(x) is manipulated or faked, rand() is too.
that's exactly what I'm trying to say why I don't use Lego-rand() any more:
the Lego-rand() does not produce statistically/stochastically independent usable random series.
This simply already shown by the fact, that all meantime Lego-rand() produced series modulo 16 or what ever are not equally distributed - even more: they are constantly in a similar way unequally distributed. So Lego-rand() can be sacrificed at any rate. We just will have to find a better (or far-better) substitute.
Evaluation of Random Number Generator is serious business for some applications http://csrc.nist.gov/groups/ST/toolkit/rng/index.html. However, it is non-trivial to implement good random number generators, especially in embedded systems which has limited processing power. I don't think a new random number generator should be implemented in NXC, it really should be provided as part of the firmware due to the computational overheads. Normally the tradeoff is whichever algorithm is 'good enough' for the application at hand. I suspect that the NXT firmware developers just picked the most commonly available algorithm and used it.
spillerrec wrote:Yes, modulus is the regular way, but that doesn't mean it is the best way.
As far as I have heard the issue is that many number generators isn't random enough at the lower significant bits, so you need to use bits at a higher range of bit to ensure that it is completely random. This is where modulus with lower values fail.
Well, a good random number generator should be able to have every bit equally random.
The real problem with modulo is visible if your modulo is not a multiple of RAND_MAX.
Let's take RAND_MAX = 100. If you compute (rand () % 30) you get:
0 if you draw 0, 30, 60 or 90,
1 if you draw 1, 31, 61 or 91,
...
11 if you draw 11, 41, 71 or... that's all.
So there is a lower probability to find 11 than 1.
yes, I agree!
But having a big RAND_MAX (like 32000 or more) and drawing a small subset by a small modulo there should be actually no problem.
In adaption of your example, already having RAND_MAX:=9999 and taking a relatively small modulo subset (e.g., modulo 10 or 20 or 30) will lead to a equal distribution although 9999 is not a multiple of 10 or 20 or 30.
If you take a look at my latest uniform_int_ul(), you can see how to avoid the "modulus problem". It may have a few bugs - if you find any, please tell me! (Java's Random.nextInt() returns a signed int type.)
Commit to LEGO Mindstorms Robotics Stack Exchange: bit.ly/MindstormsSE
Commit to LEGO Stack Exchange: bit.ly/Area51LEGOcommit
Seems like modulo 16 is the problem since Random(16) is as good as doc helmut's own much slower code. Random(16) is standard C code. It is just a user-defined function that internally uses rand() and returns a random number between 0 and 15. And it is faster than rand()%16. Use it, for pete's sake.
Random(16) really seems to be better then rand()%16 (I'm curious why)
but rand()%16 is NOT much faster than my own code rand_()%16
(980 loops/sec vs. about 930 loops/sec but having the additional advantage of generating and planting randomization seeds by my own srand(x) ).
By "no ANSI C standard" or so I meant: Random(long x) is no keyword that I found listed in a stdlib.h
- surely it's legal C code as it's a user-defined function.
stdlibs as far as I know are using functions labeled
lrand48(void) (or sth like that)
as keywords, for taking a subset (e.g. 0...15) they use it like
lrand48(void)%16 (or whatever).
(maybe I should rename my rand_() into rand32(void) or irand32(void) because of the same keyword compatibility.)
)