檜山正幸のキマイラ飼育記 このページをアンテナに追加 RSSフィード Twitter

キマイラ・サイトは http://www.chimaira.org/です。
トラックバック/コメントは日付を気にせずにどうぞ。
連絡は hiyama{at}chimaira{dot}org へ。
蒸し返し歓迎!
このブログの更新は、Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama
ところで、アーカイブってけっこう便利ですよ。

2015-12-02 (水)

コンピュータは「掛け算は足し算とする」を理解できるか

| 09:42 | コンピュータは「掛け算は足し算とする」を理解できるかを含むブックマーク

お手軽で実用的なジェネリックスへの道は遠い」で演算子オーバーロードの話をしました。演算子オーバーロードが欲しかったひとつの理由は、トロピカル代数の計算をコンピュータで出来ないかな、と思ったことです。例えば、トロピカル代数*1のひとつであるmin-plus半環では、次のような計算になります。

  • 1 + 1 = 1
  • 2 + 3 = 2
  • 2 * 3 = 5
  • 2 * 0 = 2
  • 3 + ∞ = 3
  • 3 * ∞ = ∞

こんな計算を、そのまんま(関数呼び出しとかにしないで)書けたらいいな、ということです。C++11でやってみます。

min-plus半環

min-plus半環については、(max-plus半環と共に)次の記事で紹介しています。

その応用例のひとつは:

min-plus半環での計算は、普通の計算とは違います。その対応をまとめておきます。

min-plus半環における役割 実際には
足し算 min(小さい方)
掛け算 足し算
0

min-plus半環も半環(足し算と掛け算が出来る)ので、行列計算とかは、普通の数とまったく同じく定義できます。完全なジェネリックスのもとでは、普通の行列計算ライブラリがmin-plus係数でも使えるはずです。まー、「はず」なだけだけど。

min-plus係数の行列計算により、(一般化)距離空間の実験や確認とかもできちゃうはず(「はず」なだけ)。

行列計算はともかくとして、min-plus半環そのものを定義します。

C++11でうまくいく

結果を先に言うと、C++11でほぼ期待どおりになります。

// tropical.cpp

//
// ... 途中省略 ...
//

/*
 * デモ
 */

// 略記用
MinPlus operator"" _mp(long double x) {
  MinPlus t = x;
  return t;
}

// 略記用
MinPlus operator"" _mp(unsigned long long int x) {
  MinPlus t = x;
  return t;
}

// 略記用
MinPlus const inf = MinPlus::Infinity;

// 計算してみる
int main()
{

  // 1 + 1 = 1
  std::cout << "1 + 1 = "
	    << 1_mp + 1 << std::endl;
  // 2 + 3 = 2
  std::cout << "2 + 3 = "
    	    << 2 + 3_mp << std::endl;
  // 2 * 3 = 5
  std::cout << "2 * 3 = "
    	    << 2 * 3_mp << std::endl;
  // 2 * 0 = 2
  std::cout << "2 * 0 = "
    	    << 2 * 0_mp << std::endl;
  // 3 + ∞ = 3
  std::cout << "3 + ∞ = "
    	    << 3 + inf << std::endl;
  // 3 * ∞ = ∞
  std::cout << "3 * ∞ = "
    	    << 3 * inf << std::endl;
  return 0;
}

コンパイル&実行。

$ g++ tropical.cpp

$ ./a.exe
1 + 1 = 1
2 + 3 = 2
2 * 3 = 5
2 * 0 = 2
3 + ∞ = 3
3 * ∞ = ∞

$

ソースコード内で 1 + 1 と書けば、さすがにこれは2になります。数値をmin-plus半環の要素だと思って書いても、コンパイラは心のなかまでは察してくれません。「これはmin-plus半環の要素だよ」と示すために、C++のユーザー定義リテラルというものを使ってみました。1_mp のように_mp接尾辞を付けるとmin-plusな要素と解釈します。

使ってはみたけど、ユーザー定義リテラルってあんまり便利じゃないですね。mp(1) のように普通の関数で書いても同じ、つーか、普通の関数のほうが簡単。

それはともかく; 二項演算の場合、どっちか片方の項に_mpを付ければ、もう一方は型変換してmin-plus要素に揃えてくれるようです。式のなかで、1つでもmin-plus要素だと明示すれば、他は普通の数値で書いても大丈夫。(1_mp + 3 + inf) * 5 + 3 * 2 とかも期待どおりに計算してくれます。C++11の構文解析と型変換はよくできてますね、関心しました。

でも、対話的インタプリタではないので、式を手で入力してその場で試すことが出来ないのですよね。実験用には、これは痛い。世の中、なかなかうまくいかんもんだわ。


この下にソースコード

// tropical.cpp

#include <stdexcept>
#include <iostream>

class MinPlus {
  double _val;
  static const double _internal_infinity;
  static double _min(double x, double y);
  static double _sum(double x, double y);

public:
  static const MinPlus Infinity;
  static const MinPlus Zero;
  static const MinPlus One;

  MinPlus(double x);
  MinPlus();

  bool is_infnity() const {return _val == _internal_infinity;}
  double val() const {return _val;}
  void val(double x);
  MinPlus& operator +=(MinPlus m);
  MinPlus& operator *=(MinPlus m);

};

/* 
 * 定数の定義 
 */
const double MinPlus::_internal_infinity = -1;
const MinPlus MinPlus::Infinity = MinPlus::_internal_infinity;

// MinPlusの零とは無限大のこと
const MinPlus MinPlus::Zero = MinPlus::Infinity;
// MinPlusの一とは0のこと
const MinPlus MinPlus::One = 0;

/*
 * 内部使用の関数
 */

// 無限大を考慮したmin
double MinPlus::_min(double x, double y) {
  if (x == _internal_infinity) return y;
  if (y == _internal_infinity) return x;
  if (x <= y) return x;
  return y;
}

// 無限大を考慮した和
double MinPlus::_sum(double x, double y) {
  if (x == _internal_infinity) return _internal_infinity;
  if (y == _internal_infinity) return _internal_infinity;
  return x + y;
}

/*
 * 公開する関数
 */

// 値の設定
void MinPlus::val(double x) {
  if (x == _internal_infinity || x >= 0) {
    _val = x;
  } else {
    throw std::out_of_range("Invalid MinPlus value");
  }
}

// コンストラクタ
MinPlus::MinPlus(double x) {
  val(x);
}

// デフォルトコンストラクタ
MinPlus::MinPlus() {
  _val = _internal_infinity;
}

// 足し算して代入: 足し算は小さいほう
MinPlus& MinPlus::operator +=(MinPlus m) {
  double min = _min(_val, m._val) ;
  _val = min;
  return *this;
}

// 掛け算して代入: 掛け算は足し算
MinPlus& MinPlus::operator *=(MinPlus m) {
  double sum = _sum(_val, m._val) ;
  _val = sum;
  return *this;
}

// 値の足し算
MinPlus operator+(MinPlus m, MinPlus n) {
  MinPlus t = m;
  return t += n;
}

// 値の掛け算
MinPlus operator*(MinPlus m, MinPlus n) {
  MinPlus t = m;
  return t *= n;
}

// 書き出し
std::ostream& operator<<(std::ostream &out, MinPlus m) {
  if (m.is_infnity()) {
    return out << "∞";
  } else {
    return out << m.val();
  }
}

/*
 * デモ
 */

// 略記用
MinPlus operator"" _mp(long double x) {
  MinPlus t = x;
  return t;
}

// 略記用
MinPlus operator"" _mp(unsigned long long int x) {
  MinPlus t = x;
  return t;
}

// 略記用
MinPlus const inf = MinPlus::Infinity;

// 計算してみる
int main()
{
  std::cout << (1_mp + 3 + inf) * 5 + 3 * 2<< std::endl;
  // 1 + 1 = 1
  std::cout << "1 + 1 = "
	    << 1_mp + 1 << std::endl;
  // 2 + 3 = 2
  std::cout << "2 + 3 = "
    	    << 2 + 3_mp << std::endl;
  // 2 * 3 = 5
  std::cout << "2 * 3 = "
    	    << 2 * 3_mp << std::endl;
  // 2 * 0 = 2
  std::cout << "2 * 0 = "
    	    << 2 * 0_mp << std::endl;
  // 3 + ∞ = 3
  std::cout << "3 + ∞ = "
    	    << 3 + inf << std::endl;
  // 3 * ∞ = ∞
  std::cout << "3 * ∞ = "
    	    << 3 * inf << std::endl;
  return 0;
}

*1:広義のトロピカル代数=エキゾチック代数のことです。

kmizushimakmizushima 2015/12/05 03:21 こんにちは。面白そうだったので、対話環境で試せるのをScalaで
作ってみました。もしよろしければ試して感想などいただければ。

https://github.com/kmizu/tropical

m-hiyamam-hiyama 2015/12/05 11:26 kmizushimaさん、ありがとうございます。
これを見る限り C++⊆Scala ですね。素直に翻訳できるし、しかも対話的な実行が可能だし。
対話的なのはいいなー。
ちなみに、C++インタプリタはインストール失敗(泣) http://d.hatena.ne.jp/m-hiyama-memo/20151205/1449281670

nowokaynowokay 2015/12/05 21:10 一番最初の例での2+3=3というのは、2+3=2でしょうか?

nowokaynowokay 2015/12/05 21:11 と、ソースコードのコメントも・・・

m-hiyamam-hiyama 2015/12/06 17:17 nowokayさん、
間違いです。直しました、ありがとうございます。