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