高速べき乗計算

y = xのn乗 を計算する「高速べき乗アルゴリズム」を考える． 
　　　x, y , n はそれぞれ整数型（おおきな桁数まで扱えるとする） 
　　　n には 1 以上の整数しか入力しないものとする． 

２進法の考え方を利用すると，ｘｙ を非常に早く計算することが出来る．

例１　ｎが奇数の場合だけに通用する方法

　　アルゴリズムの概要 

　　    (1) n, x の入力
　　    (2) y := x  (x を y に代入する）
　　    (3) n = 1 ならば　終了
　　    (4) そうでなければ，
    　　     n := n div 2 (n を 2 で割った商を n に代入する)
        　　 x := x * x   (x の２乗を x に代入する)
　　    (5) ( ｎが奇数　) でなければ (3) へ戻る
　　    (6) y := y * x (y と x の積を y へ代入する) そして (3) へ戻る

　　プログラム

program bekijyou(input,output);

var y,x,n:integer;

begin
	write(output,'n=');readln(input,n);
	write(output,'x=');readln(input,x);
	y:=x;
	while n>1 do
	begin
		n:=n div 2;  // nを2で割った商をnに代入する
		x:=x*x;      // xの2乗をxに代入する
                if (n mod 2)=1 then      // nが奇数でなければ戻る。つまり奇数の時は以下を実行する
		y:=y*x;      // 計算後戻る
	end;
	writeln(output,'y=',y);
end.

例２　ｎが奇数でも偶数でも通用する方法

　　アルゴリズムの概要

　　    (1) n, x の入力
　　    (2) nが偶数ならば、y := 1、nが奇数ならばy:=x
　　    (3) n = 1 ならば　終了
　　    (4) そうでなければ，
    　　     n := n div 2 (n を 2 で割った商を n に代入する)
        　　 x := x * x   (x の２乗を x に代入する)
　　    (5) ( ｎが奇数　) でなければ (3) へ戻る
　　    (6) y := y * x (y と x の積を y へ代入する) そして (3) へ戻る

　　プログラム

program bekijyou(input,output);

var y,x,n:integer;

begin
	write(output,'n=');readln(input,n);
	write(output,'x=');readln(input,x);
	if (n mod 2)=0 then y:=1 else y:=x;
	while n>1 do
	begin
		n:=n div 2;  // nを2で割った商をnに代入する
		begin
			x:=x*x;      // xの2乗をxに代入する
			if (n mod 2)=1 then
			y:=y*x;      // 計算後戻る
		end;
	end;
	writeln(output,'y=',y);
end.