Re: [avr-libc-dev] How attached are people to the implementation of rand()/random()?

[Joerg Wunsch]

As George Spelvin wrote:

> As I'm looking through the rest of the code, I notice a few silly things.
> 
> For example, couldn't rand_r save a jump by declaring it
> 
> int rand_r(unsigned long *ctx) __attribute__((alias("do_rand")));

I don't think that would work, as do_rand() is declared "static", so it
doesn't yield a linker-visible symbol.

> But the real problem is the choice of algorithm.
> 32x32-bit multiplies are very ugly and bloated on an 8-bit AVR.

It's simply been ported from a known-to-be-good algorithm.

> I could replace it with an 8-bit lag-3 multiply-with-carry generator
> with the same period (2^31 - epsilon) and state size (32 bits) which
> would be a lot faster.

If it produces the same good degree of (pseudo-)randomness, this is
certainly another Good Thing.

> But do people depend on that exact sequence of values being generated?

We could always offer a compile-time #ifdef, so people who depend on a
particular order can compile their own.  We did so using the
USE_WEAK_SEEDING #ifdef, but I think that one can finally go away.

As another option, we could include the existing algorithm in the
library (in a separate module), but rename it, say, to
"__park_miller_rand" etc.  Then, we offer (and document) a switch that
allows an application to pick the Park & Miller algorithm by #defining
__PARK_MILLER_RAND before including <stdlib.h>.  Thinking more about
it, I'd prefer it that way.

That is only needed for rand_r() / rand() / srand().  random() and
srandom() are meant to be compatible with the standard, so any version
that complies is fine.

> If they are, there's still room for improvement.  You could at least
> replace the hideous mess of 32-bit divides with a two 16x16->32-bit
> multiplies (since the multiplier 16807 fits into 16 bits) and some
> simpler modular reduction code.

That could still be done nevertheless.  In that case, I suggest to
implement testcase code though, so we can make sure the desired
sequence of pseudo-random numbers is still retained for the Park &
Miller case.  (There is a testbench around in avr-libc, even though
I guess only few developers know about it.)
-- 
cheers, Joerg               .-.-.   --... ...--   -.. .  DL8DTL

http://www.sax.de/~joerg/
Never trust an operating system you don't have sources for. ;-)