zoo

zoo copied to clipboard

Here is the headline test of this PR.

using S = SWAR<8, u32>;
constexpr auto base     = S::fromLaneLiterals({2,   3,  5,  6});
constexpr auto exponent = S::fromLaneLiterals({7,   4,  2,  3});
constexpr auto expected = S::fromLaneLiterals({128, 81, 25, 216});
constexpr auto actual = exponentiation_OverflowUnsafe(base, exponent);
static_assert(expected.value() == actual.value());
CHECK(expected.value() == actual.value());

@thecppzoo would you have some time tomorrow to go over some of this code together?

Thanks for this effort. Part of the value of re-expressing known techniques as what we call "associative iteration" is that this gets us closer to use any advantage we can find, later, about associative operations. For example, we can identify cases in which the "counts" for the iteration are constants and device optimal addition chains for them. Take cryptographic techniques: they may involve exponentiation (of some weird form of multiplication) by a constant: if it is a constant, chances are we could have compilation-time code that comes up with the optimal addition chain...

'overflow unsafe' points out the follow-up to this PR that exponentiation via repeated multiplication via repeated saturating addition is an implementation option.

'overflow unsafe' points out the follow-up to this PR that exponentiation via repeated multiplication via repeated saturating addition is an implementation option.

I don't know, Scott, perhaps it is better to focus on the flow of doubling the precision, saturating, and halving the precision.

In general, the "precision doubling" (casting to a pair of SWARs with double lane width, --how do we call this better than "precision doubling"?--) is a very useful technique, that we ought to illustrate often; see what I did with Lemire's conversion of ASCII to integer, see what the assembler of GLIBC did to implement strlen "masks".