#### X to the power N

/* 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 is N mod 2,
!,
N1 is N // 2,
X1 is X * X,
Y1 is Y0 * X,
power_1(N1, X1, Y1, Y).
power_1(N, X, Y0, Y):-
N1 is N // 2,
X1 is X * X,
power_1(N1, X1, Y0, Y).

#### X to the power N modulo M

/* 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 is N mod 2,
!,
N1 is N // 2,
X1 is (X * X) mod M,
Y1 is (Y0 * X) mod M,
powermod_1(N1, X1, M, Y1, Y).
powermod_1(N, X, M, Y0, Y):-
N1 is N // 2,
X1 is (X * X) mod M,
powermod_1(N1, X1, M, Y0, Y).

LPA Index
Home Page