Home * People * Bob Jenkins

		Robert John Jenkins Jr., an American software developer, M.Sc. in computer science from Carnegie Mellon University, Microsoft and former Oracle employee. At Microsoft, he worked in the Cosmos team [1] , and under Andrew Kadatch on the Cosmos storage distributed file system [2] , written by Andrew in C++, and on the Scope query language [3] . He was Oracle's resident expert on hash functions [4] , and he designed and published various pseudorandom number generators and hash functions for hash table lookup [5] , competing with Paul Hsieh [6] .
Bob Jenkins [7]

RKISS

Bob Jenkins' small noncryptographic PRNG approach is suited for Zobrist Hashing. Heinz van Saanen's RKISS as used in Stockfish since version 2.0 ^{[8] [9]} uses almost the same code despite embedded it into a C++ class and initialization ^[10]. Van Saanen admitted he took an obviously free and quite raw C-snippet from a random-related newsgroup long time ago. When turned this to a functional C++-class years later he could not find the initial source any longer, and gave credit to George Marsaglia as inventor of the RNG-Kiss-family ^{[11] [12] [13] [14]}. This is Bob's 64 bit code ^[15]:

If you want to use 8-byte terms instead of 4-byte terms, the proper rotate amounts are (39,11) for the two-rotate version (yielding at least 13.3 bits of avalanche after 5 rounds) or (7,13,37) for the three-rotate version (yielding 18.4 bits of avalanche after 5 rounds). I think I'd got with the three-rotate version, because the ideal is 32 bits of avalanche, and 13.3 isn't even half of that.

typedef unsigned long long u8;
typedef struct ranctx { u8 a; u8 b; u8 c; u8 d; } ranctx;
 
#define rot(x,k) (((x)<<(k))|((x)>>(64-(k))))
u8 ranval( ranctx *x ) {
    u8 e = x->a - rot(x->b, 7);
    x->a = x->b ^ rot(x->c, 13);
    x->b = x->c + rot(x->d, 37);
    x->c = x->d + e;
    x->d = e + x->a;
    return x->d;
}
 
void raninit( ranctx *x, u8 seed ) {
    u8 i;
    x->a = 0xf1ea5eed, x->b = x->c = x->d = seed;
    for (i=0; i<20; ++i) {
        (void)ranval(x);
    }
}

Selected Publications

• Bob Jenkins (1997). Hash functions. Dr. Dobb's Journal, September 1997
• Ronnie Chaiken, Bob Jenkins, Per-Åke Larson, Bill Ramsey, Darren Shakib, Simon Weaver, Jingren Zhou (2008). SCOPE: Easy and Efficient Parallel Processing of Massive Data Sets. Microsoft Corporation, pdf
• Andrew Kadatch, Bob Jenkins (2010). Everything we know about CRC but afraid to forget. ^{[16] [17]}

External Links

• Robert John Jenkins Junior from Wikipedia
• Bob Jenkins' Web Site
• Random Number Results
• Hash Functions and Block Ciphers
• A Hash Function for Hash Table Lookup updated Dr. Dobb's article
• Jenkins hash function from Wikipedia
• Perfect Hashing

References

1. ^ Stuff Yaron Finds Interesting - What is Microsoft's Cosmos service?
2. ^ Dryad - Microsoft Research
3. ^ Ronnie Chaiken, Bob Jenkins, Per-Åke Larson, Bill Ramsey, Darren Shakib, Simon Weaver, Jingren Zhou (2008). SCOPE: Easy and Efficient Parallel Processing of Massive Data Sets. Microsoft Corporation, pdf
4. ^ Resume for Bob Jenkins
5. ^ Hash Functions for Hash Table Lookup, Robert J. Jenkins Jr., 1995-1997
6. ^ Hash functions by Paul Hsieh
7. ^ Resume for Bob Jenkins
8. ^ Stockfish Blog - Stockfish 2.0
9. ^ RKISS by Gerd Isenberg, CCC, January 01, 2011
10. ^ RKISS copyright? by Giorgio Medeot, CCC, March 07, 2011
11. ^ 64-bit KISS RNGs by George Marsaglia, comp.lang.fortran | Computer Group, February 28, 2009
12. ^ Re: RKISS copyright? by Marco Costalba, CCC, March 09, 2011
13. ^ RANDOM.ORG - Integer Generator
14. ^ The Marsaglia Random Number CDROM including the Diehard Battery of Tests
15. ^ A small noncryptographic pseudorandom number generator - 64-bit variants by Bob Jenkins
16. ^ Cyclic redundancy check from Wikipedia
17. ^ Mathematics of CRC from Wikipedia

What links here?

Up one level