home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / sci / math / symbolic / 3395 < prev    next >
Encoding:
Internet Message Format  |  1993-01-07  |  2.5 KB
  1. Path: sparky!uunet!olivea!mintaka.lcs.mit.edu!zurich.ai.mit.edu!jaffer
  2. From: jaffer@zurich.ai.mit.edu (Aubrey Jaffer)
  3. Newsgroups: sci.math.symbolic
  4. Subject: Re: fast variable ordering
  5. Message-ID: <JAFFER.93Jan7115459@camelot.ai.mit.edu>
  6. Date: 7 Jan 93 16:54:59 GMT
  7. Sender: news@mintaka.lcs.mit.edu
  8. Organization: M.I.T. Artificial Intelligence Lab.
  9. Lines: 49
  10.  
  11. In article <JAFFER.92Nov28182855@camelot.ai.mit.edu> I wrote:
  12. >Variable or term orderings are a very common operations in Computer
  13. >Algebra systems.  It makes sense to optimize these comparisons in
  14. >order to improve system speed.
  15. >
  16. >Since in most systems there can be introduced new terms or variables
  17. >which are in between adjacent existing terms, a naive ordering cannot
  18. >be accomplished in finite storage.  String comparison is not as fast
  19. >as integer comparison, and even floating point is expensive on older
  20. >machines.
  21. >
  22. >I have been trying to find a dynamic data structure which would allow
  23. >me to assign integers of a finite range (say 2^29) to variables and
  24. >terms.  I am willing to periodically reassign all of these integers,
  25. >but not more often than once per hundred term creations.
  26. >
  27. >I have looked through several books on data structures and algorithms
  28. >and have not found an appropriate structure.  Can anyone suggest a
  29. >solution?
  30.  
  31.   Date: Sat, 28 Nov 92 17:58:12 PST
  32.   From: fateman@peoplesparc.Berkeley.EDU (Richard Fateman)
  33.  
  34.   I wrote a paper on doing this by combining a hash table and a tree,
  35.   in ISSAC-91.
  36.  
  37. I have not gotten a copy of this paper yet.  But WHITTEN@FWVA.SAIC.COM
  38. has sent me a suggestion which I distill as follows:
  39.  
  40. What he suggests is to store the variables in a binary tree, store the
  41. decision string in the tree of each element with that element, and use
  42. this decision string for fast variable comparisons.  If the tree
  43. remains reasonably balanced, 30 bits of decision string (alias
  44. integer) should be enough for any computation this century.
  45.  
  46. All the decision strings in a subtree will have to be recomputed
  47. whenever that subtree is rebalanced, but this is within my
  48. specifications.
  49.  
  50. What I acutally did in jacal1a0 is to make a string (of characters) a
  51. component of each variable.  The first character in the string is the
  52. user settable priority and the rest are from the variable name.
  53. String comparison is a reasonably fast and some basis for ordering has
  54. to be maintained with the variable.
  55.  
  56. At some time in the future the variable comparison acceleration as
  57. described above can be added onto the existing system by adding an
  58. integer field to variables and creating a balanced binary tree of
  59. variables.
  60.