On Tue, 31 May 2016, Andrey Chernov wrote:
On 31.05.2016 9:48, Bruce Evans wrote:
Perhaps you can find some ideas, answers and PRNG comparison in the
original paper:
http://www.firstpr.com.au/dsp/rand31/p1192-park.pdf
The ones with Mersenne primes and tweaked Mersenne primes in the reference
(lanl?) given by pfg@ seem OK.
It should be again correctly implemented to not overflow 64bit (as any
other 64bit generator too).
Moreover, it have visible patterns in the low order bits. This one from
the same site is better
http://nuclear.llnl.gov/CNP/rng/rngman/node7.html
but still have some pattern too and 61-bit. Next one does not suffer
from the pattern at all
http://nuclear.llnl.gov/CNP/rng/rngman/node8.html
but is 2^64-2^10+1.
That's the tweaked Mersenne prime one.
Surely there is a pattern in the bits for all of these, and the better
ones just hide the pattern better from normal uses and tests?
Isn't it well known that the lower bits have more patterns so shouldn't
be used? This depends on whether the implementation exposes all its
bits. Since the rand() specification and FreeBSD man pages don't say
anything about this, it is a bug in the implementation to expose all
its bits. The implementation is handicapped by using only 32 bits
internally but wanting RAND_MAX to be almost 32 bits.
You can download SPRNG library implementing all of them here:
http://www.sprng.org/RNG/
For me it is overcomplicated.
The general case is certainly too complicated. It would let the user
specify all the parameters for the LCG and generate optimal code for
the choice on the fly. Maybe also change the parameters with the seed.
But even most implementors don't know how to choose the parameters.
That's just for the not so good LCG family of RNGs.
clang -O uses single "idivl" calculating both quotient and reminder for
current code, but for ldiv(3) case call/storage/additional calcs
overhead will be added. ldiv(3) does not reduce anything, see
stdlib/ldiv.c
The extern functions give lots of overhead. Sometimes they get replaced
automatically by builtins, so it is unclear when the extern functions are
actually used. ldiv.c compiles to idivl for the division part but has
lots of extras for the fixups. The fixups do nothing except waste time
on most hardware/cstd combinations. IIRC, C99 requires direct division
to have the same poor rounding rules as idiv(), so idiv() is not really
needed in C99 and the fixups in it are negatively needed. The builtins
know what is needed so they don't do the fixups in the usual case that
the hardware follows the poor rounding rules.
We don't have ldiv() builtin in any cae.
Apparently integer division is too fundamental to be a builtin.
strings -a `which clang` | grep builtin.*div on amd64 gives 47 builtins
for division, but none seem to be for integer division. gcc-3.3 has
just 4, all for SSE FP division.
For fixups, see full
explanation in the comment of stdlib/div.c
That was what I was complaining about. div.c is for C90 (misspelled
"ANSI"). div.c hasn't caught up with C99. C99 broke this by changing
the rules for integer division to disallow correct rounding for and
require consistently incorrect rounding. Correct rounding for a
positive divisor is towards minus infinity so that the remainder is
not negative. This is modulo arithmetic and has good algebraic
properties. C99 requires rounding minus infinity, at least for positive
divisors, under the extension "reliable integer division". In C90,
the rounding is implementation- defined, so it may be correct, but it
is "unreliable" since it can be anything.
In C90, div() is specified as giving "reliable" division, and that is
what the fixups implement. This now wastes time to change nothing.
If the hardware does correct rounding, then the compiler already
had to do the fixup and id should have produced good MD code for this.
The C code then adds not so good MI code.
Bruce
_______________________________________________
svn-src-all@freebsd.org mailing list
https://lists.freebsd.org/mailman/listinfo/svn-src-all
To unsubscribe, send any mail to "svn-src-all-unsubscr...@freebsd.org"
