Author: Vincent Diepeveen
Date: 18:35:59 10/28/03
Go up one level in this thread
On October 28, 2003 at 15:02:02, Dieter Buerssner wrote: >On October 28, 2003 at 14:50:35, Martin Schreiber wrote: > >>For my hash tables I need 64 bit random numbers, but I don't know the source >>code. >>I use Dev-C++. > >Use a 32-bit pseudo random number generator, and paste 2 numbers together. In general this goes wrong, so you shouldn't give this tip to him Dieter! If generalize over the average 32 bits PRNG and generate 64 bits hash numbers with it like this, then you end up with multilineair connection and many collissions. Now i'm sure you will show up with something that doesn't have multilineair connection, but that's not what i call the 'average' 32 bits RNG :) Note that i'm still interested in a statistical analysis of how big the chance is that a collission occurs when i search at quite a big speed at world champs with 250GB hashtable. No model i ever saw matched my collission detection. Also measuring collissions at that speed is going to get kind of hard without adding some kind of locking to hashtable for verification. >For example a short one suggested by Marsaglia (it may be not the best, but most >probably much better than most Std-C rand()): >static unsigned long zseed = 0x12345678UL; >static unsigned long wseed = 0x87654321UL; > >/* Combine 2 Multiply with carry PRNGs, returns 0 < r < 2**32 > Should work correctly on any Standard-C platform independent of the > width of type unsigned long */ > >unsigned long mwc1616(void) >{ > unsigned long t = zseed; > zseed=30903*(t&0xffff)+(t>>16); > t = wseed; > wseed=18000*(t&0xffff)+(t>>16); > return ((wseed<<16)&0xffffffffUL) + (zseed&0xffff); >} > >/* Paste together 2 numbers to get a 64 bit random number */ >my_u64bit_t r64(void) >{ > my_u64bit_t r; > r = mwc1616(); > return (r<<32) | mwc1616(); >} > >To "seed" the above PRNG, change wseed and/or zseed. They should not be both >zero. > >You cold also paste together Standard rand() returns - but I would not suggest >to do it (also not without traps, to do it rigth). > >Regards, >Dieter
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.