func NewKaratsubaMultiplier(cc *Compiler, limit int, a, b, r []*Wire) error {
	a, b = cc.ZeroPad(a, b)
	if len(a) > len(r) {
		a = a[0:len(r)]
		b = b[0:len(r)]
	}
	if len(a) <= limit {
		return NewArrayMultiplier(cc, a, b, r)
	}
	mid := len(a) / 2
	aLow := a[:mid]
	aHigh := a[mid:]
	bLow := b[:mid]
	bHigh := b[mid:]
	z0 := MakeWires(types.Size(min(max(len(aLow), len(bLow))*2, len(r))))
	if err := NewKaratsubaMultiplier(cc, limit, aLow, bLow, z0); err != nil {
		return err
	}
	aSumLen := max(len(aLow), len(aHigh)) + 1
	aSum := MakeWires(types.Size(aSumLen))
	if err := NewAdder(cc, aLow, aHigh, aSum); err != nil {
		return err
	}
	bSumLen := max(len(bLow), len(bHigh)) + 1
	bSum := MakeWires(types.Size(bSumLen))
	if err := NewAdder(cc, bLow, bHigh, bSum); err != nil {
		return err
	}
	z1 := MakeWires(types.Size(min(max(aSumLen, bSumLen)*2, len(r))))
	if err := NewKaratsubaMultiplier(cc, limit, aSum, bSum, z1); err != nil {
		return err
	}
	z2 := MakeWires(types.Size(min(max(len(aHigh), len(bHigh))*2, len(r))))
	if err := NewKaratsubaMultiplier(cc, limit, aHigh, bHigh, z2); err != nil {
		return err
	}
	sub1 := MakeWires(types.Size(len(r)))
	if err := NewSubtractor(cc, z1, z2, sub1); err != nil {
		return err
	}
	sub2 := MakeWires(types.Size(len(r)))
	if err := NewSubtractor(cc, sub1, z0, sub2); err != nil {
		return err
	}
	shift1 := cc.ShiftLeft(z2, len(r), mid*2)
	shift2 := cc.ShiftLeft(sub2, len(r), mid)
	add1 := MakeWires(types.Size(len(r)))
	if err := NewAdder(cc, shift1, shift2, add1); err != nil {
		return err
	}
	return NewAdder(cc, add1, z0, r)
}
NewKaratsubaMultiplier creates a multiplier circuit implementing
the Karatsuba algorithm
(https://en.wikipedia.org/wiki/Karatsuba_algorithm). The Karatsuba
algorithm is should produce faster circuits on inputs of about 128
bits (the number of non-XOR gates is smaller). On input sizes of
256 bits also the overall circuits are smaller than with the array
multiplier algorithm.

Bits  Array     a-xor     a-and    Karatsu   K-xor    K-and
8     301       172       129      993       724      269
16    1365      852       513      3573      2660     913
32    5797      3748      2049     11937     8980     2957
64    23877     15684     8193     38277     28964    9313
128   96901     64132     32769    119793    90964    28829
256   390405    259332    131073   369333    281060   88273
512   1567237   1042948   524289   1127937   859540   268397
1024  6280197   4183044   2097153  3423717   2611364  812353
2048  25143301  16754692  8388609  10350993  7899604  2451389
package circuits
import (
	"github.com/markkurossi/mpc/circuit"
	"github.com/markkurossi/mpc/types"
)
func NewMultiplier(c *Compiler, arrayTreshold int, x, y, z []*Wire) error {
	if false {
		return NewArrayMultiplier(c, x, y, z)
	}
	if arrayTreshold < 8 {
		var ok bool
		arrayTreshold, ok = multiplierArrayTresholds[len(x)]
		if !ok {
			arrayTreshold = 21
		}
	}
	return NewKaratsubaMultiplier(c, arrayTreshold, x, y, z)
}
func NewArrayMultiplier(compiler *Compiler, x, y, z []*Wire) error {
	x, y = compiler.ZeroPad(x, y)
	if len(x) > len(z) {
		x = x[0:len(z)]
		y = y[0:len(z)]
	}
	if len(x) == 1 {
		compiler.AddGate(NewBinary(circuit.AND, x[0], y[0], z[0]))
		if len(z) > 1 {
			z[1] = compiler.ZeroWire()
		}
		return nil
	}
	var sums []*Wire
	for i, xn := range x {
		var s *Wire
		if i == 0 {
			s = z[0]
		} else {
			s = NewWire()
			sums = append(sums, s)
		}
		compiler.AddGate(NewBinary(circuit.AND, xn, y[0], s))
	}
	var j int
	for j = 1; j+1 < len(y); j++ {
		var ands []*Wire
		for _, xn := range x {
			wire := NewWire()
			compiler.AddGate(NewBinary(circuit.AND, xn, y[j], wire))
			ands = append(ands, wire)
		}
		var nsums []*Wire
		var c *Wire
		for i := 0; i < len(ands); i++ {
			cout := NewWire()
			var s *Wire
			if i == 0 {
				s = z[j]
			} else {
				s = NewWire()
				nsums = append(nsums, s)
			}
			if i == 0 {
				NewHalfAdder(compiler, ands[i], sums[i], s, cout)
			} else if i >= len(sums) {
				NewHalfAdder(compiler, ands[i], c, s, cout)
			} else {
				NewFullAdder(compiler, ands[i], sums[i], c, s, cout)
			}
			c = cout
		}
		sums = append(nsums, c)
	}
	var c *Wire
	for i, xn := range x {
		and := NewWire()
		compiler.AddGate(NewBinary(circuit.AND, xn, y[j], and))
		var cout *Wire
		if i+1 >= len(x) && j+i+1 < len(z) {
			cout = z[j+i+1]
		} else {
			cout = NewWire()
		}
		if j+i < len(z) {
			if i == 0 {
				NewHalfAdder(compiler, and, sums[i], z[j+i], cout)
			} else if i >= len(sums) {
				NewHalfAdder(compiler, and, c, z[j+i], cout)
			} else {
				NewFullAdder(compiler, and, sums[i], c, z[j+i], cout)
			}
		}
		c = cout
	}
	for i := j + len(x) + 1; i < len(z); i++ {
		z[1] = compiler.ZeroWire()
	}
	return nil
}