25,161
edits
Changes
Created page with "'''Home * People * Bob Jenkins''' FILE:bob_jenkins_portrait.jpg|border|right|thumb|link=http://burtleburtle.net/bob/|160px| Bob Jenkins <ref>[http://burtl..."
'''[[Main Page|Home]] * [[People]] * Bob Jenkins'''
[[FILE:bob_jenkins_portrait.jpg|border|right|thumb|link=http://burtleburtle.net/bob/|160px| Bob Jenkins <ref>[http://burtleburtle.net/bob/ Bob Jenkins' Web Site]</ref> ]]
'''Robert John Jenkins Jr.''',<br/>
an American computer scientist, software developer, M.Sc. in CS from [[Carnegie Mellon University]], and [[Microsoft]] and former [https://en.wikipedia.org/wiki/Oracle_Corporation Oracle] employee. At Microsoft, he worked in the ''Cosmos'' team <ref>[http://www.goland.org/whatiscosmos/ Stuff Yaron Finds Interesting - What is Microsoft's Cosmos service?]</ref> , and under [[Andrew Kadatch]] on the ''Cosmos'' storage distributed [https://en.wikipedia.org/wiki/File_system file system] <ref>[http://research.microsoft.com/en-us/projects/dryad/ Dryad - Microsoft Research]</ref> , written by Andrew in [[Cpp|C++]], and on the ''Scope'' query language <ref>[http://www.linkedin.com/pub/ronnie-chaiken/26/571/143 Ronnie Chaiken], [[Bob Jenkins]], [http://research.microsoft.com/en-us/people/palarson/ Per-Åke Larson], [http://portal.acm.org/author_page.cfm?id=81344496896&coll=DL&dl=ACM&trk=0&cfid=28619666&cftoken=49088236 Bill Ramsey], [http://www.microsoft.com/presspass/exec/de/Shakib/default.mspx Darren Shakib], [http://www.linkedin.com/in/simonjweaver Simon Weaver], [http://research.microsoft.com/en-us/um/people/jrzhou/ Jingren Zhou] ('''2008'''). ''[http://portal.acm.org/citation.cfm?id=1454166 SCOPE: Easy and Efficient Parallel Processing of Massive Data Sets]''. [[Microsoft|Microsoft Corporation]], [http://www.goland.org/Scope-VLDB-final.pdf pdf]</ref> . He was Oracle's resident expert on [https://en.wikipedia.org/wiki/Hash_function hash functions] <ref>[http://burtleburtle.net/bob/other/resume3.html Resume for Bob Jenkins]</ref> , and he designed and published various [[Pseudorandom Number Generator|pseudorandom number generators]] and hash functions for [[Hash Table|hash table lookup]] <ref>[http://burtleburtle.net/bob/hash/evahash.html Hash Functions for Hash Table Lookup], Robert J. Jenkins Jr., 1995-1997</ref> , competing with [[Paul Hsieh]] <ref>[http://www.azillionmonkeys.com/qed/hash.html Hash functions] by [[Paul Hsieh]]</ref> .
=RKISS=
<span id="RKISS"></span>Bob Jenkins' small noncryptographic PRNG approach is suited for [[Zobrist Hashing]]. [[Heinz van Saanen|Heinz van Saanen's]] RKISS as used in [[Stockfish]] since version 2.0 <ref>[http://blog.stockfishchess.com/ Stockfish Blog - Stockfish 2.0]</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=37406 RKISS] by [[Gerd Isenberg]], [[CCC]], January 01, 2011</ref> uses almost the same code despite embedded it into a C++ class and initialization <ref>[http://www.talkchess.com/forum/viewtopic.php?start=0&t=38313 RKISS copyright?] by Giorgio Medeot, [[CCC]], March 07, 2011</ref>. 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 [[Mathematician#GMarsaglia|George Marsaglia]] as inventor of the RNG-Kiss-family <ref>[http://compgroups.net/comp.lang.fortran/64-bit-kiss-rngs/601519 64-bit KISS RNGs] by [[Mathematician#GMarsaglia|George Marsaglia]], [http://compgroups.net/comp.lang.fortran/ comp.lang.fortran | Computer Group], February 28, 2009</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=398196&t=38313 Re: RKISS copyright?] by [[Marco Costalba]], [[CCC]], March 09, 2011</ref> <ref>[http://www.random.org/integers/?mode=advanced RANDOM.ORG - Integer Generator]</ref> <ref>[http://www.stat.fsu.edu/pub/diehard/ The Marsaglia Random Number CDROM including the Diehard Battery of Tests]</ref>. This is Bob's 64 bit code <ref>[http://www.burtleburtle.net/bob/rand/smallprng.html A small noncryptographic pseudorandom number generator - 64-bit variants] by [[Bob Jenkins]]</ref>:
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 [https://en.wikipedia.org/wiki/Avalanche_effect 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.
<pre>
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);
}
}
</pre>
=Selected Publications=
* [[Bob Jenkins]] ('''1997'''). ''Hash functions''. [https://en.wikipedia.org/wiki/Dr._Dobb%27s_Journal Dr. Dobb's Journal], September 1997
* Ronnie Chaiken, [[Bob Jenkins]], Per-Åke Larson, Bill Ramsey, Darren Shakib, Simon Weaver, Jingren Zhou ('''2008'''). ''[https://dl.acm.org/citation.cfm?id=1454166 SCOPE: Easy and Efficient Parallel Processing of Massive Data Sets]''. [[Microsoft|Microsoft Corporation]], [https://www.goland.org/Scope-VLDB-final.pdf pdf]
* [[Andrew Kadatch]], [[Bob Jenkins]] ('''2010'''). ''[https://www.researchgate.net/publication/268184499_Everything_we_know_about_CRC_but_afraid_to_forget Everything we know about CRC but afraid to forget]''. <ref>[https://en.wikipedia.org/wiki/Cyclic_redundancy_check Cyclic redundancy check from Wikipedia]</ref> <ref>[https://en.wikipedia.org/wiki/Mathematics_of_CRC Mathematics of CRC from Wikipedia]</ref>
=External Links=
* [https://en.wikipedia.org/wiki/Robert_John_Jenkins_Junior Robert John Jenkins Junior from Wikipedia]
* [http://burtleburtle.net/bob/ Bob Jenkins' Web Site]
* [http://burtleburtle.net/bob/rand/index.html Random Number Results]
* [http://burtleburtle.net/bob/hash/index.html Hash Functions and Block Ciphers]
* [http://burtleburtle.net/bob/hash/doobs.html A Hash Function for Hash Table Lookup] updated [https://en.wikipedia.org/wiki/Dr._Dobb%27s_Journal Dr. Dobb's] article
* [http://burtleburtle.net/bob/hash/perfect.html Perfect Hashing]
* [https://en.wikipedia.org/wiki/Jenkins_hash_function Jenkins hash function from Wikipedia]
=References=
<references />
'''[[People|Up one level]]'''
[[Category:Programmer|Jenkins]]
[[FILE:bob_jenkins_portrait.jpg|border|right|thumb|link=http://burtleburtle.net/bob/|160px| Bob Jenkins <ref>[http://burtleburtle.net/bob/ Bob Jenkins' Web Site]</ref> ]]
'''Robert John Jenkins Jr.''',<br/>
an American computer scientist, software developer, M.Sc. in CS from [[Carnegie Mellon University]], and [[Microsoft]] and former [https://en.wikipedia.org/wiki/Oracle_Corporation Oracle] employee. At Microsoft, he worked in the ''Cosmos'' team <ref>[http://www.goland.org/whatiscosmos/ Stuff Yaron Finds Interesting - What is Microsoft's Cosmos service?]</ref> , and under [[Andrew Kadatch]] on the ''Cosmos'' storage distributed [https://en.wikipedia.org/wiki/File_system file system] <ref>[http://research.microsoft.com/en-us/projects/dryad/ Dryad - Microsoft Research]</ref> , written by Andrew in [[Cpp|C++]], and on the ''Scope'' query language <ref>[http://www.linkedin.com/pub/ronnie-chaiken/26/571/143 Ronnie Chaiken], [[Bob Jenkins]], [http://research.microsoft.com/en-us/people/palarson/ Per-Åke Larson], [http://portal.acm.org/author_page.cfm?id=81344496896&coll=DL&dl=ACM&trk=0&cfid=28619666&cftoken=49088236 Bill Ramsey], [http://www.microsoft.com/presspass/exec/de/Shakib/default.mspx Darren Shakib], [http://www.linkedin.com/in/simonjweaver Simon Weaver], [http://research.microsoft.com/en-us/um/people/jrzhou/ Jingren Zhou] ('''2008'''). ''[http://portal.acm.org/citation.cfm?id=1454166 SCOPE: Easy and Efficient Parallel Processing of Massive Data Sets]''. [[Microsoft|Microsoft Corporation]], [http://www.goland.org/Scope-VLDB-final.pdf pdf]</ref> . He was Oracle's resident expert on [https://en.wikipedia.org/wiki/Hash_function hash functions] <ref>[http://burtleburtle.net/bob/other/resume3.html Resume for Bob Jenkins]</ref> , and he designed and published various [[Pseudorandom Number Generator|pseudorandom number generators]] and hash functions for [[Hash Table|hash table lookup]] <ref>[http://burtleburtle.net/bob/hash/evahash.html Hash Functions for Hash Table Lookup], Robert J. Jenkins Jr., 1995-1997</ref> , competing with [[Paul Hsieh]] <ref>[http://www.azillionmonkeys.com/qed/hash.html Hash functions] by [[Paul Hsieh]]</ref> .
=RKISS=
<span id="RKISS"></span>Bob Jenkins' small noncryptographic PRNG approach is suited for [[Zobrist Hashing]]. [[Heinz van Saanen|Heinz van Saanen's]] RKISS as used in [[Stockfish]] since version 2.0 <ref>[http://blog.stockfishchess.com/ Stockfish Blog - Stockfish 2.0]</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=37406 RKISS] by [[Gerd Isenberg]], [[CCC]], January 01, 2011</ref> uses almost the same code despite embedded it into a C++ class and initialization <ref>[http://www.talkchess.com/forum/viewtopic.php?start=0&t=38313 RKISS copyright?] by Giorgio Medeot, [[CCC]], March 07, 2011</ref>. 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 [[Mathematician#GMarsaglia|George Marsaglia]] as inventor of the RNG-Kiss-family <ref>[http://compgroups.net/comp.lang.fortran/64-bit-kiss-rngs/601519 64-bit KISS RNGs] by [[Mathematician#GMarsaglia|George Marsaglia]], [http://compgroups.net/comp.lang.fortran/ comp.lang.fortran | Computer Group], February 28, 2009</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=398196&t=38313 Re: RKISS copyright?] by [[Marco Costalba]], [[CCC]], March 09, 2011</ref> <ref>[http://www.random.org/integers/?mode=advanced RANDOM.ORG - Integer Generator]</ref> <ref>[http://www.stat.fsu.edu/pub/diehard/ The Marsaglia Random Number CDROM including the Diehard Battery of Tests]</ref>. This is Bob's 64 bit code <ref>[http://www.burtleburtle.net/bob/rand/smallprng.html A small noncryptographic pseudorandom number generator - 64-bit variants] by [[Bob Jenkins]]</ref>:
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 [https://en.wikipedia.org/wiki/Avalanche_effect 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.
<pre>
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);
}
}
</pre>
=Selected Publications=
* [[Bob Jenkins]] ('''1997'''). ''Hash functions''. [https://en.wikipedia.org/wiki/Dr._Dobb%27s_Journal Dr. Dobb's Journal], September 1997
* Ronnie Chaiken, [[Bob Jenkins]], Per-Åke Larson, Bill Ramsey, Darren Shakib, Simon Weaver, Jingren Zhou ('''2008'''). ''[https://dl.acm.org/citation.cfm?id=1454166 SCOPE: Easy and Efficient Parallel Processing of Massive Data Sets]''. [[Microsoft|Microsoft Corporation]], [https://www.goland.org/Scope-VLDB-final.pdf pdf]
* [[Andrew Kadatch]], [[Bob Jenkins]] ('''2010'''). ''[https://www.researchgate.net/publication/268184499_Everything_we_know_about_CRC_but_afraid_to_forget Everything we know about CRC but afraid to forget]''. <ref>[https://en.wikipedia.org/wiki/Cyclic_redundancy_check Cyclic redundancy check from Wikipedia]</ref> <ref>[https://en.wikipedia.org/wiki/Mathematics_of_CRC Mathematics of CRC from Wikipedia]</ref>
=External Links=
* [https://en.wikipedia.org/wiki/Robert_John_Jenkins_Junior Robert John Jenkins Junior from Wikipedia]
* [http://burtleburtle.net/bob/ Bob Jenkins' Web Site]
* [http://burtleburtle.net/bob/rand/index.html Random Number Results]
* [http://burtleburtle.net/bob/hash/index.html Hash Functions and Block Ciphers]
* [http://burtleburtle.net/bob/hash/doobs.html A Hash Function for Hash Table Lookup] updated [https://en.wikipedia.org/wiki/Dr._Dobb%27s_Journal Dr. Dobb's] article
* [http://burtleburtle.net/bob/hash/perfect.html Perfect Hashing]
* [https://en.wikipedia.org/wiki/Jenkins_hash_function Jenkins hash function from Wikipedia]
=References=
<references />
'''[[People|Up one level]]'''
[[Category:Programmer|Jenkins]]
