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
If the original problem can be solved using these restricted operations, then we may transform
Motivation
Suppose you have a value type
In the case of a numeric type like
- You may not want to have a dependency on some external library
- The big number implementation may be too inefficient.
Assume the computational basis of
Suppose we map
Alternatively, if the computational basis
Example
Suppose we try to compute
The logarithm of the data is a natural candidate for this is mapping
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; }