From: pihlab@hhcs.gov.au
Newsgroups: sci.math,comp.lang.c,comp.lang.pascal,comp.os.os2.programmer
Subject: SUMMARY: The SEED - where to start?
Date: 15 Oct 92 11:02:03 +1000
Organization: Aust. Dept. Health, Housing and Community Services


A while ago I posted this message:

========================================================================

   PLEASE send replies directly to pihlab@hhcs.gov.au

   I need an algorithm for determining a unique seed from two known values.

   The seed should be repeatable and not based on sampling a clock or such.

   I have tried things like J=999  K=777  SEED=concatenation  ie =999777
					  SEED=sum            ie =1776
					  SEED=multiplication ie =776223.

   I am then using this seed to start off a random sequence using a pseudo
   random number generator (of the form "(AX+C) MOD M").  Note that I have 
   tried various generators from KNUTH's books and algorithms posted on 
   Internet as well and the problem continues in varying degrees.

   The problem is that if I print the first iteration result for each of 
   J=1..N by K=1..N (where N is 100 say) then there are obvious patterns 
   (stripes) in the random numbers produced.

   If I cycle the Random Number Generator enough times then the pattern 
   distorts and becomes more "random" but I would like to be able to pick an 
   initial seed as quickly as possible without too much overhead.

   The pattern appears to be because the difference between (J,K)=(10,10) 
   and (10,11) or any other close set is always the same value so I end up 
   with this pattern.

   What I need is some way of being able to produce a seed which is 
   effectively random itself so that nearly identical starting values of 
   (J,K) won't produce seeds that are close to each other or always a 
   certain distance apart.

   Perhaps there is another way of generating pseudo Random Numbers that 
   doesn't have this inherent pattern when seed1 and seed2 are almost equal 
   OR regularly spaced. 

   Please help me.

   I'm losing my hair on this one and I don't have much left.

   Please reply directly to EM address.

   Thankyou.

============================================================================

I received a number of replies which are presented here in no particular 
order.


1)  Try something like Ackerman, that will change value wildly based
    on a small input change.

2)  Try using J as the seed and K as an iteration count?

3)  Try using a function or functions that are not polynomial
    in nature.  Something like the CRC algorithm, where small
     changes in input lead to big output changes.

4)  How about something involving logs or exponents.  like
    J^K+K^J that would provide wide separation or ext(j)+exp(k).

5)  How about taking a number (or several) and rearranging all the
    digits in every order possible (123= 123, 132, 231, 213, etc.)?
    This would give a unique sequence, however the repetition is not
    very smooth.

6)  Another idea would be to take the digits of an indefinately repeating
    number like pi.  Take the digits by ones, twos or threes (314, 159,
    265, etc) this would give an infinite sequence of nunbers, limited
    only by the data you have.

7)  Have you tried floating-point division?  Or a combination, e.g.
	( J + K ) * J^2 * K^3 - J-concatenated-with-K

8)  How about seeding the generator with your first word, iterating once,
    then seedin with the second one? This is, seed with (AJ+B+K) MOD M.

9)  An `encryption' algorithm is sometimes useful as a seed generator where
    the seed is otherwise visible.  I have also used an encryption routine,
    under certain circumstances, as a truly-portable-independent-of-machine
    -word-size method to generate *short* lists of random numbers.

10) The best thing is to use a cryptographic hash function like MD2, MD4,  
    or MD5. These change an arbitrary character string to a completely  
    unpredictable value (128 bits, but you can simply add the four 32bit  
    parts or just pick one of them). You can get them by anonymous ftp  
    from rsa.com.

11) What about if you try setting the seed to J, getting a random
    number, set the seed to K, get another random number, sum those two
    random numbers and use that as the seed?

======================================================================


From all the above information I chose to implement a simple but fast CRC
algorithm.  I found several in the TURBOPAS directory under SIMTEL-20
as well as the C routines of MD2, MD4, and MD5 at rsa.com and I'm sure there 
are other samples floating around in SIMTEL-20 but I've got what I need.

Rather than convert the X & Y values to text strings I simply concatenate
the X & Y integers (2 bytes each) into a string X||Y||Y||X||Y||X||X||Y and 
then apply the CRC algorithm to this string of bytes.
 
I've run some tests and the distribution is good and it works fine now.


Thankyou to all who replied, I do appreciate the help provided.


-- 

Bruce...        pihlab@hhcs.gov.au
                 ^^
*******************************************************************
* Bruce Pihlamae  --  Database Administration                     *
* Commonwealth Department of Health, Housing & Community Services *
* Canberra, Australia                             (W) 06-289-7056 *
*******************************************************************
* These are my own thoughts and opinions, few that I have.        *
*******************************************************************