Правило для вычисления степени числа, когда показатель степени отрицателен в прологе?

Question

У меня есть степенная функция pow, которая пытается вычислить значение B до степени E.До сих пор я обрабатывал случаи -
1. Показатель степени равен 0
2. Показатель отличен от нуля

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

Как добавить еще один случай, когда функция мощности может обрабатывать отрицательные показатели?

Answer 1

Во-первых, нужно подумать, как определить 0 ⁰ . Формально говоря, это неопределенно . Это может быть ноль или может быть 1. Как говорит Mathworld Вольфрама в своей статье о силах и в статье о нуле :

0 ⁰ (от нуля до нулевой степени) сам по себе не определен. Отсутствие четко определенного значения для этой величины следует из взаимно противоречивых фактов, что a ⁰ всегда равно 1, поэтому 0 ⁰ должно равняться 1, но 0 ^a всегда равно 0 (для a > 0), поэтому 0 ^a должно быть равно 0. выбор определения для 0 ⁰ обычно определяется как неопределенный, хотя определение 0 ⁰ = 1 позволяет просто выразить некоторые формулы (Knuth 1992; Knuth 1997, p. 57).

Итак, вы должны сначала выбрать, как определить особый случай 0 ⁰ : это 0? Это 1? Это неопределенно?

Я предпочитаю смотреть на это как на неопределенное.

При этом вы можете смотреть на положительный показатель как указанное повторное умножение (например, 10 ³ равно 10 * 10 * 10 или 1000), и вы можете смотреть на отрицательный показатель как на повторяющийся деление (например, 10 ^-3 равно (((1/10) / 10) / 10) или 0,001). Моя склонность, отчасти потому, что мне нравится симметрия этого подхода, а отчасти, чтобы избежать срезов (поскольку срез часто является сигналом того, что вы не определили решение правильно), будет выглядеть примерно так:

% -----------------------------
% 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 )
  .

Другой подход, как отмечали другие, заключается в определении положительного показателя как показателя повторного умножения, а отрицательного показателя - как обратного значения положительного показателя, поэтому 10 ³ равно 10 * 10 * 10 или 1000, и 10 ^-3 равно 1 / (10 ³ ), или 1/1000 или 0,001. Чтобы использовать это определение, я бы снова избежал порезов и сделал что-то вроде этого:

% -----------------------------
% 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 )
  .

Answer 2

Не забывайте, что a^(2b) = (a^b)^2 и x^2 = x*x. Можно назвать хвостовой рекурсивный рабочий предикат с аккумулятором нехвостым способом из предиката верхнего уровня "UI". Таким образом, вам не нужно реализовывать рабочий предикат для отрицательных степеней, а скорее использовать его для положительной силы и изменять его результат в предикате верхнего уровня (я вижу, это уже было предложено):

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

Answer 3

Для начала, ваше второе предложение не является хвостовым рекурсивным (вы можете прочитать о теме здесь ).Это означает, что в конечном итоге вам не хватит памяти стека вызовов при ее запуске.Хорошо бы использовать аккумулятор, чтобы сделать его рекурсивным.Вы можете добиться этого следующим образом:

% 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).

Затем вы можете просто обработать отрицательный случай, добавив это предложение поверх других (оно просто говорит прологу, что отрицательная сила является обратной положительной):

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

Обратите внимание, что вы можете сделать это напрямую с помощью своего кода:

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

Плюс, мы теперь добавили очень красное сокращение (см. здесь значение красного среза при необходимости).Так что было бы лучше превратить в зеленый срез с этой модификацией:

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).