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

[Leshii]

Доброго времени суток. Требуется помощь с написанием программы. Ниже прилагаю алгоритм решения и свои наработки.

(Условие)Допустим что нам нужно вычислить точное значиние a^n для достаточно большого значение N.

Алгоритм

Если N ( степень ) четное, тогда a^n=(a^n/2)^2. А если N нечетное, то тогда a^n = a*(a^n/2)^2. В любом случае значение показателя степени уменьшено наполовину, а вычисление сведено к, самое большее, двум операциям умножения. Таким образом, для вычисления конечного значения будет достаточно О(lg(n)) операций умножения.

Псевдокод.

function power ( a, n)
 if ( n = 0 ) return(1)
 x = power(a,n/2)
if  N is even ( четное ) then retrun(x^2)
 else
return(a * x^2);

Проблемы у меня возникли при реализации на паскале, а именно с написанием функции ( настолько привык к ретурнам в С++ что уже подзабыл как в паскале в функции можно обойтись без сего ретурна ).

Код.

var
 n, pow: longint;
 a: integer;
 s: string//для вывода длинного числа
 
function power( a, n: longint):longint;
var
 x: longint;
begin
if n = 0 then write(1);
x:= power(a,n/2);
if n mod 2 = 0 then power(sqr(x));
else power (a*sqr(x));
power:=x;
end;

begin

read(n);
a:=3;

pow:=power(a,n);
str(pow,s);
writeln(s);

end.

В функции постоянно ругается на типы в месте где выделил красным.
Заранее благодарен за помощь.

[Kostia]

n/2 - double
n div 2 - int

если память не изменяет. Кажись еще так можно round(n/2)

Ну а return легко заменить выходом из функции exit;
Result := value; exit;

[Leshii]

Благодарю, полезли новые ошибки =) будем разбираться.

[Leshii]

Ну собственно вот, что получилось.

var
 n, pow: longint;
 a: integer;
 s: string//для вывода длинного числа
 
function power( a, n: longint):longint;

begin
if n = 0 then begin
 power:=1;
 exit;
end;

if n mod 2 = 0 then 
power:=sqr(power(a, n div 2));
 else 
power :=a*sqr(power(a, n div 2));

end;

begin

read(n);
a:=3;

pow:=power(a,n);
str(pow,s);
writeln(s);

end.

[Kostia]

как-то так:

function fast_power(a,b: longint): integer;
var
  c: integer;
begin
  if(b = 1) then Result := a
  else
  if(b > 1) then
  begin
    if(b mod 2 = 0) then
      Result := sqr(fast_power(a, b div 2))
    else
      Result := a * sqr(fast_power(a, b div 2));
  end
end;

но от рекурсии я бы избавился.

[spein]

А не проще ли так?

{a^(b)}
var:=exp(a*ln(b));

[Leshii]

насколько помню а^b , а не b^a.( просто потому, что основание то логарифма по формуле а )

var:=exp(a*ln(b));

Поясню почему не просто

Такого рода задачи, в основном возникают в криптографии при проверке числа на простоту. Проблемы с точностью не позволяют воспользоваться даной форумулой

exp(b*ln(a))

возведения в степень.

Могу если захотите привести пример задачи, и возможные способы её реализации.