Sat, 26 Feb 1994 19:57:43 GMT

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

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.