From Mathematics to Generic Programming (2011)

---

7.3 Requirements on N

Now that we know that A must be a noncommutative additive semigroup, we can specify that in our template instead of just saying typename:

Click here to view code image

template <NoncommutativeAdditiveSemigroup A, typename N>
A multiply_accumulate(A r, N n, A a) {
while (true) {
if (odd(n)) {
r = r + a;
if (n == 1) return r;
}
n = half(n);
a = a + a;
}
}

Here we’re using NonCommutativeAdditiveSemigroup as a C++ concept, a set of requirements on types that we’ll discuss in Chapter 10. Instead of saying typename, we name the concept we wish to use. Since concepts are not yet supported in the language as of this writing, we’re doing a bit of preprocessor slight-of-hand:

Click here to view code image

#define NonCommutativeAdditiveSemigroup typename

As far as the compiler is concerned, A is just a typename, but for us, it’s a NonCommutativeAdditiveSemigroup. We’ll use this trick from now on when we want to specify the type requirements in templates.

Although this behavior is not needed for abstract mathematics, in programming we need our variables to be constructible and assignable, which are also guaranteed by being regular types. From now on, when we specify an algebraic structure as a concept, we will assume that we are inheriting all of the regular type requirements.

What about the requirements on our other argument’s type, N? Let’s start with the syntactic requirements. N must be a regular type implementing

• half

• odd

• == 0

• == 1

Here are the semantic requirements on N:

• even(n) half(n) + half(n) = n

• odd(n) even(n – 1)

• odd(n) half(n – 1) = half(n)

• Axiom: n ≤ 1 ∨ half(n) = 1 ∨ half(half(n)) = 1 ∨ . . .

Which C++ types satisfy these requirements? There are several: uint8_t, int8_t, uint64_t, and so on. The concept that they satisfy is called N Integer.

* * *

Now we can finally write a fully generic version of our multiply-accumulate function by specifiying the correct requirements for both types:

Click here to view code image

template <NoncommutativeAdditiveSemigroup A, Integer N>
A multiply_accumulate_semigroup(A r, N n, A a) {
// precondition(n >= 0);
if (n == 0) return r;
while (true) {
if (odd(n)) {
r = r + a;
if (n == 1) return r;
}
n = half(n);
a = a + a;
}
}

We’ve added one more line of code, which returns r when n is zero. We do this because when n is zero, we don’t need to do anything. However, the same is not true for multiply, as we’ll see in a moment.

Here’s the multiply function that calls the preceding code; it has the same requirements:

Click here to view code image

template <NoncommutativeAdditiveSemigroup A, Integer N>
A multiply_semigroup(N n, A a) {
// precondition(n > 0);
while (!odd(n)) {
a = a + a;
n = half(n);
}
if (n == 1) return a;
return multiply_accumulate_semigroup(a, half(n - 1), a + a);
}

We can also update our helper functions odd and half to work for any Integer:

Click here to view code image

template <Integer N>
bool odd(N n) { return bool(n & 0x1); }

template <Integer N>
N half(N n) { return n >> 1; }

7.4 New Requirements

Our precondition for multiply says that n must be strictly greater than zero. (We made this assumption earlier, since the Greeks had only positive integers, but now we need to make it explicit.) What should an additive semigroup multiplication function return when n is zero? It should be the value that doesn’t change the result when the semigroup operator—addition—is applied. In other words, it should be the additive identity. But an additive semigroup is not required to have an identity element, so we can’t depend on this property. In other words, we can’t rely on there being an equivalent of zero. (Remember, a no longer has to be an integer; it can be any NoncommutativeAdditiveSemigroup, such as positive integers or nonempty strings.) That’s why n can’t be zero.

But there is an alternative: instead of having a restriction on the data requiring n > 0, we can require that any type we use know how to deal with 0. We do this by changing the concept requirement on n from additive semigroup to monoid. Recall from Chapter 6 that in addition to an associative binary operation, a monoid contains an identity element e and an identity axiom that says

x ο e = e ο x = x

In particular, we’re going to use a noncommutative additive monoid, where the identity element is called “0”:

x + 0 = 0 + x = x

This is the multiply function for monoids:

Click here to view code image

template <NoncommutativeAdditiveMonoid A, Integer N>
A multiply_monoid(N n, A a) {
// precondition(n >= 0);
if (n == 0) return A(0);
return multiply_semigroup(n, a);
}

What if we want to allow negative numbers when we multiply? We need to ensure that “multiplying by a negative” makes sense for any type we might have. This turns out to be equivalent to saying that the type must support an inverse operation. Again, we find that our current requirement—noncommutative additive monoid—is not guaranteed to have this property. For this, we need a group. A group, as you may recall from Chapter 6, includes all of the monoid operations and axioms, plus an inverse operation x^–1 that obeys the cancellation axiom

x ο x^–1 = x^–1 ο x = e

In our case, we want a noncommutative additive group, one where the inverse operation is unary minus and the cancellation axiom is:

x+ –x = –x + x = 0

Having strengthened our type requirements, we can remove our preconditions on n to allow negative values. Again, we’ll wrap the last version of our function with our new one:

Click here to view code image

template <NoncommutativeAdditiveGroup A, Integer N>
A multiply_group(N n, A a) {
if (n < 0) {
n = -n;
a = -a;
}
return multiply_monoid(n, a);
}

7.5 Turning Multiply into Power

Now that our code has been generalized to work for any additive semigroup (or monoid or group), we can make a remarkable observation:

If we replace + with * (thereby replacing doubling with squaring), we can use our existing algorithm to compute aⁿ instead of n · a.

Here’s the C++ function we get when we apply this transformation to our code for multiply_accumulate_semigroup:

Click here to view code image

template <MultiplicativeSemigroup A, Integer N>
A power_accumulate_semigroup(A r, A a, N n) {
// precondition(n >= 0);
if (n == 0) return r;
while (true) {
if (odd(n)) {
r = r * a;
if (n == 1) return r;
}
n = half(n);
a = a * a;
}
}

The new function computes raⁿ. The only things that have changed are highlighted in bold. Note that we’ve changed the order of arguments a and n, so as to match the order of arguments in standard mathematical notation (i.e., we say na, but aⁿ).

Here’s the function that computes power:

Click here to view code image

template <MultiplicativeSemigroup A, Integer N>
A power_semigroup(A a, N n) {
// precondition(n > 0);
while (!odd(n)) {
a = a * a;
n = half(n);
}
if (n == 1) return a;
return power_accumulate_semigroup(a, a * a, half(n - 1));
}

Here are the wrapped versions for multiplicative monoids and groups:

Click here to view code image

template <MultiplicativeMonoid A, Integer N>
A power_monoid(A a, N n) {
// precondition(n >= 0);
if (n == 0) return A(1);
return power_semigroup(a, n);
}

template <MultiplicativeGroup A, Integer N>
A power_group(A a, N n) {
if (n < 0) {
n = -n;
a = multiplicative_inverse(a);
}
return power_monoid(a, n);
}

Just as we needed an additive identity (0) for our monoid multiply, so we need a multiplicative identity (1) in our monoid power function. Also, just as we needed an additive inverse (unary minus) for our group multiply, so we need a multiplicative inverse for our group power function. There’s no built-in multiplicative inverse (reciprocal) operation in C++, but it’s easy to write one:

Click here to view code image

template <MultiplicativeGroup A>
A multiplicative_inverse(A a) {
return A(1) / a;
}

7.6 Generalizing the Operation

We’ve seen examples of two semigroups—additive and multiplicative—each with its associated operation (+ and *, respectively). The fact that we could use the same algorithm for both is wonderful, but it was annoying to have to write different versions of the same code for each case. In reality, there could be many such semigroups, each with its associative operations (for example, multiplication mod 7) that work on the same type T. Rather than having another version for every operation we want to use, we can generalize the operation itself, just as we generalized the types of the arguments before. In fact, there are many situations where we need to pass an operation to an algorithm; you may have seen examples of this in STL.

Here’s the accumulate version of our power function for an arbitrary semigroup. We still refer to the function it computes as “power,” even though the operation it’s repeatedly applying may not necessarily be multiplication.

Click here to view code image

template <Regular A, Integer N, SemigroupOperation Op>
// requires (Domain<Op, A>)
A power_accumulate_semigroup(A r, A a, N n, Op op) {
// precondition(n >= 0);
if (n == 0) return r;
while (true) {
if (odd(n)) {
r = op(r, a);
if (n == 1) return r;
}
n = half(n);
a = op(a, a);
}
}

Notice that we’ve added a “requires” comment to our template that says the domain of operation Op must be A. If future versions of C++ support concepts, this comment could be turned into a statement (similar to an assertion) that the compiler could use to ensure the correct relationship holds between the given types. As it is, we’ll have to make sure as programmers that we call this function only with template arguments that satisfy the requirement.

Also, since we no longer know which kind of semigroup to make A—it could be additive, multiplicative, or something else altogether, depending on Op—we can require only that A be a regular type. The “semigroupness” will come from the requirement that Op be a SemigroupOperation.

We can use this function to write a version of power for an arbitrary semigroup:

Click here to view code image

template <Regular A, Integer N, SemigroupOperation Op>
// requires (Domain<Op, A>)
A power_semigroup(A a, N n, Op op) {
// precondition(n > 0);
while (!odd(n)) {
a = op(a, a);
n = half(n);
}
if (n == 1) return a;
return power_accumulate_semigroup(a, op(a, a),
half(n - 1), op);
}

As we did before, we can extend the function to monoids by adding an identity element. But since we don’t know in advance which operation will be passed, we have to obtain the identity from the operation:

Click here to view code image

template <Regular A, Integer N, MonoidOperation Op>
// requires(Domain<Op, A>)
A power_monoid(A a, N n, Op op) {
// precondition(n >= 0);
if (n == 0) return identity_element(op);
return power_semigroup(a, n, op);
}

Here are examples of identity_element functions for + and *:

Click here to view code image

template <NoncommutativeAdditiveMonoid T>
T identity_element(std::plus<T>) { return T(0); }

template <MultiplicativeMonoid T>
T identity_element(std::multiplies<T>) { return T(1); }

Each of these functions specifies the type of the object it expects to be called with, but doesn’t name it, since the object is never used. The first one says, “The additive identity is 0.” Of course, there will be different identity elements for different monoids—for example, the maximum value of the type T for min.

* * *

To extend power to groups, we need an inverse operation, which is itself a function of the specified GroupOperation:

Click here to view code image

template <Regular A, Integer N, GroupOperation Op>
// requires(Domain<Op, A>)
A power_group(A a, N n, Op op) {
if (n < 0) {
n = -n;
a = inverse_operation(op)(a);
}
return power_monoid(a, n, op);
}

Examples of inverse_operation look like this:

Click here to view code image

template <AdditiveGroup T>
std::negate<T> inverse_operation(std::plus<T>) {
return std::negate<T>();
}

template <MultiplicativeGroup T>
reciprocal<T> inverse_operation(std::multiplies<T>) {
return reciprocal<T>();
}

STL already has a negate function, but (due to an oversight) has no reciprocal. So we’ll write our own. We’ll use a function object—a C++ object that provides a function declared by operator() and is invoked like a function call, using the name of the object as the function name. To learn more about function objects, see Appendix C.

Click here to view code image

template <MultiplicativeGroup T>
struct reciprocal {
T operator()(const T& x) const {
return T(1) / x;
}
};

This is just a generalization of the multiplicative_inverse function we wrote in the previous section.²

² This time we do not need a precondition preventing x from being zero, because MultiplicativeGroup does not contain a non-invertible zero element. If in practice we have a type such as double that otherwise would satisfy the requirements of MultiplicativeGroup if it did not contain a zero, we can add a precondition to eliminate that case.