1

I have a power function pow that attempts to calculate the value of B to the power of E. So far I handle the cases-
1. exponent is 0
2. exponent is non-zero

pow(B,0,1).
pow(B,E,Result):-   E2 is E - 1,
                    pow(B,E2,Result2),
                    Result is B*Result2.

How can I add another case where the power function can handle negative exponents?

3 Answers 3

4

First, one should consider how to define 00. Formally speaking it is indeterminate. It could be zero or it could be 1. As Wolfram's Mathworld says in its article on powers and in its article on zero:

00 (zero to the zeroth power) itself is undefined. The lack of a well-defined meaning for this quantity follows from the mutually contradictory facts that a0 is always 1, so 00 should equal 1, but 0a is always 0 (for a > 0), so 0a should equal 0. The choice of definition for 00 is usually defined to be indeterminate, although defining 00 = 1 allows some formulas to be expressed simply (Knuth 1992; Knuth 1997, p. 57).

So you should first choose how to define the special case of 00: Is it 0? Is it 1? Is it undefined?

I choose to look at it as being undefined.

That being said, you can look at a positive exponent as indicated repeated multiplication (e.g. 103 is 10*10*10, or 1,000), and you can look at a negative exponent as indicating repeated division (e.g, 10-3 is (((1/10)/10)/10), or 0.001). My inclination, partly because I like the symmetry of this approach and partly to avoid the cuts (since a cut is often a signal that you've not defined the solution properly), would be something like this:

% -----------------------------
% The external/public predicate
% -----------------------------
pow( 0 , 0 , _ ) :- ! , fail .
pow( X , N , R ) :-
  pow( X , N , 1 , R )
  .

% -----------------------------------
% the tail-recursive worker predicate
% -----------------------------------
pow( _ , 0 , R , R  ).
pow( X , N , T , R  ) :-
  N > 0 ,
  T1 is T * X ,
  N1 is N-1   ,
  pow( X , N1 , T1 , R )
  .
pow( _ , 0 , R , R  ) :-
  N < 0 ,
  T1 is T / X ,
  N1 is N+1   ,
  pow( X , N1 , T1 , R )
  .

The other approach, as others have noted, is to define a positive exponent as indicating repeated multiplication, and a negative exponent as indicating the reciprocal of the positive exponent, so 103 is 10*10*10 or 1,000, and 10-3 is 1/(103), or 1/1,000 or 0.001. To use this definition, I'd again avoid the cuts and do something like this:

% -----------------------------
% the external/public predicate
% -----------------------------
pow( 0 , 0 , _ ) :-  % 0^0 is indeterminate. Is it 1? Is it 0? Could be either.
  ! ,
  fail
  .
pow( X , N , R ) :-
  N > 0 ,
  pow( X , N , 1 , R )
  .
pow( X , N , R ) :-
  N < 0 ,
  N1 = - N ,
  pow( X , N1 , 1 , R1 ) ,
  R is 1 / R1
  .

% -----------------------------------
% The tail-recursive worker predicate
% -----------------------------------
pow( _ , 0 , R , R  ).
pow( X , N , T , R  ) :-
  N > 0 ,
  T1 is T * X ,
  N1 is N-1   ,
  pow( X , N1 , T1 , R )
  .
1
  • I really appreciate the time and care you took to write down such a clear and comprehensive answer. Also, I personally consider 0^0 as undefined, although I understand there are different ways to look at it. For anyone stumbling onto this read - askamathematician.com/2010/12/… Nov 26, 2011 at 15:38
2

Don't forget that a^(2b) = (a^b)^2 and x^2 = x*x. It is ok to call a tail-recursive working predicate with accumulator, in a non-tail fashion, from a top-level "UI" predicate. That way you don't have to implement working predicate for negative powers but rather reuse the one for positive power, and alter its result in the top-level predicate (I see this has already been suggested):

pow(B, E, R):- E<0 -> ... ; E=:=0 -> ... ; E>0 -> ... .
2

To start, your second clause is non tail recursive (you can read about the subject here). It means that eventually, you will run out of call stack memory when running it. A good thing would be to use an accumulator to make it tail recursive. You can achieve that as follows :

% we add an accumulator to poW/3, making it pow/4.
pow(B, E, Result) :- pow(B, E, 1, Result).

% when we hit 0, our accumulator holds B^E so we unify it with result.
pow(_, 0, Accu, Accu) :- !.

% at each step, we multiply our accumulator by B
pow(B, E, Accu, Result) :-
    NewE is E - 1,
    NewAccu is Accu * B,
    pow(B, NewE, NewAccu, Result).

Then, you can simply handle the negative case by adding this clause on top of the others (it simply tells prolog that a negative power is the inverse of the positive one) :

pow(B, E, Result) :-
    E < 0,
    PositiveE is - E,
    pow(B, PositiveE, 1, R),
    !,
    Result is 1 / R.

Note that you can do it directly with your code :

pow(B, E, Result) :-
    E < 0,
    PositiveE is - E,
    pow(B, PositiveE, R),
    !,
    Result is 1 / R.

Plus, we now introduced a very red cut (see here for the meaning of red cut if necessary). So it'd be better to turn into a green cut with this modification :

pow(B, E, Result) :-
    E < 0,
    PositiveE is - E,
    pow(B, PositiveE, 1, R),
    !,
    Result is 1 / R.

% we add an accumulator to poW/3, making it pow/4.
pow(B, E, Result) :-
    E >= 0, %************* HERE *****************
    pow(B, E, 1, Result).

% when we hit 0, our accumulator holds B^E so we unify it with result.
pow(_, 0, Accu, Accu) :- !.

% at each step, we multiply our accumulator by B
pow(B, E, Accu, Result) :-
    NewE is E - 1,
    NewAccu is Accu * B,
    pow(B, NewE, NewAccu, Result).
1
  • That was very informative. Thanks!! (esp. for the non tail recursive and red cut concepts .. ) Nov 23, 2011 at 12:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.