Fri Dec 6 12:59:06 2024
EVENTS
 FREE
SOFTWARE
INSTITUTE

POLITICS
JOBS
MEMBERS'
CORNER

MAILING
LIST

NYLXS Mailing Lists and Archives
NYLXS Members have a lot to say and share but we don't keep many secrets. Join the Hangout Mailing List and say your peice.

DATE 2015-04-01

LEARN

2024-12-06 | 2024-11-06 | 2024-10-06 | 2024-09-06 | 2024-08-06 | 2024-07-06 | 2024-06-06 | 2024-05-06 | 2024-04-06 | 2024-03-06 | 2024-02-06 | 2024-01-06 | 2023-12-06 | 2023-11-06 | 2023-10-06 | 2023-09-06 | 2023-08-06 | 2023-07-06 | 2023-06-06 | 2023-05-06 | 2023-04-06 | 2023-03-06 | 2023-02-06 | 2023-01-06 | 2022-12-06 | 2022-11-06 | 2022-10-06 | 2022-09-06 | 2022-08-06 | 2022-07-06 | 2022-06-06 | 2022-05-06 | 2022-04-06 | 2022-03-06 | 2022-02-06 | 2022-01-06 | 2021-12-06 | 2021-11-06 | 2021-10-06 | 2021-09-06 | 2021-08-06 | 2021-07-06 | 2021-06-06 | 2021-05-06 | 2021-04-06 | 2021-03-06 | 2021-02-06 | 2021-01-06 | 2020-12-06 | 2020-11-06 | 2020-10-06 | 2020-09-06 | 2020-08-06 | 2020-07-06 | 2020-06-06 | 2020-05-06 | 2020-04-06 | 2020-03-06 | 2020-02-06 | 2020-01-06 | 2019-12-06 | 2019-11-06 | 2019-10-06 | 2019-09-06 | 2019-08-06 | 2019-07-06 | 2019-06-06 | 2019-05-06 | 2019-04-06 | 2019-03-06 | 2019-02-06 | 2019-01-06 | 2018-12-06 | 2018-11-06 | 2018-10-06 | 2018-09-06 | 2018-08-06 | 2018-07-06 | 2018-06-06 | 2018-05-06 | 2018-04-06 | 2018-03-06 | 2018-02-06 | 2018-01-06 | 2017-12-06 | 2017-11-06 | 2017-10-06 | 2017-09-06 | 2017-08-06 | 2017-07-06 | 2017-06-06 | 2017-05-06 | 2017-04-06 | 2017-03-06 | 2017-02-06 | 2017-01-06 | 2016-12-06 | 2016-11-06 | 2016-10-06 | 2016-09-06 | 2016-08-06 | 2016-07-06 | 2016-06-06 | 2016-05-06 | 2016-04-06 | 2016-03-06 | 2016-02-06 | 2016-01-06 | 2015-12-06 | 2015-11-06 | 2015-10-06 | 2015-09-06 | 2015-08-06 | 2015-07-06 | 2015-06-06 | 2015-05-06 | 2015-04-06 | 2015-03-06 | 2015-02-06 | 2015-01-06 | 2014-12-06 | 2014-11-06 | 2014-10-06

Key: Value:

Key: Value:

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



  1. 2015-04-01 Ruben <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] external paths
  2. 2015-04-01 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] omp pthread madness
  3. 2015-04-02 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: Fw: Perl Developer / Linux SysAdmin Opportunities in South Florida
  4. 2015-04-02 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: omp pthread madness
  5. 2015-04-02 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: omp pthread madness
  6. 2015-04-02 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: [New discussion] which technologies/skills are good to have
  7. 2015-04-02 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Re: omp pthread madness
  8. 2015-04-05 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Re: Depths and heights
  9. 2015-04-09 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Re: Kernel thread scheduling
  10. 2015-04-09 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Re: Kernel thread scheduling
  11. 2015-04-13 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] BASh Shell Scripting
  12. 2015-04-13 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Chapter 5 Monitor
  13. 2015-04-13 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: [Perlweekly] #194 - The CPAN PR Challenge Now Has a Mini-Me!
  14. 2015-04-13 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Kernel Hacking Resources
  15. 2015-04-14 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: Invitation: Vintage Computer Festival
  16. 2015-04-14 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] hashing slots sizes
  17. 2015-04-15 Ruben <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] BASh Shell Scripting
  18. 2015-04-15 Maneesh Kongara <maneeshkongara-at-gmail.com> Re: [LIU Comp Sci] BASh Shell Scripting
  19. 2015-04-15 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: Monday: Join 121 HackerNestologists at "HackerNest NYC April
  20. 2015-04-15 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: You're confirmed for: NYLUG Open hacker hours
  21. 2015-04-15 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Hash Tables Examples
  22. 2015-04-15 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Re: hashing quadradic probes
  23. 2015-04-15 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] [ruben-at-mrbrklyn.com: Re: Heap Management Problem]
  24. 2015-04-16 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: Re: virtualbox
  25. 2015-04-16 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] linsched
  26. 2015-04-16 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] scheduler project thus far
  27. 2015-04-17 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Come Sunday Morning
  28. 2015-04-17 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Kernel Scheduling Project
  29. 2015-04-17 Ruben <ruben.safir-at-my.liu.edu> Subject: [LIU Comp Sci] more advanced coding musings ...
  30. 2015-04-19 Tony Genao <tony.genao-at-my.liu.edu> Re: [LIU Comp Sci] Fwd: [NYLXS - HANGOUT] Summers Here
  31. 2015-04-19 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] Fwd: [NYLXS - HANGOUT] Summers Here
  32. 2015-04-19 Tony Genao <tony.genao-at-my.liu.edu> Re: [LIU Comp Sci] Fwd: [NYLXS - HANGOUT] Summers Here
  33. 2015-04-19 Ruben <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] Fwd: [NYLXS - HANGOUT] Summers Here
  34. 2015-04-19 Tony Genao <tony.genao-at-my.liu.edu> Re: [LIU Comp Sci] Fwd: [NYLXS - HANGOUT] Summers Here
  35. 2015-04-19 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: [NYLXS - HANGOUT] Summers Here
  36. 2015-04-19 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Re: The more I learn the less I know
  37. 2015-04-22 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: Re: wait queues semiphores kernel implementations
  38. 2015-04-22 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] linux locks and mutex
  39. 2015-04-23 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: Re: Kernel Scheduler and wiat queues
  40. 2015-04-25 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: Kernel Scheduling and wait queues
  41. 2015-04-27 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: OS Cpt 9 27 question
  42. 2015-04-27 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: Tomorrow: You and 30 other Flatirons are going to "Flatiron
  43. 2015-04-28 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Re: DMCA exemption commenting process broken beyond repair
  44. 2015-04-29 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Do you have notes for this question
  45. 2015-04-29 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Professional Troll job available
  46. 2015-04-29 Ruben <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Re: DMCA exemption commenting process broken beyond repair

NYLXS are Do'ers and the first step of Doing is Joining! Join NYLXS and make a difference in your community today!