🚀 go-pugleaf

mister massey's email is subject to rubberizing...

While talking to sis-a:
>>> RCPT To:<EIreland@sis-a>
<<< 550 <EIreland@sis-a>... User unknown
550 <E.Ireland@massey.ac.nz>... User unknown


but it seems that this might be of more general interest anyway,



   Date: Fri, 24 May 91 13:37:51 NZS
   From: E.Ireland%massey.ac.nz
   References: <1991May23.134621@axion.bt.co.uk>
   Organization: School of Maths and Info. Sci., Massey University, NZ

   In article <TED.91May23130637@kythera.nmsu.edu> you write:
   >in general, a much more robust generator can be constructed by using
   >an additive feedback in which an short queue of integers is kept.  new
   >...
   >lowest order bits, and you have better characteristics for the higher
   >order bits.

   If you use only (unbounded) integer arithmetic, make sure you don't
   seed the generator with a zero, and extract the numbers as with the
   `random' function in my posting (which effectively results in using
   the higher order bits only, unless the range [x..y] is huge), what
   loss of robustness will result?

depending on the exact characteristics of the floating point
arithmetic you are using, the sequence you get will vary from machine
to machine.  

secondly, it is very difficult to characterize the length of such a
method since it again depends on the details of f.p. arithmetic.
thus, you have no guarantees.

thirdly, assuming that the system you propose actually does act like
the integer linear congruential system it resembles, chances are that
it will not pass the spectral test.  very few linear congruential
generators will pass such a test, and all the ones that i know have
more significant digits in the constant multiplier.

   >the recent cacm article (a proposed standard random number generator
   >or some such) was absolute drivel and should not be relied on.  knuth
   >is a good source, although he only touches on additive feedback
   >systems.

   Can you please elaborate on this?
   What is unreliable about the
   proposed `minimal standard' generator?

they propose the standard use of a linear congruential generator which
was shown in knuth to be distinctly sub-optimal.  this is absolutely
crazy since there are so many good generators of that form that are
known.  it is even crazier when other forms of generators are also
known to produce good results.

   Do you have references to work
   which does more than `touch' on additive feedback systems?

knuth mentions several and gives some encouraging words.  in spite of
the fact that this generator has passed innumerable tests and is known
(modulo one likely conjecture) to have good multi-dimensional
characteristics and is likely faster than most others, the lack of a
strong underlying theory keeps some people from whole hearted
endorsement.

another basic reference would have to be the berkeley source code for
random (which may well be part of the liberated berkeley code).

   Thanks for any help that you can give.  I am most interested in
   generators that use unbounded integer arithmetic (if necessary),
   perferably not too much bit-twiddling (or none), and have very large
   cycles.

additive feedback systems do not require unbound integer arithmetic.
in fact, they will produce as many good bits as you can effectively
use, although there will be a serious improvement in speed if you stay
inside the bounds of machine arithmetic.  the cycle length for the lsb
of the most common generator of this sort is 2^54-1.  for n bit words,
the cycle length is at least 2^f * (2^54-1) larger than this where 
0 < f <= n.

if you change to subtractive feedback, then you can perform all
necessary arithmetic using floating point numbers in [0,1).  also, on
some machines, subtracting and testing may be slightly faster than
adding and testing (both discussed in knuth).
--
	Offer void except where prohibited by law.