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