Bob Jenkins' Web Site
What's the bottleneck for in-memory sorting? Is it fetching distant memory, or branch delays, or what?
Fetching distant memory could be minimized by having 1000 or so splitters and doing binary search between them.
Branch delays, maybe you could interleave two or four independent mergesorts. A rough experiment said that
fetching memory isn't it: sorting 2^^20 sequences of 2^^10 numbers takes half as long as sorting 2^^10 sequences
of 2^^20 numbers, which takes takes 2/3 as long as sorting 1 sequence of 2^^30 numbers. Only those longer
sequences get many cache misses, but each of the 30 passes seems to take about equally long.
Table of Contents (internal links):
- Here's a hash table, code for perfect hashing, a good hash function for hash table lookup,
a FAQ, some theory, and code to search for new hash functions. I tried designing block ciphers and finding characteristics. I had an article published in Dr. Dobb's in September 1997.
Have the cryptographic pseudorandom number
generator ISAAC, a small noncryptographic pseudorandom number generator, a prize for breaking ISAAC, and ISAAC's background and theory. Also take some tests for randomness, and a table of orders of magnitude. Here are also some protocols and a unit vector generator.
- See some skits from Boy Scouts,
SQL tricks from Oracle,
some paper airplanes,
and some cartoons that I wrote in college.
- Look into
formulae for n-body orbit simulations,
code for the HOMFLY knot
polynomial, voting methods, choosing random passwords,
jenny for pairwise testing,
some error correction codes,
a an april fool's design spec,
and a web page for choosing colors.
- Consider perpetual motion machines,
a dirigiped design,
a scale model of the solar system,
a page on exploring orbits with Java,
a simulation of Cruithne
(a near-earth object),
of figure-eight orbits,
of binary star planetary orbits,
a set of noncolliding orbits,
some Dyson Swarms (pretty pictures!),
some methods for the n-body problem,
a description of the orbit applet used,
and a tentative itzu world.
- Home projects
- See my half bath,
a house design that will never be built,
a dollhouse that did get built,
some genealogical notes,
and a roof rack for
- Here is my autobiography,
a cong from the British Museum,
a comparison of JPEG and JPEG 2000,
a bit on software patents,
my mom's art,
and some early Bob photos.
Here are people I've encountered more
Here are some other sites:
- Search engines: In the USA, Google and
Bing both do pretty well. I work for Bing, and
it used to be awful, but recently it's been quite comparable.
- Usenet: Google
groups answers the questions people tend to ask.
- Stock quotes: YCharts lets you
graph PE ratios over time as well as stock prices.
- News: http://sciencedaily.com for
science news, Slashdot for random
news, the BBC for a non-US
perspective, or the Onion for spoofs
of it all.
- Relative's web pages:
my mom's online art
any language to any other.
- Specific stuff: near-earth
journals, an online calculator, digital camera reviews,
and Rubik's Cube.
Send mail to Bob at email@example.com.