Actually, on further thought, this seems like a particularly rare
situation. Like, in a linear key space, given a search key S and
another key A, there's only one other key that's equidistant from S
with A.
We have a 160 bit key space (right? something like that), which gives
about 10^48 possible values. The chance that there are two equidistant
keys from a given search key in a node with 10^3 or 10^4 stored keys
is (I think) somewhere around 1 - ((1 - 1/10^48)^(10^3)). Actually,
it's:
N
1 - product (1 - n/S)
n = 1
(N = number of chances to hit, S = size of space -- this is
essentially the birthday problem)
Which is pretty damn close to 10^-45. Which is so damn unlikely it
makes my head spin -- I think there's a much better chance of having
your node hit by a meteor made of frozen airplane toilet waste than
having this happen.
Somebody correct my math if I'm wrong, but if there's a problem with
the search, I don't think it's because of equidistance.
~Mr. Bad
P.S. I wrote the following Guile program to figure out the exact
probability, and it works OK for birthdays, but it gets lame when
dealing with numbers as big as 2^160.
---8<---
#! /usr/bin/guile \
-e main -s
!#
(define (birthday-probability S N)
(do ((i 1 (+ i 1))
(acc 1 (* acc (- 1.0 (/ i S)))))
((> i N) (- 1.0 acc))))
(define (main args)
(let* ((S (string->number (list-ref args 1)))
(N (string->number (list-ref args 2)))
(p (birthday-probability S N)))
(format #t "Probability given ~A out of ~A: ~A\n" N S p)))
---8<---
--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Mr. Bad <[EMAIL PROTECTED]> | Pigdog Journal | http://pigdog.org/
freenet:MSK@SSK@u1AntQcZ81Y4c2tJKd1M87cZvPoQAge/pigdog+journal//
"Statements like this give the impression that this article was
written by a madman in a drug induced rage" -- Ben Franklin
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
_______________________________________________
Devl mailing list
[EMAIL PROTECTED]
http://lists.freenetproject.org/mailman/listinfo/devl
