Discrete Logarithm in Prolog

Question

I would like to check which of the two programs will stop:

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

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

Since each iteration is kind of a function composition, ultimately leading to a power of the function inside the while loop, I guess Discrete Logarithm could maybe solve the problem.

Any Prolog implementations around solving the problem?

Answer 1

I wrote two versions, one in C++, using dynamic programming/memoizing, and another in Prolog, not using it, so they are not directly comparable.

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
}

This finishes in 7s.

Prolog:

The idea behind the non-memoizing version is to loop only N+1 steps. If it doesn't terminate before then, it doesn't terminate at all, since there are only N states.

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).

The first of these queries takes much longer:

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

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

One could do memoizing in Prolog, obviously, using table or assertz, but I think you would run into memory problems much sooner than C++. C++'s vector<bool> uses just 1 bit per element! (Using unordered_map here would be a mistake, as it has slower lookup and uses much more memory)

Answer 2

We can compare performance of brute force with performance of Shanks Algorithm. I made some tests, and it seems that for the above example brute force seems to be not feasible for the non-terminating program. It is not yet finished after a minute:

/* 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 Algorithm has a common base line effort to intialize that cache which indexes half of the bits of the modulus. But it can then decide both programs in relatively short time and also correctly. Interestingly it even beats brute force in the terminating program:

/* 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 .

Open Source:

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