home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / programm / 2440 next >
Encoding:
Internet Message Format  |  1992-08-23  |  2.5 KB
  1. Path: sparky!uunet!idacrd!desj@ccr-p.ida.org
  2. From: desj@ccr-p.ida.org (David desJardins)
  3. Newsgroups: comp.programming
  4. Subject: Re: Detecting Integer Overflow/Underflow
  5. Message-ID: <1573@idacrd.UUCP>
  6. Date: 23 Aug 92 18:30:13 GMT
  7. References: <HUDGENS.92Aug22113851@sun13.SCRI.FSU.EDU> <1572@idacrd.UUCP> <1992Aug23.133620.6154@gmuvax2.gmu.edu>
  8. Sender: desj@idacrd.UUCP
  9. Organization: IDA Center for Communications Research, Princeton
  10. Lines: 52
  11.  
  12. Steve Coile <scoile@gmuvax2.gmu.edu> writes:
  13. >Could someone please, PLEASE explain what is going on with
  14. >
  15. >    ((a ^ sum) & (a ^ b)) ^ b
  16. >
  17. >What is the justification for doing this (i.e. how in the WORLD would someone
  18. >figure this out that THIS is the way to do it?????)
  19.  
  20. It's close to being trial and error.  You know what boolean function you
  21. want, and you try different sequences of operations to find a minimal-
  22. cost representation.  As I said, I think this is in general NP-hard, so
  23. it's not going to be possible to state a simple algorithm.
  24.  
  25. It does help to use boolean logic; i.e.,
  26.  
  27.    F = (a & b) | ((a | b) & ~sum)
  28.            ; Start with the "obvious" representation of the carry
  29.            ; function in terms of {a, b, sum}.  Carry if a and b are
  30.            ; both 1, or if at least one of them is 1 and the sum is 0.
  31.  
  32.      = (a & b) | ((a ^ b) & ~sum)
  33.            ; We want to replace | operations by & and ^, which are the
  34.            ; basic addition and multiplication of mod-2 arithmetic.
  35.            ; This expression is equivalent to the first, because when a
  36.            ; and b are both 1, (a & b) makes the whole expression 1, so
  37.            ; it doesn't matter that we have changed the second term.
  38.  
  39.      = (a & b) ^ ((a ^ b) & ~sum)
  40.            ; Continue replacing.  The two operands of | are never both
  41.            ; 1, so we can replace | by ^.
  42.  
  43.      = (a & b) ^ ((a ^ b) & (one ^ sum))
  44.            ; ~x is the same as (one ^ x), where one is a word of all 1s.
  45.  
  46.      = (a & b) ^ (a & one) ^ (b & one) ^ (a & sum) ^ (b & sum)
  47.            ; Now we can use the ordinary distributive law to expand the
  48.            ; product fully.
  49.  
  50.      = (a & b) ^ a ^ b ^ (a & sum) ^ (b & sum)
  51.            ; (x & one) is the same as x.
  52.  
  53.      = a ^ (a & b) ^ (sum & a) ^ (sum & b) ^ b
  54.            ; Write the terms in a different order.
  55.  
  56.      = (a ^ sum) & (a ^ b) ^ b
  57.            ; Now recognize that the first four terms can be factored
  58.            ; into a product. 
  59.  
  60. Then you look for a while for a representation with three terms and fail
  61. to find one.  So you conclude that this is the best you can do.
  62.  
  63.                                         David desJardins
  64.