Thu Dec 12 13:07:45 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-05-01

LEARN

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

Key: Value:

Key: Value:

MESSAGE
DATE 2015-05-06
FROM Ruben Safir
SUBJECT Subject: [LIU Comp Sci] hashing multiplication
From owner-learn-outgoing-at-mrbrklyn.com Wed May 6 11:31:53 2015
Return-Path:
X-Original-To: archive-at-mrbrklyn.com
Delivered-To: archive-at-mrbrklyn.com
Received: by mrbrklyn.com (Postfix)
id 5E9CE1612E1; Wed, 6 May 2015 11:31:53 -0400 (EDT)
Delivered-To: learn-outgoing-at-mrbrklyn.com
Received: by mrbrklyn.com (Postfix, from userid 28)
id 4F3211612ED; Wed, 6 May 2015 11:31:53 -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 A034D1612E1
for ; Wed, 6 May 2015 11:31:27 -0400 (EDT)
Received: from [10.0.0.19] (www.mrbrklyn.com [96.57.23.82])
by mailbackend.panix.com (Postfix) with ESMTPSA id 216D412DA5;
Wed, 6 May 2015 11:31:26 -0400 (EDT)
Message-ID: <554A33CE.8070504-at-panix.com>
Date: Wed, 06 May 2015 11:31:26 -0400
From: Ruben Safir
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.6.0
MIME-Version: 1.0
To: "Jose A. Rodriguez"
Subject: [LIU Comp Sci] hashing multiplication
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
Sender: owner-learn-at-mrbrklyn.com
Precedence: bulk
Reply-To: learn-at-mrbrklyn.com

I don't understand question 9. I've been working on it since 6AM and
even on the day that you presented this material. Variables drop in the
proof without clear definitions, and the last 2 lines seem to be
completely disconnected to what was presented before. I'm sure it my
fault, but I don't know what p,m,k,a,b, or even A stand for. Most of
all, I don't know what p is.

This is what I understand

h(k) = m(kA % 1) ==> and then you make that the floor

and I'm not sure why because % 1 makes a fraction EVERY TIME except for
whole numbers. floor 5.25%1 has to be 0.25

m is the table size - that I understand.
k is the key
kA % 1 is a fraction, specifically the fraction part of kA and when
multiplied by m that give you some value less than m, and now I see why
you need the floor.

this formula guarantees you hash less than m. It says nothing about
shared values, FWIW, or probing.

Up to this I understand.

Now, more assumptions
k must be less than a word. This should have been said on the top, IMO.
and it is kind of useless because it leaves very few keys
m = 2^p <=== Now this is where I start to get lost. What purpose is p?

A = s/2^w <==== Now what is s for?
Now what can be added to the notes is as follows:
if i follow your logic here

Since A is a real number such that 0< A < 1

if we multiply A times the maximum integer of the size of a word we get
a value, which we can call s, whose domain is 0< and less than 2^w

A*2^w = s
where 0 < s < 2^w
and 0 < A < 1
and where 0 < k < 2^w <== by definition

that means

kA = k s/2^w has a range of

0 < ks < 2^(2w) of to say ks, whatever s is, fits in two words

Now here is the really good part ;)

For no reason at all, lets turn this in to a polynumer equation or order w.

ks = a2^w +b(2^w)^0 ... just so I can understand it ;)

ks = a2^w + b where b is the lower word and a is the bits of the higher
word.

Fine, I actually understand this up to here. Then I'm completely lost.

It says the fractional part of kA = ks/2^w is b/2^w ????

you lost me here. The fractional part of kA is completely dependent on
a k and A. If k is 2, which is a valid prossible k,, and A is 0.5.
which is a completely valid A, then there is no fractional part of kA...








  1. 2015-05-02 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] debuging methods
  2. 2015-05-02 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Excellent article on Virtual Paging and OS memory
  3. 2015-05-02 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Great Article on Software Concordance program writing
  4. 2015-05-02 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Semephores and what the heck are those things?
  5. 2015-05-03 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Go Language tutorials
  6. 2015-05-04 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] ACL and beyound security in linux
  7. 2015-05-04 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: [Perlweekly] #197 - YAPC::EU Master classes - talks - hackathons
  8. 2015-05-05 Ruben <ruben.safir-at-my.liu.edu> Re: [LIU Comp Sci] Fibonacci trees
  9. 2015-05-05 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Examination Question for Allogorthims
  10. 2015-05-05 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fibonacci trees
  11. 2015-05-05 Ruben <ruben.safir-at-my.liu.edu> Subject: [LIU Comp Sci] Fwd: Internships with Oracle, Amtrak, The Nature Conservancy & more
  12. 2015-05-05 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Nice possible project for NYLXS or others
  13. 2015-05-06 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] Fibonacci trees
  14. 2015-05-06 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] Fibonacci trees
  15. 2015-05-06 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] Fibonacci trees
  16. 2015-05-06 Ruben <ruben.safir-at-my.liu.edu> Subject: [LIU Comp Sci] Fwd: Re: [opensuse] Re: no space left on the device
  17. 2015-05-06 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] hashing multiplication
  18. 2015-05-08 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: Kernel Scheduling and wait queues
  19. 2015-05-08 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: Re: Kernel Scheduler and wiat queues
  20. 2015-05-08 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Re: [NYLXS - HANGOUT] Things to study over the summer
  21. 2015-05-08 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Things to study over the summer
  22. 2015-05-10 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] scheduler Slides
  23. 2015-05-10 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] scheduler Slides
  24. 2015-05-11 Ruben Safir <ruben.safir-at-my.liu.edu> Re: [LIU Comp Sci] scheduler Slides
  25. 2015-05-11 Ruben Safir <ruben.safir-at-my.liu.edu> Re: [LIU Comp Sci] scheduler Slides
  26. 2015-05-11 Justin Lau <justinml-at-gmail.com> Re: [LIU Comp Sci] scheduler Slides
  27. 2015-05-11 Justin Lau <justinml-at-gmail.com> Re: [LIU Comp Sci] scheduler Slides
  28. 2015-05-11 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] scheduler Slides
  29. 2015-05-11 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] scheduler Slides
  30. 2015-05-11 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] scheduler Slides
  31. 2015-05-12 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Job sound like this evenings lectures
  32. 2015-05-12 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] jobs
  33. 2015-05-12 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] LAMP Jobs
  34. 2015-05-13 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] April Journal is Available
  35. 2015-05-13 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: Tomorrow: You and 256 others are going to "Btrfs"
  36. 2015-05-13 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Malloc systemtap probes: an example
  37. 2015-05-13 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Stackiq - Educational Program
  38. 2015-05-13 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Student Lab and Club House
  39. 2015-05-13 mrbrklyn-at-panix.com Subject: [LIU Comp Sci] [member-at-linkedin.com: RE: April Journal is Available]
  40. 2015-05-13 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] [mrbrklyn-at-panix.com: Re: [NYLXS - HANGOUT] Things to study over the
  41. 2015-05-14 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Weekly Education Meeting
  42. 2015-05-18 mrbrklyn-at-panix.com Subject: [LIU Comp Sci] [jkeen-at-verizon.net: ny.pm Technical Meeting Wed May 20 6:15 pm]
  43. 2015-05-25 Ruben Safir <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Summer NYLXS Study Schedule
  44. 2015-05-28 Tony Genao <tony.genao-at-my.liu.edu> Re: [LIU Comp Sci] Summer NYLXS Study Schedule
  45. 2015-05-28 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] Summer NYLXS Study Schedule
  46. 2015-05-28 Tony Genao <tony.genao-at-my.liu.edu> Re: [LIU Comp Sci] Summer NYLXS Study Schedule
  47. 2015-05-28 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] Summer NYLXS Study Schedule
  48. 2015-05-28 Ruben <mrbrklyn-at-panix.com> Subject: [LIU Comp Sci] Fwd: Re: Programming Position
  49. 2015-05-28 mrbrklyn-at-panix.com Subject: [LIU Comp Sci] [ruben-at-www.mrbrklyn.com: Linux 1 Book]
  50. 2015-05-31 Ruben Safir <mrbrklyn-at-panix.com> Re: [LIU Comp Sci] Summer NYLXS Study Schedule

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