Egyptian algorithm ideas

EgytianAlgorithmIdeas.md

Imagine there is a template that tells you from an operation type a class-function "operate", and a type called "inverse" which gives you the inverse operation:

template<typename Operation>
struct OperatorTraits {
    template<typename Argument>
    static Argument operate(Argument x, Argument y);

    using Inverse = // ...
};

Also assume there are functions called half and isOdd that do the obvious things, then:

template<typename Operation, typename Argument>
Argument egyptian(Argument x, Argument y) {
    Argument
        delta = x,
        result = 0; // the argument type must accept assignment from 0
    while(0 != y) { // the argument must be comparable to 0
        if(isOdd(y)) { result = OperatorTraits<Operation>::operate(result, delta); }
        delta = OperatorTraits<Operation>::operate(delta, delta);
        y = half(y);
    }
    return result;
}

With that code, you can do:

struct Multiplication {};
struct Substraction { template<typename A> static execute(A x, A y) { return x - y; } };
struct Exponentiation {};

template<> struct OperatorTraits<Multiplication> {
    template<typename A>
    static A operate(A x, A y) { return x + y; }

    using Inverse = Substraction;
};

template<> struct OperatorTraits<Exponentiation> {
    template<typename A>
    static A operate(A x, A y) { return egyptian<Multiplication>(x, y); }
}

template<> struct OperatorTraits<Substraction>; // defined somewhere

template<typename A>
A egyptianMultiplication(A x, A y) { return egyptian<Multiplication>(x, y); }

template<typename A>
A egyptianExponentiation(A x, A y) { return egyptian<Exponentiation>(x, y); }

Notice the code will let you have an argument of some type that could represent "integer modulo N", and without any extra work (the type should implement the operator* and operator+) you already have the Egyptian algorithm available!

Now, with respect of the idea that operating with something that resembles 2^n - 1 is to operate with 2^n and do the inverse operation once;

template<typename Operation, unsigned PowerOfTwo>
struct EgyptianOfPowerOfTwoMinus1 { // specific case for the Constant being 15
    template<typename A>
    static A execute(A x) {
        return OperatorTraits<Operation>::Inverse::execute(egyptian<Operation>(x, 1 << PowerOfTwo), x);
    }
};