Function SumRationalNumbers

circuit-std-go/logup/utils.go:29–57

Construct a binary summation tree to sum all the values

(api frontend.API, rs []RationalNumber)

// Construct a binary summation tree to sum all the values
func SumRationalNumbers(api frontend.API, rs []RationalNumber) RationalNumber {
	n := len(rs)
	if n == 0 {
		return RationalNumber{Numerator: 0, Denominator: 1}
	}

	if !IsPowerOf2(n) {
		fmt.Println(n)
		panic("The length of rs should be a power of 2")
	}

	cur := rs
	next := make([]RationalNumber, 0)

	for n > 1 {
		n >>= 1
		for i := 0; i < n; i++ {
			next = append(next, cur[i*2].Add(api, &cur[i*2+1]))
		}
		cur = next
		next = next[:0]
	}

	if len(cur) != 1 {
		panic("Summation code may be wrong.")
	}

	return cur[0]
}

func SimpleMin(a uint, b uint) uint {
	if a < b {