You already know Wallace trees reduce a matrix of partial products to two rows in logarithmic time. But there's a competing scheme — Dadda multipliers — that looks almost identical on paper and produces the same result, yet uses fewer half-adders and often less silicon. The difference is a philosophical one about when to compress.

Wallace's rule (1964): at every stage, reduce as much as possible. If a column has 3 bits, use a full adder. If it has 2, use a half-adder. Squeeze every column down aggressively until you reach height 2.

Dadda's rule (1965): at every stage, reduce as little as possible to stay under the next target height in the sequence 2, 3, 4, 6, 9, 13, 19... (each term is ⌊1.5 × previous⌋). Only compress columns that must be compressed to hit the target. Leave everything else alone.

Why does Dadda's laziness win? Half-adders are wasted work. A half-adder takes 2 bits and produces 2 bits — it doesn't actually reduce the bit count in a column, it just shuffles one bit to the next column. Wallace uses half-adders eagerly whenever a column has exactly 2 bits; Dadda avoids them unless the column would otherwise exceed the target height. Fewer half-adders means fewer gates, less area, and often less delay because the critical path doesn't wind through unnecessary compressors.

Concrete example — 8×8 multiplier: The partial product matrix has a max column height of 8. Target heights descend 6 → 4 → 3 → 2, so four reduction stages.

• Wallace 8×8: ~38 full adders + ~15 half-adders
• Dadda 8×8: ~35 full adders + ~7 half-adders

Same number of stages, same logarithmic depth, but Dadda saves roughly half the half-adders — real silicon savings in a block that gets instantiated everywhere.

Rule of thumb: The Dadda sequence d(k+1) = ⌊1.5 × d(k)⌋ starting at d(1)=2 tells you the maximum column height allowed after k stages counting backward from the final adder. For an N-bit multiplier with max height N, count stages until d(k) ≥ N. An 8×8 needs 4 stages; a 32×32 needs 8 stages.

The tradeoff: Dadda's final CPA (carry-propagate adder) is wider than Wallace's because Dadda doesn't preemptively shove bits leftward with half-adders. So Dadda saves compressor area but pays slightly more at the final adder. In modern flows with fast carry-lookahead or Kogge-Stone finishers, that final-adder cost is negligible, so Dadda usually wins in ASIC synthesis. FPGA flows sometimes prefer Wallace because LUT-based carry chains reward the eager compression.