Re: Truth table evaluation

norman@flaubert.bellcore.com (Norman Ramsey)
Sat, 26 Feb 1994 19:57:43 GMT

          From comp.compilers

Related articles
Truth table evaluation philip@livenet.ac.uk (Philip Riebold) (1994-02-25)
Re: Truth table evaluation norman@flaubert.bellcore.com (1994-02-26)
Re: Truth table evaluation bcohen@cad721.intel.com (1994-02-26)
Re: Truth table evaluation ashok@cse.iitb.ernet.in (1994-02-28)
| List of all articles for this month |

Newsgroups: comp.compilers
From: norman@flaubert.bellcore.com (Norman Ramsey)
Keywords: logic, optimize
Organization: Bellcore, Morristown NJ
References: 94-02-189
Date: Sat, 26 Feb 1994 19:57:43 GMT

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
--


Post a followup to this message

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