home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / programm / 3557 < prev    next >
Encoding:
Internet Message Format  |  1993-01-23  |  2.5 KB
  1. Path: sparky!uunet!spool.mu.edu!yale.edu!ira.uka.de!sbusol.rz.uni-sb.de!coli.uni-sb.de!coli-gate.coli.uni-sb.de!spackman
  2. From: spackman@disco-sol.dfki.uni-sb.de (Stephen Spackman)
  3. Newsgroups: comp.programming
  4. Subject: Re: hashing floating-point numbers
  5. Date: 23 Jan 1993 16:16:56 GMT
  6. Organization: DFKI Saarbruecken GmbH, D-W 6600 Saarbruecken
  7. Lines: 42
  8. Message-ID: <SPACKMAN.93Jan23172204@disco-sol.dfki.uni-sb.de>
  9. References: <1993Jan22.175723.17245@chpc.utexas.edu>
  10. Reply-To: stephen@acm.org
  11. NNTP-Posting-Host: disco-sol.dfki.uni-sb.de
  12. In-reply-to: pefv700@chpc.utexas.edu's message of Fri, 22 Jan 93 17:57:23 GMT
  13.  
  14. In article <1993Jan22.175723.17245@chpc.utexas.edu> pefv700@chpc.utexas.edu (Christopher Phillips) writes:
  15.  
  16. |What are the usual methods for hashing floating-point numbers
  17. |given that numbers "equivalent" to a certain precision should
  18. |hash to the same value?
  19.  
  20. If you think about the equivalence classes that you have in mind for a
  21. moment, you'll realise that this probably isn't a good idea anyway.
  22. Consider the following algorithm for your problem (which isn't usably
  23. efficient and doesn't have good statistical properties, but shows the
  24. problem up neatly):
  25.  
  26. problematicFloatHash
  27.   [ (epsilon    :: Float),    .. the difference defining "equivalence"
  28.     (hash     :: UninterpretedBinary(size Float) -> Hash),
  29.                 .. an arbitrary hash function for the bits
  30.     (x        :: Float)    .. the input value
  31.   ]
  32. : .if x = x + epsilon
  33.   .then hash x
  34.   .else problematicFloatHash[epsilon, hash, x + epsilon]
  35.   .
  36.  
  37. Basically all numbers with an exponent small enough that they can
  38. represent a difference of your epsilon will have to hash to the same
  39. value; if you choose a value for epsilon like 10^6, and you have, say,
  40. 48 bits in your mantissa, all numbers absolutely less than something
  41. like 2^48/10^6 ~ 2^28 will get folded together!
  42.  
  43. The problem is much worse if the error is expressed in relative terms:
  44. quite likely this model will be continuous, and *all* numbers will have
  45. to hash to the same value.
  46.  
  47. More likely what you want to do is round the things to a multiple of
  48. your bucket size *before* hashing them, and make sure that the context
  49. of use of your algorithm isn't sensitive to off-by-one errors in choice
  50. of bucket. (Of course, that's what fixed-size representations are all
  51. about).
  52. ----------------------------------------------------------------------
  53. stephen p spackman    +49 681 302 5288(o) 5282(sec)    stephen@acm.org
  54.       dfki / stuhlsatzenhausweg 3 / d-w-6600 saarbruecken 11 / germany
  55. ----------------------------------------------------------------------
  56.