home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #23 / NN_1992_23.iso / spool / sci / math / 13226 < prev    next >
Encoding:
Internet Message Format  |  1992-10-15  |  5.7 KB
  1. Xref: sparky sci.math:13226 comp.lang.c:15001 comp.lang.pascal:6003 comp.os.os2.programmer:5672
  2. Path: sparky!uunet!charon.amdahl.com!pacbell.com!iggy.GW.Vitalink.COM!cs.widener.edu!eff!sol.ctr.columbia.edu!caen!batcomputer!munnari.oz.au!manuel.anu.edu.au!sserve!hhcs.gov.au!pihlab
  3. From: pihlab@hhcs.gov.au
  4. Newsgroups: sci.math,comp.lang.c,comp.lang.pascal,comp.os.os2.programmer
  5. Subject: SUMMARY: The SEED - where to start?
  6. Message-ID: <1992Oct15.110203.414@hhcs.gov.au>
  7. Date: 15 Oct 92 11:02:03 +1000
  8. Organization: Aust. Dept. Health, Housing and Community Services
  9. Lines: 127
  10.  
  11.  
  12. A while ago I posted this message:
  13.  
  14. ========================================================================
  15.  
  16.    PLEASE send replies directly to pihlab@hhcs.gov.au
  17.  
  18.    I need an algorithm for determining a unique seed from two known values.
  19.  
  20.    The seed should be repeatable and not based on sampling a clock or such.
  21.  
  22.    I have tried things like J=999  K=777  SEED=concatenation  ie =999777
  23.                       SEED=sum            ie =1776
  24.                       SEED=multiplication ie =776223.
  25.  
  26.    I am then using this seed to start off a random sequence using a pseudo
  27.    random number generator (of the form "(AX+C) MOD M").  Note that I have 
  28.    tried various generators from KNUTH's books and algorithms posted on 
  29.    Internet as well and the problem continues in varying degrees.
  30.  
  31.    The problem is that if I print the first iteration result for each of 
  32.    J=1..N by K=1..N (where N is 100 say) then there are obvious patterns 
  33.    (stripes) in the random numbers produced.
  34.  
  35.    If I cycle the Random Number Generator enough times then the pattern 
  36.    distorts and becomes more "random" but I would like to be able to pick an 
  37.    initial seed as quickly as possible without too much overhead.
  38.  
  39.    The pattern appears to be because the difference between (J,K)=(10,10) 
  40.    and (10,11) or any other close set is always the same value so I end up 
  41.    with this pattern.
  42.  
  43.    What I need is some way of being able to produce a seed which is 
  44.    effectively random itself so that nearly identical starting values of 
  45.    (J,K) won't produce seeds that are close to each other or always a 
  46.    certain distance apart.
  47.  
  48.    Perhaps there is another way of generating pseudo Random Numbers that 
  49.    doesn't have this inherent pattern when seed1 and seed2 are almost equal 
  50.    OR regularly spaced. 
  51.  
  52.    Please help me.
  53.  
  54.    I'm losing my hair on this one and I don't have much left.
  55.  
  56.    Please reply directly to EM address.
  57.  
  58.    Thankyou.
  59.  
  60. ============================================================================
  61.  
  62. I received a number of replies which are presented here in no particular 
  63. order.
  64.  
  65.  
  66. 1)  Try something like Ackerman, that will change value wildly based
  67.     on a small input change.
  68.  
  69. 2)  Try using J as the seed and K as an iteration count?
  70.  
  71. 3)  Try using a function or functions that are not polynomial
  72.     in nature.  Something like the CRC algorithm, where small
  73.      changes in input lead to big output changes.
  74.  
  75. 4)  How about something involving logs or exponents.  like
  76.     J^K+K^J that would provide wide separation or ext(j)+exp(k).
  77.  
  78. 5)  How about taking a number (or several) and rearranging all the
  79.     digits in every order possible (123= 123, 132, 231, 213, etc.)?
  80.     This would give a unique sequence, however the repetition is not
  81.     very smooth.
  82.  
  83. 6)  Another idea would be to take the digits of an indefinately repeating
  84.     number like pi.  Take the digits by ones, twos or threes (314, 159,
  85.     265, etc) this would give an infinite sequence of nunbers, limited
  86.     only by the data you have.
  87.  
  88. 7)  Have you tried floating-point division?  Or a combination, e.g.
  89.     ( J + K ) * J^2 * K^3 - J-concatenated-with-K
  90.  
  91. 8)  How about seeding the generator with your first word, iterating once,
  92.     then seedin with the second one? This is, seed with (AJ+B+K) MOD M.
  93.  
  94. 9)  An `encryption' algorithm is sometimes useful as a seed generator where
  95.     the seed is otherwise visible.  I have also used an encryption routine,
  96.     under certain circumstances, as a truly-portable-independent-of-machine
  97.     -word-size method to generate *short* lists of random numbers.
  98.  
  99. 10) The best thing is to use a cryptographic hash function like MD2, MD4,  
  100.     or MD5. These change an arbitrary character string to a completely  
  101.     unpredictable value (128 bits, but you can simply add the four 32bit  
  102.     parts or just pick one of them). You can get them by anonymous ftp  
  103.     from rsa.com.
  104.  
  105. 11) What about if you try setting the seed to J, getting a random
  106.     number, set the seed to K, get another random number, sum those two
  107.     random numbers and use that as the seed?
  108.  
  109. ======================================================================
  110.  
  111.  
  112. From all the above information I chose to implement a simple but fast CRC
  113. algorithm.  I found several in the TURBOPAS directory under SIMTEL-20
  114. as well as the C routines of MD2, MD4, and MD5 at rsa.com and I'm sure there 
  115. are other samples floating around in SIMTEL-20 but I've got what I need.
  116.  
  117. Rather than convert the X & Y values to text strings I simply concatenate
  118. the X & Y integers (2 bytes each) into a string X||Y||Y||X||Y||X||X||Y and 
  119. then apply the CRC algorithm to this string of bytes.
  120.  
  121. I've run some tests and the distribution is good and it works fine now.
  122.  
  123.  
  124. Thankyou to all who replied, I do appreciate the help provided.
  125.  
  126.  
  127. -- 
  128.  
  129. Bruce...        pihlab@hhcs.gov.au
  130.                  ^^
  131. *******************************************************************
  132. * Bruce Pihlamae  --  Database Administration                     *
  133. * Commonwealth Department of Health, Housing & Community Services *
  134. * Canberra, Australia                             (W) 06-289-7056 *
  135. *******************************************************************
  136. * These are my own thoughts and opinions, few that I have.        *
  137. *******************************************************************
  138.