[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

225.0. "A new way to flip" by SPEEDY::BRETT () Sat Feb 23 1985 23:55

Ada has an interesting feature.  You can use any two ascending integers to
represent FALSE and TRUE.

For example,	FALSE => -37,  TRUE => 99

Now this feature makes implementing NOT, AND, OR, and XOR tricky!   Fortunately
I have found a NEAT trick!

	NOT X	can be done as		X_num xor (FALSE_num xor TRUE_num)

This is a generalisation of the old  1 <-> 0  trick of  X <-> 1-X.   Using XOR
rather than SUBTRACT avoids overflow problems!

Curiously enough XOR can be done as

	X XOR Y		is	X_num xor Y_num xor FIXUP

where FIXUP has the right bits to fix the result!  For example if the n'th bit
of FALSE_num and TRUE_num is ON,  then X_num xor Y_num would have this bit off
so FIXUP should have this bit on to get the result correctly one of FALSE_num
and TRUE_num.

Without being sure, it looks like AND and OR can both be done as

	X AND Y	
is
	((X xor FIXUP_X) or (Y xor FIXUP_Y)) xor FIXUP_RESULT

and X OR Y also.


/Bevin
T.RTitleUserPersonal
Name
DateLines
225.1TURTLE::GILBERTSun Feb 24 1985 21:3052
Hopefully, such code will only be generated in cases where the result of
the boolean expression must be materialized.

Consider the case where FALSE is represented by 0, and TRUE is some non-zero
value.  Then the boolean operators can be computed as:

	not X	 =	X_num xor TRUE_num
	X and Y	 =	X_num and Y_num
	X xor Y	 =	X_num xor Y_num
	X or Y	 =	X_num or Y_num

However, if FALSE is not represented by 0, we can apply a transformation so that
FALSE becomes 0, use the above equations, and apply the reverse transformation.
One such simple transformation is:  X_num xor FALSE_num.  So, we have:

	not X	=	((X_num xor FALSE_num) xor (TRUE_num xor FALSE_num))
				xor FALSE_num
		=	X_num xor (TRUE_num xor FALSE_num)
	X and Y	=	((X_num xor FALSE_num) and (Y_num xor FALSE_num))
				xor FALSE_num
		=	X_num and Y_num or (X_num or Y_num) and FALSE_num
	X xor Y	=	((X_num xor FALSE_num) xor (Y_num xor FALSE_num))
				xor FALSE_num
		=	X_num xor Y_num xor FALSE_num
	X or Y	=	((X_num xor FALSE_num) or (Y_num xor FALSE_num))
				xor FALSE_num
		=	X_num and Y_num or (X_num or Y_num) and not FALSE_num

Note the similarity of the expressions for "X and Y" and "X or Y" (which aren't
particularly simple -- can someone suggest a simpler expression for these?)

If the result of the operation need not be materialized, a better solution is
to find some bit position that's clear in FALSE_num and set in TRUE_num, compute
"X op Y" as "X_num op Y_num", and branch on the value of that bit position.
If such a bit position can't be found (ex: FALSE_num = -2, TRUE_num = 2), then
there must be a bit position that's set in FALSE_num and clear in TRUE_num
(else the two numbers would be equal), and the boolean operators are similarly
handled.


Another technique possible because FALSE_num < TRUE_num, is to treat "X or Y"
and "X and Y" as threshold functions.  That is, these are computed like:

	temp_num = X_num + Y_num
	if temp_num lss some_constant then false, else true.

(of course, this poses problems if there's a potential for overflow).

The ACBL instruction can be used to advantage here, if there's no chance
of overflow, and FALSE_num >= 0.

					- Gilbert
225.2ELUDOM::BRETTMon Feb 25 1985 11:579
Some of these thoughts had occurred (esp. the one about finding some bits
that differ and using those for the 'control-flow-boolean') and others had
not.   One reason for setting up the AND and OR operators the way I did was
the VAX h/w doesn't do AND very well (MCOML followed by a BICL is the usual
solution).

The use of + and threshold is real cute for AND (or OR with a lower threshold)

/Bevin
225.3SPRITE::OSMANThu Feb 28 1985 20:1327
Here's an excerpt from original note, to which I'd like to respond:
-------------------------beginning of excerpt-------------------------
Ada has an interesting feature.  You can use any two ascending integers to
represent FALSE and TRUE.

For example,	FALSE => -37,  TRUE => 99

Now this feature makes implementing NOT, AND, OR, and XOR tricky!   Fortunately
I have found a NEAT trick!

	NOT X	can be done as		X_num xor (FALSE_num xor TRUE_num)
-------------------------end of excerpt.  my response follows-------------

Note being an ADA programmer, I ask for the following clarification, which
I presume would benefit other nonADA people as well as me:

1)	XOR is generally associative, so if the parentheses are really
	needed, I presume your use of "xor" is not the traditional
	add-without-carry, which the standard XOR in logical math is ?

2)	I have come to the conclusion that when you say "X_num", you
	don't mean "X".  Because if you did, your statement is false.
	Test:  1 xor (-37 xor 99) => 1 xor (....0) => 1.  which is not
	NOT 1.

Thanks in advance for enlightening me regarding this !

225.4TURTLE::GILBERTThu Feb 28 1985 20:4319
1)	The parentheses are superfluous.  Note that the parenthesized
 	expression is constant (since TRUE_num and FALSE_num are constants).
	The standard bit-wise XOR of the (binary) numeric values is intended.

2)	While X represents a boolean in Ada, X_num represents the numeric
	encoding of this boolean (kind of like ORD(FALSE) in Pascal?).
	Note that -37 xor 99 = %B11011011 xor %B01100011 = %B10111000, not 0.
	    (using 16-bit signed two's-complement numbers).

	Also, the expressions assume that X_num is either equal to FALSE_num
	or TRUE_num.  Thus, in the example, 1 is an inappropriate numeric
	value for the representation of a boolean.

Perhaps the following will put you on the right track:  Given a variable X
that equals one of two constants (A or B), then one way to compute the *other*
number is by toggling all the bits that are different between A and B.
Consider A = 0100_0111 and B = 0110_0111 (underscores for readability only).
Then if X is one of these, a way to get the other is to take X xor 0010_0000;
this is similar to how some 'change case' code works.
225.5METOO::YARBROUGHFri Mar 01 1985 13:308
At least in BLISS and, I assume in ADA as well, one can define the constants
as
	TRUE = (1 EQL 1) and FALSE = (1 NEQ 1)
which depends only on the compiler's ability to do assignments and perform
relational operations on an integer constant. The user need not know or care
what the representation is, so long as one uses simply <bool-var> or NOT
<bool-var> and avoids comparisons like '<bool-var> EQL TRUE' and '<bool-var>
EQL FALSE'. - Lynn Yarbrough
225.6SPEEDY::BRETTFri Mar 01 1985 16:514
It's not quite like Pascal's ORD.   The only way to find out what underlying
representation is to 'uncheck convert' it to an integer.

/Bevin
225.7TURTLE::GILBERTMon Mar 04 1985 03:427
re .2 (the way Brett formed the expressions for AND and OR).

It turns out that for the set of operators provided by the VAX instruction
set, four operations are required to compute these functions, so Brett's
expressions turn out to be the 'best possible'.

Puzzle:  Why are most of the expressions independent of TRUE_num?