MESSAGE
| DATE | 2015-04-15 |
| FROM | Ruben Safir
|
| SUBJECT | Subject: [LIU Comp Sci] Re: hashing quadradic probes
|
From owner-learn-outgoing-at-mrbrklyn.com Wed Apr 15 02:05:09 2015
Return-Path:
X-Original-To: archive-at-mrbrklyn.com
Delivered-To: archive-at-mrbrklyn.com
Received: by mrbrklyn.com (Postfix)
id 8ADD2161130; Wed, 15 Apr 2015 02:05:09 -0400 (EDT)
Delivered-To: learn-outgoing-at-mrbrklyn.com
Received: by mrbrklyn.com (Postfix, from userid 28)
id 74B34161165; Wed, 15 Apr 2015 02:05:09 -0400 (EDT)
Delivered-To: learn-at-nylxs.com
Received: from mailbackend.panix.com (mailbackend.panix.com [166.84.1.89])
by mrbrklyn.com (Postfix) with ESMTP id 6BC74161130
for ; Wed, 15 Apr 2015 02:04:44 -0400 (EDT)
Received: from [10.0.0.19] (www.mrbrklyn.com [96.57.23.82])
by mailbackend.panix.com (Postfix) with ESMTPSA id 96F03127D9;
Wed, 15 Apr 2015 02:04:44 -0400 (EDT)
Message-ID: <552DFF7C.6080708-at-panix.com>
Date: Wed, 15 Apr 2015 02:04:44 -0400
From: Ruben Safir
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.3.0
MIME-Version: 1.0
To: "Jose A. Rodriguez"
Subject: [LIU Comp Sci] Re: hashing quadradic probes
References: <552D2564.5040701-at-mrbrklyn.com> <2DC87042-A9B2-451B-A4FD-8CD9267C1CD9-at-liu.edu>,<552D4A1E.5030908-at-mrbrklyn.com> <818D0A13-C015-4B31-843F-4344718EA68B-at-liu.edu>,<552D51D1.4000701-at-mrbrklyn.com> <29AF6F71-169D-4719-B089-676130D7A9B4-at-liu.edu>,<552D6AA7.3000203-at-mrbrklyn.com>
In-Reply-To:
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: 7bit
Sender: owner-learn-at-mrbrklyn.com
Precedence: bulk
Reply-To: learn-at-mrbrklyn.com
I was looking over the details of the proof for probing needing to be
more than m/2. I don't know.
I'm lost on the final lines
First, the step were we are subtracting the formula
h(k) + i^2 = Am + r
h(k) + j^2 = Bm + r
Why are we subtracting?
Just shaking out an example
if m = 3, i = 16 and j=19
16/3 = 5 R1
3*5 +1 check
19/3 = 6 R1
3*6 + 1 - Check
Now in this case j and i are much larger than m (let alone m/2) so you
can see right away the problems as we get closer the condition
0 <= i < j < m/2
(in fact I wonder if there is a limit means of solving this problem such
as if i goes from inf -> -inf and j is constant solve the limit where
i%m = j%m )
anyway, why are we subtracting after this instead of solving for
simultaneous equation ... maybe my math is rusty.
The 2nd to last line, I can't understand at all.
But m cannot divide j-1 or j+1, since j-1 <= m/2 and j+1 <= m/2 + 2m -1
= m-1 ??
My first thought its, hey you can always divide. You might not like
the result but you can ALWAYS do it. and that equation on the end, I
don't know where that comes from at all.
Ruben
|
|
