Пролог - составить список

Question

Учитывая аргумент makelist(A,N,K,M,L) :-, должен расширяться и возвращать true, если A,N,K,M,L>0 Целые числа с M>=2 и L список:

[A^N mod M , A^(N+1) mod M , A^(N+2) mod M , ... , A*(N+K) mod M]

Ожидаемые результаты:

| ?- makelist(10,2,1,10000,L).
L = [100,1000]
| ?- makelist(2,6,10,100,L).
L = [64,28,56,12,24,48,96,92,84,68,36]
| ?- makelist(12345678,3,8,100,L).
L = [52,56,68,4,12,36,8,24,72]
| ?- makelist(2,3000,5,7,L).
L = [1,2,4,1,2,4]
| ?- makelist(2,555000,5,17,L).
L = [1,2,4,8,16,15]
| ?- makelist(2,3000000,5,21,L).
L = [1,2,4,8,16,11]
| ?- makelist(142857,98765432,9,100,L).
L = [1,57,49,93,1,57,49,93,1,57]

я думал, что для начала будет реализован элемент K экспоненты (N+K) путем взятия чисел от 0 до K

bet(N, M, K) :- N =< M, K = N.
bet(N, M, K) :- N < M, N1 is N+1, bet(N1, M, K).


makelist(A,N,K,M,L) :- bet(0,K,(N+K)),

Answer 1

Решение для малых показателей

Хорошо известное свойство модульного возведения в степень устанавливает, что:

x ^ n мод м = ( х мод м ) ^ n мод m

Таким образом, для больших баз с малыми показателями вы можете использовать следующий код:

makelist(A, N, K, M, L) :-
    A>0, N>0, K>0, M>0,
    K1 is N + K,
    findall(X, (between(N,K1,E), X is (A mod M)^I mod M), L).

Вот некоторые решения, найденные с этим кодом:

?- makelist(10,2,1,10000,L).
L = [100, 1000].

?- makelist(2,6,10,100,L).
L = [64, 28, 56, 12, 24, 48, 96, 92, 84|...].

?- makelist(12345678,3,8,100,L).
L = [52, 56, 68, 4, 12, 36, 8, 24, 72].

?- makelist(2,3000,5,7,L).
L = [1, 2, 4, 1, 2, 4].

?- makelist(2,555000,5,17,L).
L = [1, 2, 4, 8, 16, 15].

?- makelist(2,3000000,5,21,L).
L = [1, 2, 4, 8, 16, 11].

Обратите внимание, что без использования такого свойства мы не можем вычислить ответ для больших базисов с большими показателями:

?- X is 142857^98765432 mod 100.
ERROR: Stack limit (0.5Gb) exceeded

?- X is (142857 mod 100)^98765432 mod 100.
X = 1.

Решение для больших показателей

Однакодля больших показателей этот код оказывается очень неэффективным .Например:

?- time(makelist(142857,98765432,9,100,L)).
% 47 inferences, 115.328 CPU in -544348879559065600.000 seconds (?% CPU, 0 Lips)
L = [1, 57, 49, 93, 1, 57, 49, 93, 1|...].

Итак, лучший подход для большого показателя n - это использовать следующее определение:

• , если n = 0, затем x ^ n = 1
• В противном случае, если n = 1, то x ^ n = x
• В противном случае, если n является четным, то x ^ n =( x ^ 2) ^ ( n / 2)
• иначе, если n нечетно, тогда x ^ n = x * ( x ^ 2) ^ floor ( n / 2)

С этим определением мы можем вычислить x ^ n с использованием только O (lg n ) умножений.На основании этого мы можем определить следующие предикаты:

fast_pow(X, N, M, P) :-
    (   N < 32
    ->  P is (X mod M)^N mod M
    ;   (   X1 is (X mod M)^2 mod M,
            N1 is N//2,
            fast_pow(X1, N1, M, P1),
            (   N mod 2 =:= 0
            ->  P is P1
            ;   P is (X mod M)*P1  mod M ) ) ).

fast_makelist(A, N, K, M, L) :-
    A>0, N>0, K>0, M>0,
    K1 is N + K,
    findall(P, (between(N,K1,E), fast_pow(A,E,M,P)), L).

Теперь у нас есть:

?- time(fast_makelist(142857,98765432,9,100,L)).
% 1,704 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
L = [1, 57, 49, 93, 1, 57, 49, 93, 1|...].

Answer 2

Вы можете начать со следующего кода:

makelist(A,N,0,M,[X]) :- X is mod(A^N,M).
makelist(A,N,K,M,[X|L]) :-  
        Max is N + K,
        N <  Max,
        N1 is  N + 1,
        K1 is K-1,
        X is mod(A^N, M),
        makelist(A, N1, K1, M, L).

, а затем применить дополнительные ограничения, такие как M>= 2.