-2

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

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 实现？

4

2 回答 2

2

我写了两个版本，一个在 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在这里使用是错误的，因为它的查找速度较慢并且使用更多的内存）

于 2020-12-09T01:43:27.900 回答
0

我们可以将蛮力的性能与香克斯算法的性能进行比较。我做了一些测试，对于上面的例子，蛮力似乎对于非终止程序是不可行的。一分钟后还没有完成：

/* Brute Force */
?- time(call_with_time_limit(60,terminates(819688,N))).
% 505,081,233 inferences, 58.984 CPU in 60.000 seconds (98% CPU, 8562967 Lips)
ERROR: Unhandled exception: Time limit exceeded

?- time(terminates(955725,N)).
% 4,194,305 inferences, 0.469 CPU in 0.501 seconds (94% CPU, 8947851 Lips)
N = 2097151.

Shanks 算法有一个共同的基线努力来初始化该缓存，该缓存索引模数的一半位。但是它可以在相对较短的时间内正确地决定这两个程序。有趣的是，它甚至在终止程序中击败了蛮力：

/* Shanks Algorithm */
?- time(solve(819688, N)).
% 1,179,836 inferences, 0.196 CPU in 0.205 seconds (95% CPU, 6024828 Lips)
false.

?- time(solve(955725, N)).
% 590,289 inferences, 0.137 CPU in 0.144 seconds (95% CPU, 4296792 Lips)
N = 2097151 .

开源：

Jekejeke Prolog Shanks：
https
://gist.github.com/jburse/dfaa1fd638f3397ae83879c124b37f8b#file-shanks-pl SWI-Prolog Shanks：
https:
//gist.github.com/jburse/dfaa1fd638f3397ae83879c124b37f8b#file-shanksswi-pl MaxB Brute Force ：
https ://gist.github.com/jburse/dfaa1fd638f3397ae83879c124b37f8b#file-pumping-pl

于 2020-12-11T12:36:58.620 回答