|Truth table evaluation firstname.lastname@example.org (Philip Riebold) (1994-02-25)|
|Re: Truth table evaluation email@example.com (1994-02-26)|
|Re: Truth table evaluation firstname.lastname@example.org (1994-02-26)|
|Re: Truth table evaluation email@example.com (1994-02-28)|
|From:||firstname.lastname@example.org (Norman Ramsey)|
|Organization:||Bellcore, Morristown NJ|
|Date:||Sat, 26 Feb 1994 19:57:43 GMT|
Philip Riebold <email@example.com> wrote:
> I need to evaluate the truth table for [an arbitrary Boolean] expression.
> At present I use a straightforward method of evaluating the expression for
> each of the possible combination of the variables.
> Are there any ways I can speed this up ?
A variation of this problem was given as a class assignment back when
I was a TA for Andrew Appel. The students had to implement two tricks:
For N variables, we have to evaluate the Boolean expression 2^N
times, but the machine is capable of doing 32 evaluations at once.
Write an interpreter using the C bit operators to do those evaluations.
Instead of interpreting the expression, generate machine code to
evaluate it. How many variables does the expression have to have
for this strategy to be worthwhile?
This assignment was great fun. Don't forget that on a modern machine
you may have to worry about I-cache vs D-cache if you write code and
then branch to it. David Keppel's `fly' library should handle those
Return to the
Search the comp.compilers archives again.