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?

There's no magic discrete logarithm solver that can quickly solve every similar problem. Since this is based on an LCG there's an efficient algorithm to compute any "power" of the function; see [this](https://www.nayuki.io/page/fast-skipping-in-a-linear-congruential-generator) for one nice explanation and some non-Prolog code. From this, and a description of the [baby-step giant-step algorithm](https://en.wikipedia.org/wiki/Baby-step_giant-step) you should be able to construct an efficient solution. — President James K. Polk, Dec 09 '20 at 00:41
THere is paper by F. Brown, "Random Number Generation with Arbitrary Stride," Trans. Am. Nucl. Soc. (Nov. 1994), which implements jump ahead for LCG in O(log(N)) time, which is basically exponentiation. Code in Python is https://stackoverflow.com/questions/56985271/linear-congruential-generator-how-to-choose-seeds-and-statistical-tests. I have no Prolog experience, so no help with the code — Severin Pappadeux, Dec 09 '20 at 03:29
@MostowskiCollapse *"Halting problem refers to problems where the program state space is infinite."* Not true. [To quote Wikipedia](https://en.wikipedia.org/wiki/Halting_problem), "**The halting problem** is theoretically decidable for linear bounded automata (LBAs) or deterministic machines with finite memory." — MWB, Dec 12 '20 at 19:55
@MostowskiCollapse *"You can read the stackoverflow description of the "halting-problem" ... typically a Turing machine"* Well, "typically" implies "not always", and I already pointed you to where Wikipedia says you are incorrect. And even Turing machine programs can, and often do, only encounter a finite number of states. Your question shows two examples of such. — MWB, Dec 13 '20 at 06:22

MWB · Answer 1 · 2020-12-09T02:05:08.510

3

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)

edited Dec 09 '20 at 02:05

answered Dec 09 '20 at 01:43

MWB

11,740
6
46
91

2

@MostowskiCollapse It sounds like you had a different question in mind than the one you actually asked. – MWB Dec 09 '20 at 10:01
@MaxB : Even in C++ non-memoizing is more efficient. On my system the C++ version just counting down N+1 steps is taking less than half the time with negligible memory. Memoizing does not seem to be helping. – rajashekar Dec 09 '20 at 13:28
@rajashekar That probably depends on the input. Try `12345`. The Prolog version is non-memoizing, so I didn't feel like there was a need to demo it in C++ too, especially since the implementation is trivial. – MWB Dec 09 '20 at 20:48
@MostowskiCollapse Wikipedia says `However, no efficient method is known for computing (discrete logarithms) in general`. In any case, I answered the question that *was* posted. Using discrete logarithm was clearly just an unhelpful suggestion. – MWB Dec 09 '20 at 21:12
2

@MaxB (meta:) quotations are to be included between double- (or single-) quotation marks (sometimes other markings are used, like << and >>). *back-quotes* though, a.k.a. backticks, *indicate code snippets*, and are shown as such; so if you intend then to serve as quotations that is really not clear at all and very confusing to see them as code snippets. :) this used to be discussed on meta in years past; I seem to remember seeing one user even state on their profile "if you don't use backticks for quotes, we can probably be friends on SO" or something like that. :) – Will Ness Dec 12 '20 at 00:03
1

@MostowskiCollapse *"and this discrete logarithm suggestion is not mine."* What's [this](https://stackoverflow.com/revisions/65208158/1) then? For anyone trying to make sense of this thread: OP deleted a whole bunch of outrageous comments, some of them claiming to never have said what he definitely said. – MWB Dec 12 '20 at 00:21

score 0 · Answer 2 · 2020-12-13T21:30:36.917

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

((meta:) btw you can edit your deleted answer without undeleting it. I've done that a few times myself) :) — Will Ness, Dec 12 '20 at 00:12
Yes, I noticed that there is some new functionality, but I am not yet used to it. — , Dec 12 '20 at 00:13

Discrete Logarithm in Prolog

2 Answers2