Messages in this thread | | | Date | Mon, 25 Jan 1999 14:38:26 +0000 | From | Jamie Lokier <> | Subject | Re: arca-vm-26 |
| |
I wrote: > I don't think the source has to be _that_ good, so a linear feedback > shift register should do. You can periodically mix in entropy from the > random device into the LFSR value to keep it "fairly" random. (Say, > whenever entropy enters the randomness pool),
I've changed my mind. For a VMA skiplist, I would try a polynomial congruential generator similar to the kind used by BSD random(), as that can also be extremely fast, and is pretty good.
Benjamin Saller Bender wrote: > Can you imagine the VM or the network layer blocking to wait for > the entorpy pool to refill though. The better the random() the better the > spread on the tree, it becomes more important as N grows.
The LFSR suggestion doesn't involve any blocking. An LFSR, which is very fast, provides random bits though they are not particularly good. A skip list only needs bits, which suits an LFSR. New entropy is used to stir the LFSR value to keep it fair -- to avoid identifiable long term patterms. That is only done when new entropy arrives, not when a random bit is required.
-- Jamie
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/
| |