fixedpoint.jp

Implementation of "A Space-efficient Goedel Numbering with Chinese Remainder Theorem" (2010-01-02)

2009/12/27 に書いたように、"A Space-efficient Goedel Numbering with Chinese Remainder Theorem" の実装を行いました。多倍長の算術演算が標準に備わっている Scheme によるものです。

テストとともに http://github.com/tabe/goedel-number/ で公開しました。

コードにしてみると

• 論文中の DecodeNumbers にインデックスについてのバグがある
• 長さが 1000 個以上の integer 列でも現実的な計算時間で処理できる
• 同じ長さの列でも規則正しい integer の並びはより計算時間が短い

ということが分かりました。