Homomorphic computational extensions

Introduction

We consider homomorphisms which are based on computational concerns which are used to transform inefficient or lossy computations over some original domain T into a conceptually equivalent group T over a restricted set of operations.

If the original problem can be solved using these restricted operations, then we may transform T into T and efficiently perform the computations. Sometimes, the entire solution cannot be transformed back to T, but the restricted set of functions or operations may still be sufficient, e.g., evaluating a+c<b+c even though a+c or b+c may not be in the domain of T.

Motivation

Suppose you have a value type T (e.g., double or something more fancy), but when you apply some operations to it, undesirable behavior is produced, e.g., double overflows due to multiplications or loses too much precision due to round-off error.

In the case of a numeric type like double, one option is to use a big number library. However, this approach has some disadvantages:

  1. You may not want to have a dependency on some external library
  2. The big number implementation may be too inefficient.

Assume the computational basis of T is F(T)={,/,+,,<,==}, which can be used to relatively efficiently implement other operations like sin.

Suppose we map T to a modified type T^ such that the computational basis F(T^) is a proper subset of F(T), say F(T^)={,/,<,==}. In exchange for this restriction, the undesired behavior may be avoidable, say multiplications and divisions almost never overflow or underflow. If we do not require the operations in basis F(T), this is a good exchange.

Alternatively, if the computational basis F(T) is needed, it may or may not be possible to map T^ back to T without any loss of information.

Example

Suppose we try to compute a!/b! (ratio of factorials). The end result may be a value in the domain of T, but intermediate values (e.g., a!) may only be in the domain of T^. In this case, we can map the final result back to T without any loss.

The logarithm of the data is a natural candidate for this is mapping double to double^ with the restricted basis

{,/,<,==,=}

such that any of these operations almost never fail and can be performed very efficiently, both in terms of time and space complexity.

Code

template <typename T = double>
struct lg
{
    T k;

    lg(lg const &) = default;

    // default constructs the multiplicative identity
    lg() : k(T(0)) {}

    lg(T x) : k(log(x)) { assert(0 < x); };

    // operator to convert (back) to type T.
    operator T() const { return exp(k); }
};

template <typename T>
auto operator*(lg<T> x, lg<T> y) { return lg<T>{x.k + y.k}; }

template <typename T>
auto operator/(lg<T> x, lg<T> y) { return lg<T>{x.k - y.k}; }

template <typename T>
auto operator<(lg<T> x, lg<T> y) { return x.k < y.k; }

template <typename T>
auto operator==(lg<T> x, lg<T> y) { return x.k == y.k; }
Alex Towell
Alex Towell

Alex Towell has a masters in computer science and a masters in mathematics (statistics) from SIUe.

Related