CODEWITHSUNDEEP
functionprologexponentiation
user3241846
user3241846

Reputation: 677

Prolog Power Function

I am new to Prolog and while I can understand the code, I find it hard to create a program. I am trying to create a function that takes an integer and return 2^(integer) example pow(4) returns 16 (2^4). I also need it to be in a loop to keep taking input until user inputs negative integer then it exits.

In this example, C is counter, X is user input, tried to include variable for output but cant think how to integrate it.

pow(0):- 0.
pow(1):- 2.
pow(X):-
   X > 1, 
   X is X-1,
   power(X),
   C is X-1,
   pow(X1),
   X is 2*2.
pow(X):- X<0, C is 0.
pow(C).

Upvotes: 0

Views: 4526

Answers (2)

Nicholas Carey
Nicholas Carey

Reputation: 74177

The [naive] recursive solution:

pow2(0,1) .     % base case: any number raised to the 0 power is 1, by definition
pow2(N,M) :-    % a positive integral power of 2 is computed thus:
  integer(N) ,  % - verify than N is an inetger
  N > 0 ,       % - verify that N is positive
  N1 is N-1 ,   % - decrement N (towards zero)
  pow2(N1,M1) , % - recurse down (when we hit zero, we start popping the stack)
  M is M1*2     % - multiply by 2
  .             %
pow2(N,M) :-    % negative integral powers of 2 are computed the same way:
  integer(N) ,  % - verify than N is an integer
  N < 0 ,       % - verify than N is negative
  N1 is N+1 ,   % - increment N (towards zero).
  pow2(N1,M) ,  % - recurse down (we we hit zero, we start popping the stack)
  M is M / 2.0  % - divide by 2.
  .             % Easy!

The above, however, will overflow the stack when the recursion level is sufficiently high (ignoring arithmetic overflow issues). SO...

The tail-recursive solution is optimized away into iteration:

pow2(N,M) :-      %
  integer(N) ,    % validate that N is an integer
  pow2(N,1,M)     % invoke the worker predicate, seeding the accumulator with 1
  .               %

pow2(0,M,M) .     % when we hit zero, we're done
pow2(N,T,M) :-    % otherwise...
  N > 0 ,         % - if N is positive,
  N1 is N-1 ,     % - decrement N
  T1 is T*2 ,     % - increment the accumulator
  pow2(N1,T1,M)   % - recurse down
  .               %
pow2(N,T,M) :-    % otherwise...
  N < 0 ,         % - if N is negative,
  N1 is N+1 ,     % - increment N
  T1 is T / 2.0 , % - increment the accumulator
  pow2(N1,T1,M)   % - recurse down
  .               %

Upvotes: 1

Sergii Dymchenko
Sergii Dymchenko

Reputation: 7209

You really need to read something about Prolog before trying to program in it. Skim through http://en.wikibooks.org/wiki/Prolog, for example.

Prolog doesn't have "functions": there are predicates. All inputs and outputs are via predicate parameters, the predicate itself doesn't return anything.

So pow(0):- 0. and pow(1):- 2. don't make any sense. What you want is pow(0, 0). and pow(1, 2).: let the first parameter be the input, and the second be the output.

X is X-1 also doesn't make sense: in Prolog variables are like algebra variables, X means the same value through the whole system of equations. Variables are basically write-once, and you have to introduce new variables in this and similar cases: X1 is X-1.

Hope that's enough info to get you started.

Upvotes: 2

Related Questions