Быстрое возведение в степень. Pascal, Delphi.

итак, данный алгоритм основан на том, что:
a^p = a^p-1 * a;
a^p = (a^p/2)^2, если p = 2;
Собственно тогда все очень просто

Код:


Function Power(a, p: integer): integer;
Begin
  if p = 0 then
  begin
    power := 1;
    exit;
  end;
  if p mod 2 = 0 then
    power := sqr(power(a, p div 2))
  else
    power := power(a, p - 1) * a;
end;


Также эту функцию можно использовать для возведения очень больших чисел в степень, но тогда необходимо немного изменить код.

HELP!!!! Голову сломала...Помогите, пожалуйста! На вводе а,N:integer. Вычислить степень числа для 1<a<1000, 1<N<1000 (паскаль). Понимаю, что длинная арифметика, но момент преобразования результата не могу поймать. Если есть возможность - помогите. С уважением.

В принципе, можно использовать произведение длинных чисел в цикле...
https://progaem.forum2x2.ru/t93-topic

Попробую поискать что-нибудь более оптимальное)

Спасибо за надежду. Я уже подумывала об умножении длинных...Но в условии входные - INTEGER! И всё тут...На компромиссы рассчитывать не приходится. Буду ждать с нетерпением С уважением.

Везде, где ни искал, есть только такая же статья, как у нас(
Видимо придется все-таки работать с длинным умножением...

Я нашла умножение длинного на короткое... но не могу сообразить куда промежуточный результат засунуть, чтобы применить этот код...столько всего в голове крутится, а как только за комп - в кучу собрать не могу...
Procedure Mul(Const A: TLong;Const К: Longlnt;Var С: TLong) ;
Var i: Integer;
{результат - значение переменной С}
Begin
FillChar (С, SizeOf (С), 0) ;
If K=0 Then Inc(С[0]){умножение на ноль}
Else Begin
For i:==l To A[0] Do Begin
C[i+l]:=(LongInt(A[i])*K+C[i]) Div Osn;
C[i]:=(LongInt(A[i])*K +C[i]) Mod Osn;
End;
If C[A[0]+1]>0 Then C[0]:=A[0]+1
Else C[0]:=A[0] ;
{определяем длину результата}
End;
End;
Может Вы поможете?

Я не очень понимаю, что ты имеешь ввиду под промежуточным результатом...
А на форуме у нас уже есть произведение длинного на короткое. Посмотри, может там попонятнее будет.
https://progaem.forum2x2.ru/t93-topic (функция scalmul).

Но вот зачем тебе длинное на короткое, если ты хочешь большое число в степень возвести...

Так говорю в голове - каша!