home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / programm / 3168 < prev    next >
Encoding:
Internet Message Format  |  1992-11-17  |  1.4 KB
  1. Path: sparky!uunet!usc!zaphod.mps.ohio-state.edu!swrinde!elroy.jpl.nasa.gov!nntp-server.caltech.edu!toddpw
  2. From: toddpw@cco.caltech.edu (Todd P. Whitesel)
  3. Newsgroups: comp.programming
  4. Subject: Re: Modulo n arithmetics
  5. Date: 17 Nov 1992 11:17:53 GMT
  6. Organization: California Institute of Technology, Pasadena
  7. Lines: 19
  8. Message-ID: <1eakd1INNg8d@gap.caltech.edu>
  9. References: <92-11-029@comp.compilers> <92-11-043@comp.compilers> <92-11-078@comp.compilers>
  10. NNTP-Posting-Host: sandman.caltech.edu
  11. Keywords: arithmetic
  12.  
  13. wendt@CS.ColoState.EDU (alan l wendt) writes:
  14.  
  15. >If the algorithm maintains the queue head pointer and the queue length,
  16. >instead of head and tail, the two cases can be disambiguated easily!
  17.  
  18. Sorry if this is nitpicking, but if your length ranges from 0..2^N and you
  19. want to store the length in a bitfield or packed subrange for some reason,
  20. you need to be careful. Thankfully, this is not much of a problem anymore
  21. (except on 8 bit embedded systems and such), but it is easy to solve:
  22.  
  23. >Horowitz & Sahni (Fundamentals of Computer Algorithms) suggest that one
  24. >might maintain an additional boolean to disambiguate the two situations,
  25.  
  26. If you use _two_ booleans, you get mutual exclusion for free. It's been
  27. a while since I worked it out though, so I'd have to dig up my notes to
  28. remember the whole algorithm. I do remember that it is fairly symmetric.
  29.  
  30. Todd Whitesel
  31. toddpw @ cco.caltech.edu
  32.