Date: Tue, 31 May 2016 19:58:47 +1000 (EST) From: Bruce Evans <brde@optusnet.com.au> To: Andrey Chernov <ache@freebsd.org> Cc: Bruce Evans <brde@optusnet.com.au>, pfg@freebsd.org, src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: Re: svn commit: r300956 - head/lib/libc/stdlib Message-ID: <20160531185907.Y2047@besplex.bde.org> In-Reply-To: <af15ef04-74f5-6a02-9822-2cacaa7ded1b@freebsd.org> References: <201605291357.u4TDv6No071840@repo.freebsd.org> <20160530110541.I924@besplex.bde.org> <b7074832-ba30-0371-ee8a-a51a19aadea0@freebsd.org> <20160531155327.I1534@besplex.bde.org> <af15ef04-74f5-6a02-9822-2cacaa7ded1b@freebsd.org>
next in thread | previous in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20160531185907.Y2047>