Re: Truth table evaluation

Philip Riebold <philip@livenet.ac.uk> 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
details.


Norman Ramsey
--

Return to the comp.compilers page.
Search the comp.compilers archives again.