X to the power N, and X to the power N mod M
check_determ
domains
int = integer
predicates
power(int,int,int)
power_1(int,int,int,int)
powermod(int,int,int,int)
powermod_1(int,int,int,int,int)
clauses
/* power(X, N, Y) is true if Y is the result of raising X to the power N, */
/* where N is a positive integer. */
power(X, N, Y):-
N >= 0,
power_1(N, X, 1, Y).
power_1(0, _, Y, Y):-!.
power_1(N, X, Y0, Y):-
1 = N mod 2,
!,
N1 = N div 2,
X1 = X * X,
Y1 = Y0 * X,
power_1(N1, X1, Y1, Y).
power_1(N, X, Y0, Y):-
N1 = N div 2,
X1 = X * X,
power_1(N1, X1, Y0, Y).
/* powermod(X, N, M, Y) is true if Y is the result of raising X to the */
/* power N, mod M, where N and M are positive integers. */
powermod(X, N, M, Y):-
N >= 0,
M > 0,
powermod_1(N, X, M, 1, Y).
powermod_1(0, _, _, Y, Y):-!.
powermod_1(N, X, M, Y0, Y):-
1 = N mod 2,
!,
N1 = N div 2,
X1 = X * X mod M,
Y1 = Y0 * X mod M,
powermod_1(N1, X1, M, Y1, Y).
powermod_1(N, X, M, Y0, Y):-
N1 = N div 2,
X1 = X * X mod M,
powermod_1(N1, X1, M, Y0, Y).
Turbo Prolog Index
Home Page