3 ms·

Zero suppressed decision diagrams work even better (less nodes). I think TAoCP Vol. 4 goes through a bunch of examples that applies them and has interesting cou

• dragontamer 4y ago
  > Zero suppressed decision diagrams work even better (less nodes) No. Zero suppressed decision diagrams (aka: ZDDs) *sometimes* work better than ROBDDs (the default). Its difficult to know which style of decision diagram is best for any application. There's lots of different pros-and-cons, and different styles. But the majority of Knuth's TAoCP Volume4 is on ROBDDs (or BDDs for short) for a reason, they're one of the "original" and broadly applicable. ----------- I'd say that BDDs / ROBDDs work best with so called "symmetric" functions. XOR, AND, OR, Addition... these are all "symmetric" (based off of the _count_ of its input bits, rather than an arbitrary function), and therefore very efficient to represent in BDDs. Functions built up "out of" symmetric functions are also reasonably efficient. So multiplication is built up from a lot of additions. So its not as efficient as addition, but efficient enough that we can represent 128-bit inputs and 128-bit outputs (ie: 64-bit x 64-bit == 128-bit output) kinds of functions with BDDs.