Mul (hardcaml_circuits.Hardcaml

wallace

Take any three wires with the same weights and input them into a full adder. The result will be an output wire of the same weight and an output wire with a higher weight for each three input wires.
If there are two wires of the same weight left, input them into a half adder.
If there is just one wire left, connect it to the next layer.

dadda

Take any three wires with the same weights and input them into a full adder. The result will be an output wire of the same weight and an output wire with a higher weight for each three input wires.
If there are 2 wires of the same weight left, and the current number of output wires with that weight is equal to 2 (modulo 3), input them into a half adder. Otherwise, pass them through to the next layer.
If there is just 1 wire left, connect it to the next layer.

However, when a layer carries at most 3 input wires for any weight, that layer will be the last one. In this case, the Dadda tree will use half adder more aggressively (but still not as much as in a Wallace multiplier), to ensure that there are only two outputs for any weight. Then, the second rule above changes as follows:

If there are 2 wires of the same weight left, and the current number of output wires with that weight is equal to 1 or 2 (modulo 3), input them into a half adder. Otherwise, pass them through to the next layer.

module type Gen = sig ... end

module Config : sig ... end

val create_gen : 
  config:Config.t ->
  (module Gen with type t = 'a) ->
  'a ->
  'a ->
  'a

val create : 
  config:Config.t ->
  (module Hardcaml.Comb.S with type t = 'a) ->
  'a ->
  'a ->
  'a