"Integers modulo n" - good template & op. overloading example

[ajbennieston]

e.g. n as template param.

[ajbennieston]

This could become quite complicated. There are a lot of design issues to make this work correctly (and several possible definitions of "working correctly"). For instance, the code below is one possible implementation. It uses ab = (a%N)(b%N) rather than a_b = (a_b)%N, and probably has a bunch of other things which aren't ideal.

#include <iostream>

template<unsigned long N, typename Underlying=int> class ModularInt
{
    public:
        ModularInt()
            : value(0) {}

        ModularInt(Underlying x)
            : value(x % N) {}

        template<typename T> ModularInt(const ModularInt<N, T>& other)
            : value(other.val()) {}

        template<typename T> ModularInt& operator=(const ModularInt<N, T>& other)
        {
            if (&other != this)
                value = other.val();
            return *this;
        }

        ModularInt& operator=(Underlying x)
        {
            value = x % N;
        }

        ModularInt& operator+=(const ModularInt& y)
        {
            value = (value + y.value) % N;
            return *this;
        }

        ModularInt& operator*=(const ModularInt& y)
        {
            value = (value * y.value) % N;
            return *this;
        }

        ModularInt& operator++()
        {
            value = (value + 1) % N;
            return *this;
        }

        ModularInt operator++(int)
        {
            ModularInt tmp(value);
            value = (value + 1) % N;
            return tmp;
        }

        Underlying val() const { return value; }

        friend std::ostream& operator<<(std::ostream& s, const ModularInt& v)
        {
            s << v.value;
            return s;
        }
    private:
        Underlying value;
};

template<unsigned long N, typename T> ModularInt<N, T> operator+(ModularInt<N, T> lhs, const ModularInt<N, T>& rhs)
{
    return lhs += rhs;
}

template<unsigned long N, typename T, typename U> ModularInt<N, T> operator+(ModularInt<N, T> lhs, U rhs)
{
    return lhs += ModularInt<N, T>(rhs);
}

template<unsigned long N, typename T, typename U> ModularInt<N, T> operator+(U lhs, ModularInt<N, T> rhs)
{
    return rhs += ModularInt<N, T>(lhs);
}

template<unsigned long N, typename T> ModularInt<N> operator*(ModularInt<N, T> lhs, const ModularInt<N, T>& rhs)
{
    return lhs *= rhs;
}

template<unsigned long N, typename T, typename U> ModularInt<N, T> operator*(ModularInt<N, T> lhs, U rhs)
{
    return lhs += ModularInt<N, T>(rhs);
}

template<unsigned long N, typename T, typename U> ModularInt<N, T> operator*(U lhs, ModularInt<N, T> rhs)
{
    return rhs += ModularInt<N, T>(lhs);
}

int main()
{
    ModularInt<5> a;
    for (int x = 0; x < 10; ++x)
    {
        // Test that the value wraps round: 8..9..0..1..
        std::cout << ++a << "\n";
    }

    std::cout << "---\n";

    for (int x = 0; x < 10; ++x)
    {
        // Test that the value wraps round: 8..9..0..1..
        // Using postfix increment
        std::cout << a++ << "\n";
    }

    std::cout << "---\n";

    ModularInt<5> b = 3;
    ModularInt<5> c = 3;
    std::cout << b + c << "\n"; // Test that the result wraps
    std::cout << b + 3 << "\n"; // Test that we can use plain ints too

    std::cout << "---\n";

    ModularInt<32> x = 2;
    ModularInt<32> y = 10;
    // Test multiplication of two ModularInts, and of a ModularInt with a plain int
    std::cout << x * y << " " <<  x * y * 2 << "\n";

    std::cout << "---\n";

    // Test a larger underlying integer type
    ModularInt<1UL << 39, unsigned long> big = 1UL << 38;
    std::cout << big << "\n";

    std::cout << "---\n";

    // Test wrapping with the larger type
    ModularInt<1UL << 39, unsigned long> big2 = 1UL << 37;
    ModularInt<1UL << 39, unsigned long> big3 = big;
    for (int n = 0; n < 10; ++n)
    {
        big3 += big2 + (1UL << 20);
        std::cout << big3 << "\n";
    }

    std::cout << "---\n";

    // Test retrieval of the integer value
    int z = y.val();
    std::cout << z << "\n";

    std::cout << "---\n";

    return 0;
}

[ajbennieston]

Due to the complexity of this, it is probably better suited to a longer, more in-depth section that goes beyond the content in the current set of notes, and focuses more on larger design and implementation issues.

[ajbennieston]

N.B. Other approaches exist, e.g. keeping the integer un-wrapped, and using %N only for output operation. This brings its own set of problems (e.g. integer overflow causes wrapping at a different place to N).