home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / programm / 3585 < prev    next >
Encoding:
Text File  |  1993-01-25  |  2.0 KB  |  42 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!cs.utexas.edu!convex!convex!dodson
  3. From: Dave Dodson <dodson@convex.COM>
  4. Subject: Re: hashing floating-point numbers
  5. Originator: dodson@bach.convex.com
  6. Sender: usenet@news.eng.convex.com (news access account)
  7. Message-ID: <1993Jan25.161901.5233@news.eng.convex.com>
  8. Date: Mon, 25 Jan 1993 16:19:01 GMT
  9. Reply-To: dodson@convex.COM (Dave Dodson)
  10. References: <1993Jan22.175723.17245@chpc.utexas.edu>
  11. Nntp-Posting-Host: bach.convex.com
  12. Organization: Engineering, CONVEX Computer Corp., Richardson, Tx., USA
  13. X-Disclaimer: This message was written by a user at CONVEX Computer
  14.               Corp. The opinions expressed are those of the user and
  15.               not necessarily those of CONVEX.
  16. Lines: 24
  17.  
  18. In article <1993Jan22.175723.17245@chpc.utexas.edu> pefv700@chpc.utexas.edu (Christopher Phillips) writes:
  19. >What are the usual methods for hashing floating-point numbers
  20. >given that numbers "equivalent" to a certain precision should
  21. >hash to the same value?
  22.  
  23. I don't think you have specified the problem well.  Suppose you have
  24. chosen a certain tolerance, epsilon, such that if x and y differ in
  25. magnitude by less than epsilon ( abs(x-y) < epsilon ) then they hash
  26. to the same value.  Now suppose that you have x, y, and z such that
  27. x < y and y < z, but y-x < epsilon and z-y < epsilon.  Then x and y
  28. have to hash to the same value, and y and z have to hash to the same
  29. value, so x and z have to hash to the same value, even if z-x > epsilon.
  30.  
  31. Now, given any two floating point numbers, w and y, with w < y, you can
  32. construct a net of values w < x1 < x2 < ... < xn < y, with each adjacent
  33. pair differing by less than epsilon.  Then w hashes to the same value as
  34. x1, which hashes to the same value as x2, ..., which hashes to the same
  35. value as y.  So w and y hash to the same value for every w and y.  This
  36. does not sound useful.
  37.  
  38. ----------------------------------------------------------------------
  39.  
  40. Dave Dodson                                     dodson@convex.COM
  41. Convex Computer Corporation      Richardson, Texas      (214) 497-4234
  42.