时间戳

首页 > 解决方案 > Prolog中的离散对数

prolog - Prolog中的离散对数

问题描述

我想检查两个程序中的哪一个会停止：

P1() {
   X = 819688;
   while (X != 77) {
      X = (X*12367+3466) mod 4294967296;
   }
}

P2() {
   X = 955725;
   while (X != 77) {
      X = (X*12367+3466) mod 4294967296;
   }
}

由于每次迭代都是一种函数组合，最终导致函数在while循环中的幂，我想离散对数可能会解决这个问题。

围绕解决问题的任何 Prolog 实现？

标签： prologprimespumping-lemmahalting-problem

解决方案

我写了两个版本，一个在 C++ 中，使用动态编程/记忆，另一个在 Prolog 中，没有使用它，所以它们不能直接比较。

C++：

#include <iostream>
#include <vector>

const unsigned long N = 4294967296;

bool terminates(unsigned long x) { // x should be less than N
    std::vector<bool> visited(N, false);

    while(x != 77) {
        if(visited[x])
            return false;
        visited[x] = true;
        x = (x*12367+3466) % N;
    }

    return true;
}

int main() {
    std::cout << terminates(819688) << std::endl; // prints 0
    std::cout << terminates(955725) << std::endl; // prints 1
}

这在 7 秒内完成。

序言：

非记忆版本背后的想法是只循环N+1步骤。如果它在那之前没有终止，它根本不会终止，因为只有N状态。

terminates(X, R) :- terminates(X, 4294967297, R).

terminates(77, _, true) :- !.
terminates(_, 0, false) :- !.
terminates(_, I, false) :- I =< 0, !.
terminates(X, I, R) :-
    I2 is I-1,
    X2 is (X*12367+3466) mod 4294967296,
    terminates(X2, I2, R).

这些查询中的第一个需要更长的时间：

?- terminates(819688, R).
R = false.

?- terminates(955725, R).
R = true.

table显然，使用or可以在 Prolog 中进行assertz记忆，但我认为你会比 C++ 更快地遇到内存问题。C++ 的vector<bool>每个元素只使用 1 位！（unordered_map在这里使用是错误的，因为它的查找速度较慢并且使用更多的内存）

推荐阅读