[haiku-development] Re: Scheduler and _rand()
- From: "Axel Dörfler" <axeld@xxxxxxxxxxxxxxxx>
- To: haiku-development@xxxxxxxxxxxxx
- Date: Sat, 22 May 2010 19:22:06 +0200
Varga Endre Sándor <vendre@xxxxxxxxxx> wrote:
> I am Endre Varga from the Technical University of Budapest, and I am
> new
> to Haiku development.
Be welcome Endre!
> This is a standard textbook PRNG (truncated to 15 bits), but I think
> this
> is not the appropriate one to use here. I would recommend to use a
> simple
> LFSR (a Galois LFSR to be pedantic):
>
> lfsr = (lfsr >> 1) ^ (-(lfsr & 1u) & 0x6000u); //0x6000
> corresponds to
> the polynomial x^15 + x^14 + 1 (after shifted by one)
>
> This produces all 15 bit binary numbers (except 0) periodically in a
> "random" order. I think this approach is better, because:
>
> - No multiplication -- only bitwise operations
> - No need for seeding or reseeding
> - It is guaranteed to be "fair", because it is periodic
I haven't investigated that issue at all yet, but your reasons are
sound.
Do you want to prepare a patch? :-)
> It has however the property that it does not generate 0 -- I do not
> think
> it is a problem, however
Indeed it wouldn't.
Bye,
Axel.
Other related posts:
