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

[George Spelvin]

(This is a much lower priority than the printf work; I just noticed it
in passing.)

>> 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.

I don't think that's a problem.  The assembly generated is basically:

        .type   do_rand, @function
do_rand:
        <code>
        .size   do_rand, .-do_rand
.global rand_r
        .set    rand_r,do_rand

The assembler is generating two symbols that happen to have the same
value, and one is exported while the other is not.

The important thing is that the linker knows that the reference in rand()
is to the non-exported symbol, so even if someone overrides rand_r,
rand() will still call do_rand().


(Speaking of the linker, I wish it could relax conditional branches.
It has all the information it needs in the R_AVR_7_PCREL relocation
table entry.  Just flip bit 10 of the opcode to negate the sense of the
branch and append an RJMP or JMP to the destination.)


>> 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.

Actually, that's something of a known-to-be-bad algorithm, but yeah,
it's okay as LCRNGs go.  You might note that, per

https://en.wikipedia.org/wiki/Park%E2%80%93Miller_RNG#Parameters_in_common_use
http://www.firstpr.com.au/dsp/rand31/p105-crawford.pdf

Park and Miller suggested changing the multiplier to 48271.

These are available in the C++ library as:
http://www.cplusplus.com/reference/random/minstd_rand0/
http://www.cplusplus.com/reference/random/minstd_rand/

>> 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.

Obviously, any generator with a 32-bit state is limited in the period
it can generate, but there are plenty of decent ones.  I was just
trying to keep the math simple.

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

> 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.

Okay, that sounds simple enough.  

>> 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.)

A README in test/simulate would definitely help.  Based on my
quick glance at things:

"The tests are all compiled and simulated by runtest.sh.  Each *.c
file is compiled and simulated on several representative models of AVR.
The simulator halts when exit() is called, and the 16-bit return value
is extracted from the register file in the core dump.

"If the exit code is non-zero, the test has failed.  Usually the exit code
is the line number where the failing test was called.

"You may add new files to the existing test directories freely, but adding
a new directory requires updating the list in runtest.sh."


However, I can't get it to work.  For me, it generates a near-infinite
stream of errors:

Simulate: time/aux.c atmega128 ... avr-gcc: error: 
../../avr/lib/avr51/atmega128/libatmega128.a: No such file or directory
*** compile failed
Simulate: time/declination.c atmega128 ... avr-gcc: error: 
../../avr/lib/avr51/atmega128/libatmega128.a: No such file or directory
*** compile failed
Simulate: time/equation.c atmega128 ... avr-gcc: error: 
../../avr/lib/avr51/atmega128/libatmega128.a: No such file or directory
*** compile failed

...etc.  
[921]$ ls -l  ../../avr/lib/avr51/atmega128/
total 108
-rw-rw-r-- 1 colin software 30385 Dec  5 20:12 Makefile
-rw-rw-r-- 1 colin software  3434 Dec  5 20:00 Makefile.am
-rw-rw-r-- 1 colin software 33194 Dec  5 20:01 Makefile.in
-rw-rw-r-- 2 colin software  8884 Dec  5 20:14 crtm128.o
-rw-rw-r-- 2 colin software  8884 Dec  5 20:14 gcrt1.o
-rw-rw-r-- 1 colin software  9672 Dec  5 20:14 libcrt.a

I can't find a "libatmega128.a" anywhere. :-(