summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--utils/logval.h87
-rw-r--r--utils/logval_test.cc10
-rwxr-xr-xutils/max_plus.h203
-rwxr-xr-xutils/semiring.h74
4 files changed, 353 insertions, 21 deletions
diff --git a/utils/logval.h b/utils/logval.h
index b337cf0e..868146de 100644
--- a/utils/logval.h
+++ b/utils/logval.h
@@ -8,20 +8,32 @@
#include <cstdlib>
#include <cmath>
#include <limits>
+#include "semiring.h"
+//TODO: template for supporting negation or not - most uses are for nonnegative "probs" only; probably some 10-20% speedup available
template <class T>
class LogVal {
public:
- LogVal() : s_(), v_(-std::numeric_limits<T>::infinity()) {}
+ typedef LogVal<T> Self;
+
+ LogVal() : s_(), v_(LOGVAL_LOG0) {}
explicit LogVal(double x) : s_(std::signbit(x)), v_(s_ ? std::log(-x) : std::log(x)) {}
+ LogVal(init_minus_1) : s_(true),v_(0) { }
+ LogVal(init_1) : s_(),v_(0) { }
+ LogVal(init_0) : s_(),v_(LOGVAL_LOG0) { }
LogVal(int x) : s_(x<0), v_(s_ ? std::log(-x) : std::log(x)) {}
LogVal(unsigned x) : s_(0), v_(std::log(x)) { }
LogVal(double lnx,bool sign) : s_(sign),v_(lnx) {}
- static LogVal<T> exp(T lnx) { return LogVal(lnx,false); }
+ LogVal(double lnx,init_lnx) : s_(),v_(lnx) {}
+ static Self exp(T lnx) { return Self(lnx,false); }
+
+ // maybe the below are faster than == 1 and == 0. i don't know.
+ bool is_1() const { return v_==0&&s_==0; }
+ bool is_0() const { return v_==LOGVAL_LOG0; }
- static LogVal<T> One() { return LogVal(1); }
- static LogVal<T> Zero() { return LogVal(); }
- static LogVal<T> e() { return LogVal(1,false); }
+ static Self One() { return Self(1); }
+ static Self Zero() { return Self(); }
+ static Self e() { return Self(1,false); }
void logeq(const T& v) { s_ = false; v_ = v; }
std::size_t hash_impl() const {
@@ -29,8 +41,21 @@ class LogVal {
return hash_value(v_)+s_;
}
- LogVal& operator+=(const LogVal& a) {
- if (a.v_ == -std::numeric_limits<T>::infinity()) return *this;
+ // just like std::signbit, negative means true. weird, i know
+ bool signbit() const {
+ return s_;
+ }
+ friend inline bool signbit(Self const& x) { return x.signbit(); }
+
+ Self& besteq(const Self& a) {
+ assert(!a.s_ && !s_);
+ if (a.v_ < v_)
+ v_=a.v_;
+ return *this;
+ }
+
+ Self& operator+=(const Self& a) {
+ if (a.is_0()) return *this;
if (a.s_ == s_) {
if (a.v_ < v_) {
v_ = v_ + log1p(std::exp(a.v_ - v_));
@@ -48,31 +73,31 @@ class LogVal {
return *this;
}
- LogVal& operator*=(const LogVal& a) {
+ Self& operator*=(const Self& a) {
s_ = (s_ != a.s_);
v_ += a.v_;
return *this;
}
- LogVal& operator/=(const LogVal& a) {
+ Self& operator/=(const Self& a) {
s_ = (s_ != a.s_);
v_ -= a.v_;
return *this;
}
- LogVal& operator-=(const LogVal& a) {
- LogVal b = a;
- b.invert();
+ Self& operator-=(const Self& a) {
+ Self b = a;
+ b.negate();
return *this += b;
}
- // LogVal(fabs(log(x)),x.s_)
- friend LogVal abslog(LogVal x) {
+ // Self(fabs(log(x)),x.s_)
+ friend Self abslog(Self x) {
if (x.v_<0) x.v_=-x.v_;
return x;
}
- LogVal& poweq(const T& power) {
+ Self& poweq(const T& power) {
#if LOGVAL_CHECK_NEG
if (s_) {
std::cerr << "poweq(T) not implemented when s_ is true\n";
@@ -83,26 +108,50 @@ class LogVal {
return *this;
}
- void invert() { s_ = !s_; }
+ //remember, s_ means negative.
+ inline bool lt(Self const& o) const {
+ return s_ ? (!o.s_ || o.v_<v_) : (o.s_ || v_<o.v_);
+ }
+ inline bool gt(Self const& o) const {
+ return s_ ? (o.s_ && v_<o.v_) : (!o.s_ && o.v_<v_);
+ }
- LogVal pow(const T& power) const {
- LogVal res = *this;
+ Self operator-() const {
+ return Self(v_,-s_);
+ }
+ void negate() { s_ = !s_; }
+
+ Self inverse() const { return Self(-v_,s_); }
+
+ Self pow(const T& power) const {
+ Self res = *this;
res.poweq(power);
return res;
}
- LogVal root(const T& root) const {
+ Self root(const T& root) const {
return pow(1/root);
}
operator T() const {
if (s_) return -std::exp(v_); else return std::exp(v_);
}
+ T as_float() const {
+ if (s_) return -std::exp(v_); else return std::exp(v_);
+ }
bool s_;
T v_;
};
+template <class T>
+struct semiring_traits<LogVal<T> > : default_semiring_traits<LogVal<T> > {
+ static const bool has_logplus=true;
+ static const bool has_besteq=true;
+ static const bool has_subtract=true;
+ static const bool has_negative=true;
+};
+
// copy elision - as opposed to explicit copy of LogVal<T> const& o1, we should be able to construct Logval r=a+(b+c) as a single result in place in r. todo: return std::move(o1) - C++0x
template<class T>
LogVal<T> operator+(LogVal<T> o1, const LogVal<T>& o2) {
diff --git a/utils/logval_test.cc b/utils/logval_test.cc
index 1a23177d..4aa452f2 100644
--- a/utils/logval_test.cc
+++ b/utils/logval_test.cc
@@ -26,13 +26,19 @@ TEST_F(LogValTest,Order) {
EXPECT_FALSE(a < a);
}
-TEST_F(LogValTest,Invert) {
+TEST_F(LogValTest,Negate) {
LogVal<double> x(-2.4);
LogVal<double> y(2.4);
- y.invert();
+ y.negate();
EXPECT_FLOAT_EQ(x,y);
}
+TEST_F(LogValTest,Inverse) {
+ LogVal<double> x(1/2.4);
+ LogVal<double> y(2.4);
+ EXPECT_FLOAT_EQ(x,y.inverse());
+}
+
TEST_F(LogValTest,Minus) {
LogVal<double> x(12);
LogVal<double> y(2);
diff --git a/utils/max_plus.h b/utils/max_plus.h
new file mode 100755
index 00000000..5136b881
--- /dev/null
+++ b/utils/max_plus.h
@@ -0,0 +1,203 @@
+#ifndef MAX_PLUS_H_
+#define MAX_PLUS_H_
+
+#include
+// max-plus algebra. ordering a > b really means that (i.e. default a<b sorting will do worst (closest to 0) first. so get used to passing predicates like std::greater<MaxPlus<T> > around
+// x+y := max{x,y}
+// x*y := x+y
+// 0 := -inf
+// 1 := 0
+// additive inverse does not, but mult. does. (inverse()) and x/y := x-y = x+y.inverse()
+//WARNING: default order is reversed, on purpose, i.e. a<b means a "better than" b, i.e. log(p_a)>log(p_b). sorry. defaults in libs are to order ascending, but we want best first.
+
+#include <boost/functional/hash.hpp>
+#include <iostream>
+#include <cstdlib>
+#include <cmath>
+#include <limits>
+#include "semiring.h"
+#define TROPICAL_DEBUG(x)
+#undef LOGVAL_LOG0
+#define LOGVAL_LOG0 -std::numeric_limits<T>::infinity()
+
+template <class T>
+class MaxPlus {
+ public:
+ typedef MaxPlus<T> Self;
+ MaxPlus() : v_(LOGVAL_LOG0) {}
+ explicit MaxPlus(double x) : v_(std::log(x)) {}
+ MaxPlus(init_1) : v_(0) { }
+ MaxPlus(init_0) : v_(LOGVAL_LOG0) { }
+ MaxPlus(int x) : v_(std::log(x)) {}
+ MaxPlus(unsigned x) : v_(std::log(x)) { }
+ MaxPlus(double lnx,bool sign) : v_(lnx) { TROPICAL_DEBUG(assert(!sign)); }
+ MaxPlus(double lnx,init_lnx) : v_(lnx) {}
+ static Self exp(T lnx) { return MaxPlus(lnx,false); }
+
+ // maybe the below are faster than == 1 and == 0. i don't know.
+ bool is_1() const { return v_==0; }
+ bool is_0() const { return v_==LOGVAL_LOG0; }
+
+ static Self One() { return Self(init_1()); }
+ static Self Zero() { return Self(init_0()); }
+ static Self e() { return Self(1,false); }
+ void logeq(const T& v) { v_ = v; }
+ bool signbit() const { return false; }
+
+ std::size_t hash_impl() const {
+ using namespace boost;
+ return hash_value(v_);
+ }
+
+ Self& logpluseq(const Self& a) {
+ if (a.is_0()) return *this;
+ if (a.s_ == s_) {
+ if (a.v_ < v_) {
+ v_ = v_ + log1p(std::exp(a.v_ - v_));
+ } else {
+ v_ = a.v_ + log1p(std::exp(v_ - a.v_));
+ }
+ } else {
+ if (a.v_ < v_) {
+ v_ = v_ + log1p(-std::exp(a.v_ - v_));
+ } else {
+ v_ = a.v_ + log1p(-std::exp(v_ - a.v_));
+ s_ = !s_;
+ }
+ }
+ return *this;
+ }
+
+ Self& besteq(const Self& a) {
+ if (a.v_ < v_)
+ v_=a.v_;
+ return *this;
+ }
+
+ Self& operator+=(const Self& a) {
+ if (a.v_ < v_)
+ v_=a.v_;
+ return *this;
+ }
+
+ Self& operator*=(const Self& a) {
+ v_ += a.v_;
+ return *this;
+ }
+
+ Self& operator/=(const Self& a) {
+ v_ -= a.v_;
+ return *this;
+ }
+
+ // Self(fabs(log(x)),x.s_)
+ friend Self abslog(Self x) {
+ if (x.v_<0) x.v_=-x.v_;
+ return x;
+ }
+
+ Self& poweq(const T& power) {
+ v_ *= power;
+ return *this;
+ }
+
+ Self inverse() const {
+ return Self(-v_,false);
+ }
+
+ Self pow(const T& power) const {
+ Self res = *this;
+ res.poweq(power);
+ return res;
+ }
+
+ Self root(const T& root) const {
+ return pow(1/root);
+ }
+
+// copy elision - as opposed to explicit copy of Self const& o1, we should be able to construct Logval r=a+(b+c) as a single result in place in r. todo: return std::move(o1) - C++0x
+ friend inline operator+(Self a,Self const& b) {
+ a+=b;
+ return a;
+ }
+ friend inline operator*(Self a,Self const& b) {
+ a*=b;
+ return a;
+ }
+ friend inline operator/(Self a,Self const& b) {
+ a/=b;
+ return a;
+ }
+ friend inline T log(Self const& a) {
+ return a.v_;
+ }
+ friend inline T pow(Self const& a,T const& e) {
+ return a.pow(e);
+ }
+
+ // intentionally not defining an operator < or operator > - because you may want to default (for library convenience) a<b means a better than b (i.e. gt)
+ inline bool lt(Self const& o) const {
+ return v_<o.v_;
+ }
+ inline bool gt(Self const& o) const {
+ return o.v_<v_;
+ }
+ friend inline bool operator==(Self const& lhs, Self const&rhs) {
+ return lhs.v_ == rhs.v_;
+ }
+ friend inline bool operator!=(Self const& lhs, Self const&rhs) {
+ return lhs.v_ != rhs.v_;
+ }
+/*
+ operator T() const {
+ return std::exp(v_);
+ }
+*/
+ T as_float() const {
+ return std::exp(v_);
+ }
+
+ T v_;
+};
+
+template <class T>
+struct semiring_traits<MaxPlus<T> > : default_semiring_traits<MaxPlus<T> > {
+ static const bool has_logplus=true;
+ static const bool has_besteq=true;
+};
+
+
+template <class T>
+
+#if 0
+template <class T>
+bool operator<=(const MaxPlus<T>& lhs, const MaxPlus<T>& rhs) {
+ return (lhs.v_ <= rhs.v_);
+}
+
+template <class T>
+bool operator>(const MaxPlus<T>& lhs, const MaxPlus<T>& rhs) {
+ return (lhs.v_ > rhs.v_);
+}
+
+template <class T>
+bool operator>=(const MaxPlus<T>& lhs, const MaxPlus<T>& rhs) {
+ return (lhs.v_ >= rhs.v_);
+}
+#endif
+
+
+template <class T>
+std::size_t hash_value(const MaxPlus<T>& x) { return x.hash_impl(); }
+
+template <class T>
+bool operator==(const MaxPlus<T>& lhs, const MaxPlus<T>& rhs) {
+ return (lhs.v_ == rhs.v_) && (lhs.s_ == rhs.s_);
+}
+
+template <class T>
+bool operator!=(const MaxPlus<T>& lhs, const MaxPlus<T>& rhs) {
+ return !(lhs == rhs);
+}
+
+#endif
diff --git a/utils/semiring.h b/utils/semiring.h
new file mode 100755
index 00000000..5007994c
--- /dev/null
+++ b/utils/semiring.h
@@ -0,0 +1,74 @@
+#ifndef SEMIRING_H
+#define SEMIRING_H
+
+struct init_1 { };
+struct init_0 { };
+struct init_minus_1 { };
+struct init_lnx { };
+
+#undef LOGVAL_LOG0
+#define LOGVAL_LOG0 -std::numeric_limits<T>::infinity()
+
+/* if T is a semiring,
+
+ then constructors:
+ T() := T(init_0)
+ T(init_0()) := semiring 0
+ T(init_1()) := semiring 1
+ (copy constructor, equality, assignment also)
+ T(other initializers) - semiring dependent e.g. T(double lnx,bool is_negative); T(double lnx,init_lnx); T(double x) := T(log(fabs(x)),signbit(x))
+
+ optional: T(init_minus_1()) := -1, assuming additive inverse
+
+ if T a,b;
+ then a+b := semiring + - commutative monoid with 0
+ a*b := semiring * with identity 1 - monoid with 1
+ * distributes over +
+ 0*a=a*0=0
+
+ also a+= a*=
+
+ optional: commutative multiplication (commutative semiring)
+
+ non-semiring concepts you may also have:
+ order (a<b)
+ logplus(a,b), logpluseq(a,b), T::exp(lnx), log(a)
+ a-b, usually with a-b := a+T(init_minus_1())*b
+ a.inverse() : a*a.inverse() = 1
+ a.left_inverse() : a.left_inverse()*a = 1 (define if not commuatative and it exists)
+ signbit(a) := a<0
+ pow(a,2) := a*a
+ pow(a,2.3)
+*/
+
+template <class T>
+struct default_semiring_traits {
+ static const T One;
+ static const T Zero;
+ static inline bool is_1(T const& x) { return x==One; }
+ static inline bool is_0(T const& x) { return x==Zero; }
+ static const bool commutative=true;
+ static const bool has_inverse=true; // multiplicative, that is
+// static const bool has_left_inverse=false; // note: not intended to imply that inverse isn't a left_inverse
+ static const bool has_order=false; // we usually don't defined < > <= >= although == != must exist
+ static const bool has_ltgt=true; // but we will probably give a a.lt(b) x.gt(y) which are a<b and x>y resp.
+ static const bool has_subtract=false; // e.g. tropical can't do this
+ static const bool has_logplus=false;
+ static const bool has_pow=true;
+ static const bool has_init_float=true; // implies you can T a; T a.as_float() as well as T(float f)
+ static const bool has_negative=false;
+ static const bool has_ostream=false; // we could provide these but for some reason we usually don't
+ static const bool has_istream=false;
+};
+
+template <class T>
+struct semiring_traits : default_semiring_traits<T> {
+};
+
+
+template <class T>
+const T default_semiring_traits<T>::One=init_1();
+template <class T>
+const T default_semiring_traits<T>::Zero=init_0();
+
+#endif
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-11 01:45:14 +0000